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, ID, left, right):
        
        self.id = ID
        self.parent = -1 
        self.sibling = -1 
        self.degree = -1 
        self.depth = 0 
        self.height = 0 
        self.type = None 
 
        
        self.left_child = left
        self.right_child = right
 
def calc_depth(i):
    global node_list
 
    if node_list[i].depth != 0:
        return node_list[i].depth
 
    depth = 0
    if node_list[i].parent != -1:
        depth = calc_depth(node_list[i].parent) + 1
 
    node_list[i].depth = depth
    return depth
 
 
def calc_height(i):
    global node_list
 
    if node_list[i].height != 0:
        return node_list[i].height
 
    h1 = h2 = 0
    if node_list[i].right_child != -1:
        h1 = calc_height(node_list[i].right_child) + 1
    if node_list[i].left_child != -1:
        h2 = calc_height(node_list[i].left_child) + 1
 
    height = max(h1, h2)
    node_list[i].height = height
    return height
 
n = int(input())
data = [tuple(map(int, input().split())) for x in range(n)]
node_list = []
 
for data_row in data:
    ID, left, right = data_row
    node = Node(ID, left, right)
    node_list.append(node)
 
node_list.sort(key = lambda node: node.id)
 
for i, node in enumerate(node_list):
    left = node.left_child
    right = node.right_child
    degree = 0
 
    
    if left != -1:
        degree += 1
        node_list[left].parent = i
        node_list[left].sibling = right
 
    if right != -1:
        degree += 1
        node_list[right].parent = i
        node_list[right].sibling = left
 
    
    node.degree = degree
 
for i in range(n):
    calc_depth(i)
    calc_height(i)
 
    node = node_list[i]
 
    if node.depth == 0:
        node.type = 'root'
    elif node.height == 0:
        node.type = 'leaf'
    else:
        node.type = 'internal node'
 
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(node.id, node.parent, node.sibling, node.degree, node.depth, node.height, node.type))

Solution (Python):

 
class Node:
    def __init__(self, ID, left, right):
        
        self.id = ID
        self.parent = -1
        self.sibling = -1
        self.degree = -1
        self.depth = 0
        self.height = 0
        self.type = None
 
        
        self.left_child = left
        self.right_child = right
 
def calc_depth(i):
    global node_list
 
    if node_list[i].depth != 0:
        return node_list[i].depth
 
    depth = 0
    if node_list[i].parent != -1:
        depth = calc_depth(node_list[i].parent) + 1
 
    node_list[i].depth = depth
    return depth
 
 
def calc_height(i):
    global node_list
 
    if node_list[i].height != 0:
        return node_list[i].height
 
    h1 = h2 = 0
    if node_list[i].right_child != -1:
        h1 = calc_height(node_list[i].right_child) + 1
    if node_list[i].left_child != -1:
        h2 = calc_height(node_list[i].left_child) + 1
 
    height = max(h1, h2)
    node_list[i].height = height
    return height
 
n = int(input())
data = [tuple(map(int, input().split())) for x in range(n)]
node_list = []
 
for data_row in data:
    ID, left, right = data_row
    node = Node(ID, left, right)
    node_list.append(node)
 
node_list.sort(key = lambda node: node.id)
 
for i, node in enumerate(node_list):
    left = node.left_child
    right = node.right_child
    degree = 0
 
    
    if left != -1:
        degree += 1
        node_list[left].parent = i
        node_list[left].sibling = right
 
    if right != -1:
        degree += 1
        node_list[right].parent = i
        node_list[right].sibling = left
 
    
    node.degree = degree
 
for i in range(n):
    calc_depth(i)
    calc_height(i)
 
    node = node_list[i]
 
    if node.depth == 0:
        node.type = 'root'
    elif node.height == 0:
        node.type = 'leaf'
    else:
        node.type = 'internal node'
 
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(node.id, node.parent, node.sibling, node.degree, node.depth, node.height, node.type))

Solution (Python):

 
class Node:
    def __init__(self, ID, left, right):
        
        self.id = ID
        self.parent = -1
        self.sibling = -1
        self.degree = -1
        self.depth = 0
        self.height = 0
        self.type = None
 
        
        self.left_child = left
        self.right_child = right
 
def calc_depth(i):
    global node_list
 
    if node_list[i].depth != 0:
        return node_list[i].depth
 
    depth = 0
    if node_list[i].parent != -1:
        depth = calc_depth(node_list[i].parent) + 1
 
    node_list[i].depth = depth
    return depth
 
 
