Problem:
Binary Tree A rooted binary tree is a tree with a root node in which every node has at most two children. Your task is to write a program which reads a rooted binary tree T and prints the following information for each node u of T :  node ID of u  parent of u  sibling of u  the number of children of u  depth of u  height of u  node type (root, internal node or leaf)  If two nodes have the same parent, they are siblings . Here, if u and v have the same parent, we say u is a sibling of v (vice versa). The height of a node in a tree is the number of edges on the longest simple downward path from the node to a leaf. Here, the given binary tree consists of n nodes and evey node has a unique ID from 0 to n -1. Input The first line of the input includes an integer n , the number of nodes of the tree. In the next n lines, the information of each node is given in the following format:  id left right   id is the node ID, left is ID of the left child and right is ID of the right child. If the node does not have the left (right) child, the left ( right ) is indicated by -1 . Output Print the information of each node in the following format:  node  id : parent = p , sibling = s , degree = deg , depth = dep , height = h , type   p is ID of its parent. If the node does not have a parent, print -1 .  s is ID of its sibling. If the node does not have a sibling, print -1 .  deg , dep and h are the number of children, depth and height of the node respectively.  type is a type of nodes represented by a string ( root , internal node or leaf . If the root can be considered as a leaf or an internal node, print root . Please follow the format presented in a sample output below. Constraints  1 ≤ n ≤ 25  Sample Input 1 9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1 Sample Output 1 node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node
node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf
node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf
node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node
node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node
node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf
node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf
node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf   Reference Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

Solution (Python):
class Node:
    def __init__(self):
        self.id = -1
        self.parent = None
        self.childs = [None, None]
        self.sibling = -1
        self.depth = -1
        self.height = -1

    def parentId(self):
        return -1 if self.parent == None else self.parent.id

    def type(self):
        if self.parent == None:
            return "root"
        elif self.childs[0] != None or self.childs[1] != None:
            return "internal node"
        return "leaf"

    def degree(self):
        r = 0
        for c in self.childs:
            r += 1 if c != None else 0
        return r


def setDepthAndHeight(node, d):
    h = 0
    node.depth = d
    for i in range(2):
        if node.childs[i] != None:
            h = max(h, setDepthAndHeight(node.childs[i], d+1)+1)
    node.height = h
    return h


n = int(input())
nodes = [Node() for _ in range(n)]

for i in range(n):
    id, l, r = map(int, input().split())
    p = nodes[id]
    p.id = id
    if l >= 0:
        nodes[l].parent = p
        nodes[l].sibling = r
        p.childs[0] = nodes[l]
    if r >= 0:
        nodes[r].parent = p
        nodes[r].sibling = l
        p.childs[1] = nodes[r]

root = None
for node in nodes:
    if node.type() == "root":
        root = node
        break

setDepthAndHeight(root, 0)

for node in nodes:
    s = f"node {node.id}: "
    s += f"parent = {node.parentId()}, "
    s += f"sibling = {node.sibling}, "
    s += f"degree = {node.degree()}, "
    s += f"depth = {node.depth}, "
    s += f"height = {node.height}, "
    s += f"{node.type()}"
    print(s)

Solution (Python):
class Node:
    def __init__(self, n, left=None, right=None, parent=None):
        self.n = n
        self.parent = parent
        self.left = left
        self.right = right

    @property
    def depth(self):
        count = 0
        p = self.parent
        while p is not None:
            count += 1
            p = p.parent
        return count

    @property
    def height(self):
        if self.left is None and self.right is None:
            return 0
        elif self.left is None:
            return 1 + self.right.height
        elif self.right is None:
            return 1 + self.left.height
        else:
            left_h = 1 + self.left.height
            right_h = 1 + self.right.height
            return max(left_h, right_h)

    @property
    def sibling(self):
        if self.parent is None:
            return -1
        for node in [self.parent.right, self.parent.left]:
            if node is None:
                return -1
            if node.n != self.n:
                return node.n

    @property
    def degree(self):
        count = 0
        if self.right:
            count += 1
        if self.left:
            count += 1
        return count

    @property
    def type(self):
        if self.parent is None:
            return "root"
        elif self.left is None and self.right is None:
            return "leaf"
        else:
            return "internal node"

    def __str__(self):
        if self.parent is None:
            parent = -1
        else:
            parent = self.parent.n

        return "node {}: parent = {}, sibling = {}, degree = {}, " \
               "depth = {}, height = {}, {}".format(
            self.n, parent, self.sibling, self.degree,
            self.depth, self.height, self.type
        )


n = int(input())
nodes = []
for i in range(n):
    nodes.append(Node(i))

for _ in range(n):
    x, y, z = map(int, input().split())
    node = nodes[x]

    if y == -1:
        node.left = None
    else:
        nodes[y].parent = node
        node.left = nodes[y]

    if z == -1:
        node.right = None
    else:
        nodes[z].parent = node
        node.right = nodes[z]

for n in nodes:
    print(n)

Solution (Python):

import queue

class Node:
    def __init__(self, myNum, left, right):
        self.myNum = myNum
        self.left = left
        self.right = right
        self.parent = -1
        self.bs = -1
        self.nodeType = ""
        self.degree = -1
        self.depth = -1
        self.height = -1

        
nodes = []
n = int(input().rstrip())
for i in range(n):
    line = [int(j) for j in input().rstrip().split()]
    nodes.append(Node(line[0],line[1],line[2]))

nodes = sorted(nodes, key = lambda x: x.myNum)


for node in nodes:
    dg = 0
    if node.left != -1:
        nodes[node.left].parent = node.myNum
        dg += 1
    if node.right != -1:
        nodes[node.right].parent = node.myNum
        dg += 1
    node.degree = dg


for node in nodes:
    if node.left != -1 and node.right != -1:
        nodes[node.left].bs = nodes[node.right].myNum
        nodes[node.right].bs = nodes[node.left].myNum


for node in nodes:
    if node.parent == -1:
        node.nodeType = "root"
        node.depth = 0
        rootNum = node.myNum
    elif node.left == -1 and node.right == -1:
        node.nodeType = "leaf"
    else:
        node.nodeType = "internal node"


q = queue.Queue()
q.put(nodes[rootNum])
while not q.empty():
    nd = q.get()
    if nd.left != -1:
        nodes[nd.left].depth = nd.depth + 1
        q.put(nodes[nd.left])
    if nd.right != -1:
        nodes[nd.right].depth = nd.depth + 1
        q.put(nodes[nd.right])


for node in nodes:
    if node.parent == -1 or node.nodeType == "leaf":
        node.height = 0
        q.put(node)
while not q.empty():
    nd = q.get()
    if nd.parent != -1:
        nodes[nd.parent].height = max(nodes[nd.parent].height, nd.height + 1)
        q.put(nodes[nd.parent])


for node in nodes:
    print("node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}"
          .format(node.myNum, node.parent, node.bs, node.degree, node.depth, node.height, node.nodeType))

Solution (Python):
from sys import stdin

class Node:
    def __init__(self):
        self.parent = -1
        self.sibling = -1
        self.depth = -1
        self.height = -1
        self.children = [-1, -1]

class Tree:
    def __init__(self, nodes):
        self.nodes = nodes
        for i in range(self.size()):
            n = self.nodes[i]
            n.depth = self.depth(i)
            n.height = self.height(i)

    def depth(self, i):
        node = self.nodes[i]
        if self.isRoot(i):
            return 0
        else:
            return self.depth(node.parent)+1

    def height(self, i):
        node = self.nodes[i]
        if i == -1:
            return -1
        else:
            return max([self.height(c) for c in node.children])+1

    def size(self):
        return len(self.nodes)

    def isLeaf(self, i):
        return self.nodes[i].children == [-1, -1]

    def isRoot(self, i):
        return self.nodes[i].parent == -1

n = int(stdin.readline().rstrip())
nodes = [Node() for _ in range(n)]
for i in range(n):
    l = [int(x) for x in stdin.readline().rstrip().split()]
    nodes[l[0]].children = l[1:3]
    if l[1] != -1:
        nodes[l[1]].parent = l[0]
        nodes[l[1]].sibling = l[2]
    if l[2] != -1:
        nodes[l[2]].parent = l[0]
        nodes[l[2]].sibling = l[1]

t = Tree(nodes)
for i in range(t.size()):
    node = t.nodes[i]
    l = ["node ", i, ": parent = ", node.parent, ", sibling = ", node.sibling, ", degree = ", len([c for c in node.children if c != -1]), ", depth = ", node.depth, ", height = ", node.height, ", "]

    if t.isRoot(i):
        l.append("root")
    elif t.isLeaf(i):
        l.append("leaf")
    else:
        l.append("internal node")

    print(*l, sep="")

Solution (Python):
class node:
    parent = None
    depth = 0
    degree = 0
    height = 0

    def __init__(self, no, l, r,sib):
        self.no = no
        self.left = l
        self.right = r
        self.sibling = sib
    
    def setsibdepth(self, nodes, d):
        if self.left is None:
            return
        self.depth = d
        self.left.sibling = self.right
        self.right.sibling = self.left
        self.left.setsibdepth(nodes, d+1)
        self.right.setsibdepth(nodes, d+1)

    def setheight(self, nodes, h):
        if self.left is None:
            return h-1
        return max(self.left.setheight(nodes, h+1), self.right.setheight(nodes, h+1))



NULL = node(-1, None, None, None)
head = None
nodes = []
n = int(input())
for i in range(n):
    temp = node(i, None, None, NULL)
    nodes.append(temp)

for i in range(n):
    temp = list(map(int,input().split()))
    if temp[1] == -1:
        nodes[temp[0]].left = NULL
    else:
        nodes[temp[0]].left = nodes[temp[1]]
        nodes[nodes[temp[0]].left.no].parent = nodes[temp[0]]

    if temp[2] == -1:
        nodes[temp[0]].right = NULL
    else:
        nodes[temp[0]].right = nodes[temp[2]]
        nodes[nodes[temp[0]].right.no].parent = nodes[temp[0]]

    if temp[1] == -1 and temp[2] == -1:
        nodes[temp[0]].degree = 0
    elif temp[1] != -1 and temp[2] != -1:
        nodes[temp[0]].degree = 2
    else:
        nodes[temp[0]].degree = 1

for i in range(n):
    if nodes[i].parent is None:
        head = nodes[i]
        break

head.setsibdepth(nodes, 0)

for i in range(n):
    nodes[i].height = nodes[i].setheight(nodes, 0)

for i in range(n):
    if nodes[i].parent is None:
        print("node " + str(i) + ": parent = -1, sibling = "                              + str(nodes[i].sibling.no) + ", degree = " + str(nodes[i].degree) + ", depth = " + str(nodes[i].depth) + ", height = " + str(nodes[i].height) + ", root")
    elif nodes[i].left == NULL and nodes[i].right == NULL:
        print("node " + str(i) + ": parent = " + str(nodes[i].parent.no) + ", sibling = " + str(nodes[i].sibling.no) + ", degree = " + str(nodes[i].degree) + ", depth = " + str(nodes[i].depth) + ", height = " + str(nodes[i].height) + ", leaf")
    else:
        print("node " + str(i) + ": parent = " + str(nodes[i].parent.no) + ", sibling = " + str(nodes[i].sibling.no) + ", degree = " + str(nodes[i].degree) + ", depth = " + str(nodes[i].depth) + ", height = " + str(nodes[i].height) + ", internal node")

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

def upd_dpth(node, depth):
    par, sib, deg, dep, hei, l, r = nodes[node]
    height = 0
    if l != -1:
        height = max(height, upd_dpth(l, depth+1))
    if r != -1:
        height = max(height, upd_dpth(r, depth+1))
    nodes[node][3] = depth
    nodes[node][4] = height
    return height+1

N = INT()


nodes = [[-1, -1, 0, 0, 0, -1, -1] for i in range(N)]

for i in range(N):
    node, l, r = MAP()
    if l != -1:
        
        nodes[node][2] += 1
        
        nodes[l][0] = node
        
        nodes[l][1] = r
        
        nodes[node][5] = l
    if r != -1:
        nodes[node][2] += 1
        nodes[r][0] = node
        nodes[r][1] = l
        nodes[node][6] = r


for i in range(N):
    
    if nodes[i][0] == -1:
        upd_dpth(i, 0)

for i in range(N):
    par, sib, deg, dep, hei, l, r = nodes[i]
    if par == -1:
        _type = 'root'
    elif deg == 0:
        _type = 'leaf'
    else:
        _type = 'internal node'
    print('node {node}: parent = {parent}, sibling = {sibling}, \
degree = {degree}, depth = {depth}, height = {height}, {type}'.format(
        node=i, parent=par, sibling=sib, degree=deg, depth=dep, height=hei, type=_type))

Solution (Python):
class Node():
    def __init__(self,node_id,left,right):
        self.node_id = node_id
        self.parent = -1
        self.left = left
        self.right = right
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = 'leaf'

    def set_attr(self,node_id,parent,sibling,depth):
        if node_id == -1:
            return -1
        self.parent = parent
        self.sibling = sibling
        self.depth = depth
        self.degree = (self.left != -1)+(self.right != -1)
        if self.degree:
            self.type = 'internal node'
        if self.parent == -1:
            self.type = 'root'
        self.height = max(
            tree[self.left].set_attr(
            self.left,
            self.node_id,
            self.right,
            self.depth+1
            ),
            tree[self.right].set_attr(
            self.right,
            self.node_id,
            self.left,
            self.depth+1
            )
        )+1
        return self.height

n = int(input())
tree = [None]*n
root = set(range(n))

for _ in range(n):
    node_id,left,right = map(int,input().split())
    tree[node_id] = Node(node_id,left,right)
    root -= set([left,right])

root_id = root.pop()
tree[root_id].set_attr(root_id,-1,-1,0)
for node in tree:
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(node.node_id, node.parent, node.sibling, node.degree, node.depth, node.height, node.type))

Solution (Python):
from typing import List


class Node:
    parent = -1  
    sibling = -1  
    degree = -99  
    depth = -99  
    height = -99  
    node_type = 'Not set'  
    left = -99
    right = -99


num_of_node = int(input())
nodes = [Node() for i in range(num_of_node)]
for _i in range(num_of_node):
    node_id, left, right = map(int, input().split())
    
    nodes[node_id].left = left
    nodes[node_id].right = right

    degree = 0
    if left != -1:
        degree += 1
    if right != -1:
        degree += 1
    nodes[node_id].degree = degree


for i in range(num_of_node):
    if nodes[i].left != -1:
        nodes[nodes[i].left].parent = i
    if nodes[i].right != -1:
        nodes[nodes[i].right].parent = i


for i in range(num_of_node):
    if nodes[i].parent == -1:
        continue
    
    if nodes[nodes[i].parent].left == i and nodes[nodes[i].parent].right != -1:
        nodes[i].sibling = nodes[nodes[i].parent].right
    
    if nodes[nodes[i].parent].right == i and nodes[nodes[i].parent].left != -1:
        nodes[i].sibling = nodes[nodes[i].parent].left


def set_depth(node_id: int, depth: int):
    nodes[node_id].depth = depth
    if nodes[node_id].left != -1:
        set_depth(nodes[node_id].left, depth + 1)
    if nodes[node_id].right != -1:
        set_depth(nodes[node_id].right, depth + 1)