def calc_height(i):
    global node_list
 
    if node_list[i].height != 0:
        return node_list[i].height
 
    h1 = h2 = 0
    if node_list[i].right_child != -1:
        h1 = calc_height(node_list[i].right_child) + 1
    if node_list[i].left_child != -1:
        h2 = calc_height(node_list[i].left_child) + 1
 
    height = max(h1, h2)
    node_list[i].height = height
    return height
 
n = int(input())
data = [tuple(map(int, input().split())) for x in range(n)]
node_list = []
 
for data_row in data:
    ID, left, right = data_row
    node = Node(ID, left, right)
    node_list.append(node)
 
node_list.sort(key = lambda node: node.id)
 
for i, node in enumerate(node_list):
    left = node.left_child
    right = node.right_child
    degree = 0
 
    
    if left != -1:
        degree += 1
        node_list[left].parent = i
        node_list[left].sibling = right
 
    if right != -1:
        degree += 1
        node_list[right].parent = i
        node_list[right].sibling = left
 
    
    node.degree = degree
 
for i in range(n):
    calc_depth(i)
    calc_height(i)
 
    node = node_list[i]
 
    if node.depth == 0:
        node.type = 'root'
    elif node.height == 0:
        node.type = 'leaf'
    else:
        node.type = 'internal node'
 
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(node.id, node.parent, node.sibling, node.degree, node.depth, node.height, node.type))

Solution (Python):
def main():
    n = input()
    tree = MyTree(n)
    for i in range(n):
        id_cn = map(int,raw_input().split())
        id_node = id_cn.pop(0)
        
        tree.add(id_node,None,id_cn)
    
    tree.search_children()
    tree.set_depth_height(tree.nodes[tree.id_root],0)
        
    for node in tree.nodes:
        print "node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}".format(
            node.id_self, node.id_parent, node.sibling, node.degree, node.depth, node.height, node.node_type)


class MyTree():
    def __init__(self,num_nodes):
        self.nodes = [MyNode() for i in range(num_nodes)]
        self.id_root = None

    def add(self,id_node,id_parent,id_children):
        node = self.nodes[id_node]
        node.id_self = id_node
        node.id_parent = id_parent
        node.id_children = id_children
    
    def search_children(self):
        for node in self.nodes:
            if all(item==-1 for item in node.id_children):
                node.node_type = "leaf"
                node.degree = 0
            else:
                node.node_type = "internal node"
                l = node.id_children[0]
                r = node.id_children[1]
                if l == -1:
                    node.degree = 1
                    self.nodes[r].id_parent = node.id_self
                    self.nodes[r].sibling = l
                elif r == -1:
                    node.degree = 1
                    self.nodes[l].id_parent = node.id_self
                    self.nodes[l].sibling = r
                else:
                    node.degree = 2
                    self.nodes[l].id_parent = node.id_self
                    self.nodes[r].id_parent = node.id_self
                    self.nodes[l].sibling = r
                    self.nodes[r].sibling = l

        for node in self.nodes:
            if node.id_parent == None:
                node.id_parent = -1
                node.node_type = "root"
                self.id_root = node.id_self
                break

    def set_depth_height(self,node,depth):
        node.depth = depth
        l_height = []
        if all(item==-1 for item in node.id_children):
            node.height = 0
            return 0
        else:
            for item in node.id_children:
                if not item == -1:
                    l_height.append(self.set_depth_height(self.nodes[item],depth+1))
            height = max(l_height)+1
            node.height = height
            return height
                


class MyNode():
    def __init__(self):
        self.id_self = None
        self.id_parent = None
        self.id_children = None
        self.depth = None
        self.node_type = None
        self.n_children = 0
        self.sibling = -1
        self.degree = 0
        self.height = 0


if __name__ == "__main__":
    main()

Solution (Python):
import sys


def dep(u, p):
    depth[u] = p
    if TREE[u][1] != NIL:
        dep(TREE[u][1], p+1)
    if TREE[u][2] != NIL:
        dep(TREE[u][2], p+1)


def hei(u):
    h1, h2 = 0, 0
    if TREE[u][1] != NIL:
        h1 = hei(TREE[u][1]) + 1
    if TREE[u][2] != NIL:
        h2 = hei(TREE[u][2]) + 1
    height[u] = max(h1, h2)
    return height[u]