for i in range(num_of_node):
    if nodes[i].parent == -1:
        set_depth(i, 0)
        break


def set_height(node_id: int, height: int):
    if nodes[node_id].height < height:
        nodes[node_id].height = height
    if nodes[node_id].parent != -1:
        set_height(nodes[node_id].parent, height + 1)



for i in range(num_of_node):
    if nodes[i].degree == 0:
        set_height(i, 0)


for i in range(num_of_node):
    if nodes[i].parent == -1:
        nodes[i].node_type = 'root'
    elif nodes[i].degree != 0:
        nodes[i].node_type = 'internal node'
    else:
        nodes[i].node_type = 'leaf'


for i in range(num_of_node):
    out = f'node {i}: parent = {nodes[i].parent}, sibling = {nodes[i].sibling}'
    out += f', degree = {nodes[i].degree}, depth = {nodes[i].depth}'
    out += f', height = {nodes[i].height}, {nodes[i].node_type}'
    print(out)

Solution (Python):
def parent(s):
    sib[ch[s][0]] = ch[s][1]
    sib[ch[s][1]] = ch[s][0]
    if ch[s][0] != -1:
        par[ch[s][0]] = s
        dep[ch[s][0]] = dep[s]+1
        parent(ch[s][0])
    if ch[s][1] != -1:
        par[ch[s][1]] = s
        dep[ch[s][1]] = dep[s]+1
        parent(ch[s][1])