def print_ans():
    for i in range(n):
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
              .format(i, TREE[i][0], TREE[i][3],
                      2 if TREE[i][1] != -1 and TREE[i][2] != -1 else 0 if TREE[i][1] == NIL and TREE[i][2] == NIL else 1,
                      depth[i], height[i],
                      "root" if TREE[i][0] == NIL else "leaf" if TREE[i][1] == NIL and TREE[i][2] == NIL else "internal node"))


if __name__ == "__main__":
    n = int(sys.stdin.readline())
    NIL = -1
    TREE = [[NIL, NIL, NIL, NIL] for i in range(n)]
    depth = [-1 for i in range(n)]
    height = [-1 for i in range(n)]
    root = set(range(n))
    for inp in sys.stdin.readlines():
        inp = list(map(int, inp.split()))
        if inp[1] != -1:
            TREE[inp[0]][1] = inp[1]
            TREE[inp[1]][0] = inp[0]
            TREE[inp[1]][3] = inp[2]
        if inp[2] != -1:
            TREE[inp[0]][2] = inp[2]
            TREE[inp[2]][0] = inp[0]
            TREE[inp[2]][3] = inp[1]
        root -= set([inp[1], inp[2]])
    a = root.pop()
    dep(a, 0)
    hei(a)
    print_ans()

Solution (Python):
class Node():

    def __init__(self, node_id, left, right):
        self.node_id = node_id
        self.parent = -1
        self.sibling = -1
        self.left = left
        self.right = right
        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 = [0] * n
root = set(range(n))

for i 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):


"""
???????????¨
??????????????????????????¨ T ???????????? u ???????????????
??\???????????±???????????????????????°????????????????????????????????????

u ???????????????
u ?????????????????????
u ?????±???
u ?????????????¨??????????????????¨?????????????????????
u ??????????????????
????????§???????????????????????¨??? n ????????????????????????
???????????? 0 ?????? n???1 ???????????????????????????????????????????????¨????????????

??\???
??\??????????????????????????????????????° n ????????????????????????
?¶???? n ?????????????????????????????±????¬??????¢?????§??????????????????????????????

id k c1 c2 ... ck

id ?????????????????????k ????¬???°?????¨????????????c1 c2 ...ck ???
 1 ??????????????????????????????... kk ?????????????????????????????????????????????

??????
?¬??????¢?????§??????????????±??????????????????????????????
??????????????±???????????????????°????????????????????????????????????????

node id: parent = p , depth = d, type, [c1...ck]

p ?????????????????????????????????????????????????????????????????´?????? -1 ??¨????????????
d ??????????????±?????????????????????

type??????????????¨??????????????????????????????????????? root???internal node???leaf ?????????????????????????????§??????
?????????????????????????????¨??????????????¶?????????????????´?????? root ??¨????????????

c1...ck ????????????????????§??????
????????¨??¨???????????\?????????????????????????????????????????????
?????????????????????????????¨???????????????????????????????????????????????¢???????¢?????????????????????????

"""
import sys

I = 0
L = 1
R = 2
P = 3
B = 4
D = 5
H = 6

def setd(A, id, d):
    n = A[id]

    n[D] = d
    ld = 0
    rd = 0
    if n[L] > -1:
       ld = setd(A, n[L], d + 1) + 1
    if n[R] > -1:
       rd = setd(A, n[R], d + 1) + 1
    if ld > rd:
        n[H] = ld
    else:
        n[H] = rd
    return n[H]

def getroot(A, id):
    if A[id][P] > -1:
        return getroot(A,A[id][P])
    return A[id][I]

def main():

    """ ????????? """
    num = int(input().strip())
    istr = sys.stdin.read()
    nlist = list(istr.splitlines())
    
    nodes = [[i, -1, -1, -1, -1, 0, 0] for i in range(num)]

    for nstr in nlist:
        i = list(map(int,nstr.split()))
        n = nodes[i[I]]
        n[I] = i[I]
        if i[L] > -1:
            n[L] = i[L]
            nodes[n[L]][P] = i[I]
            nodes[n[L]][B] = i[R]
        if i[R] > -1:
            n[R] = i[R]
            nodes[n[R]][P] = i[I]
            nodes[n[R]][B] = i[L]


    r = getroot(nodes, 0)
    setd(nodes,r, 0)

    for id in range(num):
        n = nodes[id]

        type = "leaf"
        children = ""
        cnum = 0

        if n[L] > -1:
            type = "internal node"
            cnum += 1

        if n[R] > -1:
            type = "internal node"
            cnum += 1

        if n[P] == -1:
            type = "root"

        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(n[I], n[P], n[B], cnum, n[D], n[H], type))

if __name__ == '__main__':
    main()

Solution (Python):
class Node():
    def __init__(self, id, left, right, parent=-1, sibling=-1, degree=-1, depth=-1, height=-1, type=None):
        self.id = id
        self.left = left
        self.right = right
        self.parent = parent
        self.sibling = sibling
        self.degree = degree
        self.depth = depth
        self.height = height
        self.type = type
    def show(self):
        print 'node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s' % (self.id, self.parent, self.sibling, self.degree, self.depth, self.height, self.type)

def hasChild(x):
    if x == -1:
        return 0
    else:
        return 1

def calcDepth(node):
    if node.parent == -1:
        return 0
    return 1 + calcDepth(a[node.parent])

def calcHeight(node):
    if node.degree == 0:
        return 0
    return 1 + max(calcHeight(a[node.left]), calcHeight(a[node.right]))

n = int(raw_input())
a = []
dict = {}
for i in range(n):
    tmp = map(int, raw_input().split())
    if tmp[1] == -1 and tmp[2] == -1:
        dict[tmp[0]] = Node(tmp[0], tmp[1], tmp[2], degree=0)
    else:
        dict[tmp[0]] = Node(tmp[0], tmp[1], tmp[2], degree=hasChild(tmp[1])+hasChild(tmp[2]))

for i in range(n):
    a.append(dict[i])

for i in range(n):
    if a[i].right != -1:
        a[a[i].right].parent = a[i].id
    if a[i].left != -1:
        a[a[i].left].parent = a[i].id

for i in range(n):
    a[i].depth = calcDepth(a[i])
    a[i].height = calcHeight(a[i])
        
for i in range(n):
    if a[i].parent != -1 and a[i].degree != 0:
        a[i].type = 'internal node'
    elif a[i].parent != -1 and a[i].degree == 0:
        a[i].type = 'leaf'
    else:
        a[i].type = 'root'
        
    for j in range(n):
        if i == j:
            continue
        if a[i].depth == a[j].depth and a[i].parent == a[j].parent:
            a[i].sibling = j
        
for el in a:
    el.show()

Solution (Python):
N = int(input())
tree = [None] * N
root = set(range(N))

def set_pd(i, parent, sibling, depth):
    if i == -1:
        return -1
    node = tree[i]
    l, r = node[0], node[1]
    
    node[2], node[3], node[5] = parent, sibling, depth
    node[4] = (l != -1) + (r != -1)
    height = node[6] = max(set_pd(l, i, r, depth + 1), set_pd(r, i, l, depth + 1)) + 1
    return height

while N:
    i, l, r = list(map(int, input().split()))
    tree[i] = [l,r] + [None] * 5 
    root -= {l, r}
    N -= 1

set_pd(root.pop(), -1, -1, 0)

for i, node in enumerate(tree):
    l, r, p, s, deg, dep, h = node
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
        i, p, s, deg, dep, h, 'root' if not dep else 'internal node' if deg else 'leaf'
    ))

Solution (Python):

N = int(input())
tree = {n:{"height":0} for n in range(N)}
parent = set([n for n in range(N)])

for n in range(N):
    inp = [int(n) for n in input().split()]
    tree[inp[0]]["children"] = [m for m in inp[1:] if m!=-1]
    parent = parent.difference(inp[1:])

generation = [parent.pop()]
tree[generation[0]]["parent"] = -1
tree[generation[0]]["depth"] = 0
tree[generation[0]]["sibling"] = -1
tree[generation[0]]["type"] = "root"
tree[generation[0]]["degree"] = len(tree[generation[0]]["children"])

checked = set(generation)
leaves = set()

depth = 1
while len(checked) < N:
    new_generation = []
    for g in generation:
        for c in tree[g]["children"]:
            tree[c]["parent"] = g
            tree[c]["sibling"] = set(tree[g]["children"]).difference([c]).pop() if len(tree[g]["children"]) == 2 else -1
            tree[c]["depth"] = depth
            tree[c]["type"] = "leaf" if len(tree[c]["children"]) == 0 else "internal node"
            if not len(tree[c]["children"]):
                leaves.add(c)            
            tree[c]["degree"] = len(tree[c]["children"])
            new_generation.append(c)
            
            
    checked.update(generation)
    last_generation = generation
    generation = new_generation
    depth += 1