def setheight(t):
    h1 = h2 = 0
    if ch[t][0] != -1:
        h1 = setheight(ch[t][0]) + 1
    if ch[t][1] != -1:
        h2 = setheight(ch[t][1]) + 1
    high[t] = (h1 if h1 > h2 else h2)
    return high[t]
n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]

ch = {}
par = {}
sib = {}
dep = {}
deg = {}
high = {}
kara = []
for i in range(n):
    kara.append(i)

for i in data:
    tmp = 0
    if i[1] != -1:
        tmp += 1
    if i[2] != -1:
        tmp += 1
    deg[i[0]] = tmp
    ch[i[0]] = i[1:]
    try:
        kara.remove(i[1])
    except:
        pass
    try:
        kara.remove(i[2])
    except:
        pass
r = kara[0]

par[r] = -1
sib[r] = -1
dep[r] = 0
parent(r)
setheight(r)

for i in range(n):
    if par[i] == -1:
        tmp = 'root'
    elif ch[i][0] == -1 & ch[i][1] == -1:
        tmp = 'leaf'
    else:
        tmp = 'internal node'
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i, par[i], sib[i], deg[i], dep[i], high[i], tmp))

Solution (Python):
class Node:
    def __init__(self,parent,left,right):
        self.parent = parent
        self.left = left
        self.right = right

    def __repr__(self):
        return "{ "+ str(self.parent) + " " + str(self.left) + " " + str(self.right) + " }"