checked = set()            
parents = set()
height = 0
while len(leaves):
    old_leaves = set()
    for l in leaves:
        tree[l]["height"] = max(height, tree[l]["height"])
        if tree[l]["parent"] != -1:
            old_leaves.add(tree[l]["parent"])
    checked.update(leaves)
    leaves = old_leaves
    height += 1
    
for n in range(N):
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"\
          .format(n, tree[n]["parent"], tree[n]["sibling"], tree[n]["degree"], tree[n]["depth"], tree[n]["height"], tree[n]["type"]))

Solution (Python):

N = int(input())
tree = [{"parent":-1, "left":-1, "right":-1, "sibling": -1} for _ in range(N)]
parent = set([n for n in range(N)])

for _ in range(N):
    inp = [int(n) for n in input().split()]
    tree[inp[0]]["left"] = inp[1]
    tree[inp[0]]["right"] = inp[2]
    tree[inp[0]]["degree"] = sum([inp[1] != -1, inp[2] != -1])
    
    if inp[1] != -1:
        tree[inp[1]]["parent"] = inp[0]
        tree[inp[1]]["sibling"] = inp[2]
    if inp[2] != -1:
        tree[inp[2]]["parent"] = inp[0]    
        tree[inp[2]]["sibling"] = inp[1]
    
    parent = parent.difference(inp[1:])
    
def set_depth(n, depth):
    tree[n]["depth"] = depth
    
    if tree[n]["left"] != -1:
        set_depth(tree[n]["left"], depth+1)
    if tree[n]["right"] != -1:
        set_depth(tree[n]["right"], depth+1)

root = parent.pop()
set_depth(root, 0)

def set_height(n):
    h1 = 0
    h2 = 0
    if tree[n]["right"] != -1:
        h1 = set_height(tree[n]["right"]) + 1
    if tree[n]["left"] != -1:
        h2 = set_height(tree[n]["left"]) + 1
    
    tree[n]["height"] = max(h1, h2)
    return max(h1, h2)

set_height(root)

for n in range(N):
    if tree[n]["parent"] == -1:
        tree[n]["type"] = "root"
    elif tree[n]["degree"] == 0:
        tree[n]["type"] = "leaf"
    else:
        tree[n]["type"] = "internal node"
    
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"\
          .format(n, tree[n]["parent"], tree[n]["sibling"],
                  tree[n]["degree"], tree[n]["depth"], tree[n]["height"], tree[n]["type"]))

Solution (Python):
def binarytrees():
    def set_depth(node_id):
        if tree[node_id]['parent'] == -1:
            return 0
        else:
            return set_depth(tree[node_id]['parent']) + 1

    def set_height(node_id):
        if not tree[node_id]['degree']:
            return 0
        else:
            return max(set_height(tree[node_id]['children'][0]),
                set_height(tree[node_id]['children'][1])) + 1

    n = int(input())

    tree = [{'parent': -1, 'sibling': -1, 'degree': 0, 'depth': 0, 'height': 0,
             'node_type': 'leaf', 'children': []} for i in range(n)]

    for i in range(n):
        line = list(map(int, input().split()))
        node_id = line[0]
        child1 = line[1]
        child2 = line[2]

        for child in [child1, child2]:
            if child != -1:
                tree[node_id]['children'] = line[1:]
                tree[child]['parent'] = node_id
                tree[node_id]['degree'] += 1

        if (child1 != -1) and (child2 != -1):
            tree[child1]['sibling'] = child2
            tree[child2]['sibling'] = child1

        if tree[node_id]['degree']:
            tree[node_id]['node_type'] = 'internal node'

    for node_id in range(n):
        tree[node_id]['depth'] = set_depth(node_id)
        tree[node_id]['height'] = set_height(node_id)

        if tree[node_id]['parent'] == -1:
            tree[node_id]['node_type'] = 'root'

    for node_id in range(n):
        parent = tree[node_id]['parent']
        sibling = tree[node_id]['sibling']
        degree = tree[node_id]['degree']
        depth = tree[node_id]['depth']
        height = tree[node_id]['height']
        node_type = tree[node_id]['node_type']

        print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'
            .format(node_id, parent, sibling, degree, depth, height, node_type))

if __name__ == '__main__':
    binarytrees()

Solution (Python):
class Node:
    def __init__(self, node_id, left_child, right_child):
        self.node_id = node_id
        self.parent = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.node_type = ''

        self.left_child = left_child
        self.right_child = right_child
        

def binarytrees():
    def input_node_list():
        n = int(input())

        for i in range(n):
            node_id, left_child, right_child = list(map(int, input().split()))

            node = Node(node_id, left_child, right_child)
            node_list.append(node)

        node_list.sort(key = lambda node: node.node_id)

    def calc_parent_sibling_degree():
        if node.left_child != -1:
            node_list[node.left_child].parent = node.node_id
            node_list[node.left_child].sibling = node.right_child
            node.degree += 1

        if node.right_child != -1:
            node_list[node.right_child].parent = node.node_id
            node_list[node.right_child].sibling = node.left_child
            node.degree += 1

    def calc_depth(node_id):
        if  node_list[node_id].parent == -1:
            return 0
        else:
            return calc_depth(node_list[node_id].parent) + 1

    def calc_height(node_id):
        if not node_list[node_id].degree:
            return 0
        else:
            return max(calc_height(node_list[node_id].left_child),
                calc_height(node_list[node_id].right_child)) + 1

    def calc_node_type():
        if node.depth == 0:
            node.node_type = 'root'
        elif node.height == 0:
            node.node_type = 'leaf'
        else:
            node.node_type = 'internal node'

    def show_node_info():
        print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'
            .format(node.node_id, node.parent, node.sibling,
            node.degree, node.depth, node.height, node.node_type))

    node_list = []
    input_node_list()

    for node in node_list:
        calc_parent_sibling_degree()

    for node in node_list:
        node.depth = calc_depth(node.node_id)
        node.height = calc_height(node.node_id)

        calc_node_type()

        show_node_info()


if __name__ == '__main__':
    binarytrees()

Solution (Python):
class Node:
    def __init__(self, node_id, left_child, right_child):
        self.node_id = node_id
        self.parent = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.node_type = ''

        self.left_child = left_child
        self.right_child = right_child
        

def binarytrees():
    def input_node_list():
        n = int(input())

        for i in range(n):
            node_id, left_child, right_child = list(map(int, input().split()))

            node = Node(node_id, left_child, right_child)
            node_list.append(node)

        node_list.sort(key = lambda node: node.node_id)

    def calc_parent_sibling_degree():
        if node.left_child != -1:
            node_list[node.left_child].parent = node.node_id
            node_list[node.left_child].sibling = node.right_child
            node.degree += 1

        if node.right_child != -1:
            node_list[node.right_child].parent = node.node_id
            node_list[node.right_child].sibling = node.left_child
            node.degree += 1

    def calc_depth(node_id):
        if  node_list[node_id].parent == -1:
            return 0
        else:
            return calc_depth(node_list[node_id].parent) + 1

    def calc_height(node_id):
        if not node_list[node_id].degree:
            return 0
        else:
            return max(calc_height(node_list[node_id].left_child),
                calc_height(node_list[node_id].right_child)) + 1

    def calc_node_type():
        if node.depth == 0:
            node.node_type = 'root'
        elif node.height == 0:
            node.node_type = 'leaf'
        else:
            node.node_type = 'internal node'

    def show_node_info():
        print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'
            .format(node.node_id, node.parent, node.sibling,
            node.degree, node.depth, node.height, node.node_type))

    node_list = []
    input_node_list()

    for node in node_list:
        calc_parent_sibling_degree()

    for node in node_list:
        node.depth = calc_depth(node.node_id)
        node.height = calc_height(node.node_id)

        calc_node_type()

        show_node_info()


if __name__ == '__main__':
    binarytrees()

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

    def set_prop(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.typ    =   "internal node"
        if self.parent == -1:
            self.typ    =   "root"
        self.height     =   max(tree[self.left].set_prop(self.left, self.node_id, self.right, self.depth + 1), 
                                tree[self.right].set_prop(self.right, self.node_id, self.left, self.depth + 1)) + 1
        return self.height

n = int(input())
tree = [None for i in range(n)]
root = set(range(n))

for i in range(n):
    node_id, left, right = map(int, input().split())
    tree[node_id] = Node(node_id, left, right)
    root -= set([left, right])
r = root.pop()
tree[r].set_prop(r, -1, -1, 0)

for i in range(n):
    a = tree[i]
    print("node ", a.node_id, ": parent = ", a.parent, ", sibling = ", a.sibling,
          ", degree = ", a.degree, ", depth = ", a.depth, ", height = ", a.height, ", ", a.typ, sep="")