class BinarySearchTree:
    def __init__(self,size):
        self.tree = [Node(-1,-1,-1) for i in range(size+1)]
        self.root = -1

    def add(self,key,right,left):
        self.tree[key].left = left
        self.tree[key].right = right
        self.tree[left].parent = key
        self.tree[right].parent = key 
        
        

    def calcHeight(self,next,sum):
        if next == -1:
            return sum -1
        return max(self.calcHeight(self.tree[next].left,sum+1),self.calcHeight(self.tree[next].right,sum+1))

    def calcDepth(self,next):
        
        if next == -1:
            return -1
        return 1 + self.calcDepth(self.tree[next].parent)
    
    def getType(self,node):
        if node.parent == -1:
            return "root"
        elif node.right == node.left == -1:
            return "leaf"
        return "internal node"
    
    def printAll(self):
        for idx, node in enumerate(self.tree):
            if node.parent == -1:
                self.root = idx
                break
        self.tree.pop()
        for idx, node in enumerate(self.tree):
            parent = node.parent
            sibling = self.tree[node.parent].left
            if sibling == idx:
                sibling = self.tree[node.parent].right
            degree = 0
            if node.left != -1:
                degree += 1
            if node.right != -1:
                degree += 1
            depth = self.calcDepth(idx)
            height = self.calcHeight(idx,0)
            typed = self.getType(node)
            print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(idx,parent,sibling,degree, depth, height,typed))

N = int(input())
BST = BinarySearchTree(N)
for i in range(N):
    Q = list(map(int, input().split()))
    BST.add(Q[0],Q[1],Q[2])
BST.printAll()

Solution (Python):
import sys


class Node:
    def __init__(self):
        self.parent = self.left = self.right = None
        self.height = self.depth = None


n = int(sys.stdin.readline())

nodes = [Node() for _ in range(n)]

for _ in range(n):
    id, left, right = map(int, sys.stdin.readline().split())
    if left != -1:
        nodes[id].left = left
        nodes[left].parent = id
    if right != -1:
        nodes[id].right = right
        nodes[right].parent = id


def set_height(id):
    node = nodes[id]
    height = max(
        -1 if child is None else set_height(child)
        for child in (node.left, node.right)
    ) + 1
    node.height = height
    return height


def set_depth(id, depth):
    node = nodes[id]
    node.depth = depth
    for child in (node.left, node.right):
        if child is not None:
            set_depth(child, depth + 1)


root_id = next(i for i, node in enumerate(nodes) if node.parent is None)
set_height(root_id)
set_depth(root_id, 0)

for id, node in enumerate(nodes):
    sibling = -1
    if node.parent is not None:
        parent = nodes[node.parent]
        sibling = parent.right if parent.left == id else parent.left
        if sibling is None:
            sibling = -1

    node_type = 'internal node'
    if node.parent is None:
        node_type = 'root'
    elif node.left is None and node.right is None:
        node_type = 'leaf'

    print(
        (
            'node %d: parent = %d, sibling = %d, ' +
            'degree = %d, depth = %d, height = %d, %s'
        ) % (
            id,
            -1 if node.parent is None else node.parent,
            sibling,
            sum(child is not None for child in (node.left, node.right)),
            node.depth,
            node.height,
            node_type
        ))

Solution (Python):


class node:
    def __init__(self,nodeid):

        self.parent = None
        self.parentid = -1
        self.c_leftid = -1
        self.c_left = None
        self.c_rightid = -1
        self.c_right = None
        self.nodeid = nodeid
        self.type = "root"
    def setLeftChild(self,cn):
        self.c_left = cn
        self.c_leftid = cn.nodeid
        cn.parent = self
        cn.parentid = self.nodeid
        cn.setNodeType()
        self.setNodeType()
        return
    def setRightChild(self,cn):
        self.c_right = cn
        self.c_rightid = cn.nodeid
        cn.parent = self
        cn.parentid = self.nodeid
        cn.setNodeType()
        self.setNodeType()
        return
    def getDepth(self):
        cnt = 0
        t = self
        while True:
            if (t.parentid == -1 ):
                break
            t = t.parent
            cnt = cnt + 1
        return cnt
    def setNodeType(self):
        if (self.getDepth() == 0):
            self.type = "root"
        else:
            if ( self.c_rightid == -1 and self.c_leftid == -1 ):
                self.type = "leaf"
            else:
                self.type = "internal node" 
    def getNodeType(self):
        return self.type
    def getSibling(self):
        if ( self.parentid == -1):
            return -1
        i = self.parent
        if ( i.c_rightid == self.nodeid ):
            return i.c_leftid
        elif ( i.c_leftid == self.nodeid):
            return i.c_rightid
    def getHeight(self):
        lcnt = 0
        rcnt = 0
        if (self.c_leftid == -1  and self.c_rightid == -1 ):
            return 0
        elif (self.c_rightid  == -1):
            lcnt = lcnt + self.c_left.getHeight() + 1
        elif (self.c_leftid  == -1):
            rcnt = rcnt + self.c_right.getHeight() + 1
        else:
            lcnt = lcnt + self.c_left.getHeight() + 1
            rcnt = rcnt + self.c_right.getHeight() + 1
        if (lcnt >= rcnt):
            return lcnt
        else:
            return rcnt
    def getDegree(self):
        cnt = 0
        if (self.c_leftid != -1):
            cnt += 1
        if (self.c_rightid != -1):
            cnt += 1
        return cnt
    def showNode(self):
        i1 = self.nodeid
        i2 = self.parentid
        i3 = self.getSibling()
        i4 = self.getDegree()
        i5 = self.getDepth()
        i6 = self.getHeight()
        i7 = self.getNodeType()
        print ('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i1,i2,i3,i4,i5,i6,i7))
        return

nl = []
n = int(input())
for i in range(0,n):
    nl.append(node(i))

for i in range(0,n):
    (a,b,c) = map(int,input().split())
    if (b != -1):
        nl[a].setLeftChild(nl[b])
    if (c != -1):
        nl[a].setRightChild(nl[c])

for i in range(0,n):
    nl[i].showNode()

Solution (Python):
class Node:
    parent = ""
    sibling = ""
    depth = ""
    height = ""

    def __init__(self, left, right):
        self.left = left
        self.right = right

        if self.right == -1 and self.left == -1:
            self.degree = 0
            self.type = 'leaf'
        elif self.right == -1 or self.left == -1:
            self.degree = 1
            self.type = 'internal node'
        else:
            self.degree = 2
            self.type = 'internal node'


def add_parent_node_and_depth(nodes, parent_node_no, node_no, depth):
    nodes[node_no].parent = parent_node_no
    nodes[node_no].depth = depth

    left_node_no = nodes[node_no].left
    right_node_no = nodes[node_no].right

    left_height, right_height = 0, 0
    if left_node_no != -1:
        left_height = add_parent_node_and_depth(nodes, node_no, left_node_no, depth+1)
        nodes[left_node_no].sibling = right_node_no
    if right_node_no != -1:
        right_height = add_parent_node_and_depth(nodes, node_no, right_node_no, depth+1)
        nodes[right_node_no].sibling = left_node_no

    if left_node_no == -1 and right_node_no == -1:
        nodes[node_no].height = 0
    else:
        nodes[node_no].height = max(left_height, right_height) + 1
    return nodes[node_no].height


def main():
    n = int(input())
    nodes = {}
    for i in range(n):
        node_no, left, right = [int(x) for x in input().split()]
        nodes[node_no] = Node(left, right)

    lefts = [nodes[x].left for x in nodes]
    rights = [nodes[x].right for x in nodes]
    root_no = list(set(nodes.keys()) - set(lefts + rights))[0]

    nodes[root_no].type = 'root'
    nodes[root_no].sibling = -1
    add_parent_node_and_depth(nodes, -1, root_no, 0)

    for i in range(n):
        node = nodes[i]
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
            i, node.parent, node.sibling, node.degree, node.depth, node.height, node.type
        ))

    return

main()

Solution (Python):
class Trees():
    def __init__(self):
        self.nodes = {}
    def add_nodes(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)
    def add_child(self, id, child_id1, child_id2):
        for child_id in [child_id1, child_id2]:
            if child_id != -1:
                self.add_nodes(child_id)
                self.nodes[id].add_child_id(self.nodes[child_id])
        if child_id1 != -1:
            self.nodes[child_id1].sibling = child_id2
        if child_id2 != -1:            
            self.nodes[child_id2].sibling = child_id1
        self.nodes[id].left = child_id1
        self.nodes[id].right = child_id2
    def setheight(self, id):
        h1, h2 = 0, 0
        if self.nodes[id].right != -1:
            h1 = self.setheight(self.nodes[id].right) + 1
        if self.nodes[id].left != -1:
            h2 = self.setheight(self.nodes[id].left) + 1
        self.nodes[id].height = max(h1, h2)
        return max(h1, h2)
        

         
class Node():
    def __init__(self, id):
        self.node = id
        self.parent = None
        self.depth = 0
        self.nodetype = 'root'
        self.children = []
        self.sibling = -1
        self.degree = 0
        self.height = 0
        self.left = -1
        self.right = -1
     
    def add_child_id(self, child):
        child.parent = self
        self.children.append(child)
        child.update_depth()
        self.update_nodetype()
        child.update_nodetype()
        self.degree += 1
        
     
    def update_depth(self):
        depth = self.depth
        if self.parent:
            self.depth = self.parent.depth + 1
        if depth != self.depth:
            for child in self.children:
                child.update_depth()
 
     
    def update_nodetype(self):
        if self.depth == 0:
            self.nodetype = 'root'
        elif len(self.children) > 0:
            self.nodetype = 'internal node'
        else:
            self.nodetype = 'leaf'
            

     
    def __str__(self):
        parent = self.parent.node if self.parent else -1
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
            self.node, parent, self.sibling, self.degree, self.depth, self.height, self.nodetype)
     
 
tree = Trees()
 
n = int(input())
 
for i in range(n):
    a = list(map(int,input().split()))
    tree.add_nodes(a[0])
    tree.add_child(id=a[0], child_id1=a[1], child_id2=a[2])

for id in range(n):
    tree.setheight(id)
        

for id in range(n):
    print(f"{tree.nodes[id]}")