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.



Sample input:
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:
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

Submission status: Accepted

Solution code:
# coding=utf-8
 
class Node:
    def __init__(self, ID, left, right):
        ### information for output ###
        self.id = ID
        self.parent = -1
        self.sibling = -1
        self.degree = -1
        self.depth = 0
        self.height = 0
        self.type = None
 
        ### other information ###
        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
 
    ### child information ###
    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
 
    ### self information ###
    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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
???????????¨
??????????????????????????¨ 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]
#    print("depth d:{} n:{} {}".format(d,id,n))
    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]
#        print("set n:{} {} {}".format(n[I],n,i))

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

    for id in range(num):
        n = nodes[id]
#        print("print n:{} {}".format(id,n))
        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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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 # parent, sibling, degree, depth, height
    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'
    ))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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"]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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"]))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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="")

Submission status: Accepted

Solution code:
from collections import defaultdict

def dfs(here, p, d, conn, parent, depth, height):
    parent[here] = p
    depth[here] = d
    l_d, r_d = 0, 0
    for c in conn[here]:
        if c[0] >= 0:
            l_d = dfs(c[0], here, d + 1, conn, parent, depth, height)
        if c[1] >= 0:
            r_d = dfs(c[1], here, d + 1, conn, parent, depth, height)
    if len(conn[here]):
        height[here] = max(max(l_d, r_d) - d, 0)
    return max(l_d, r_d, d)

v_num = int(input())
conn = defaultdict(list)
in_v = [0 for n in range(v_num + 1)]
degree = [0 for n in range(v_num)]
for _ in range(v_num):
    v, left, right = (int(n) for n in input().split(" "))
    conn[v].append([left, right])
    in_v[left] += 1
    in_v[right] += 1
    degree[v] += int(left >= 0) + int(right >= 0)
for i, n in enumerate(in_v):
    if not n:
        root = i
        break
parent = [-1 for n in range(v_num)]
depth = [0 for n in range(v_num)]
height = [0 for n in range(v_num)]
dfs(root, -1, 0, conn, parent, depth, height)
sibling = [-1 for n in range(v_num)]
for i in range(v_num):
    for j in range(v_num):
        if i == j:
            continue
        elif parent[i] == parent[j]:
            sibling[i] = j
            break
v_type = ["" for n in range(v_num)]
for i in range(v_num):
    if i == root:
        v_type[i] = "root"
    elif degree[i] != 0:
        v_type[i] = "internal node"
    else:
        v_type[i] = "leaf"
for i in range(v_num):
    print("node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}".format(i, parent[i], sibling[i], degree[i], depth[i], height[i], v_type[i]))

Submission status: Accepted

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

def setParentAndTypeAndSibling(tree):
    result = -1
    for i, tmp in enumerate(tree):
        if tmp.left != -1:
            tree[tmp.left].parent = i
        if tmp.right != -1:
            tree[tmp.right].parent = i

    for i, tmp in enumerate(tree):
        if tmp.parent == -1:
            tmp.type = 'root'
            result = i
        elif tmp.left == -1 and tmp.right == -1:
            tmp.type = 'leaf'
        else:
            tmp.type = 'internal node'

        if tmp.left == -1 and tmp.right == -1:
            tmp.degree = 0
        elif tmp.left != -1 and tmp.right != -1:
            tmp.degree = 2
            tree[tmp.left].sibling = tmp.right
            tree[tmp.right].sibling = tmp.left
        else:
            tmp.degree = 1
    return result

def setdepth(tree,i,d):
    tree[i].depth = d
    if tree[i].left != -1:
        setdepth(tree,tree[i].left,d+1)
    if tree[i].right != -1:
        setdepth(tree,tree[i].right,d+1)
    return

def findParentAndsetHeight(tree,i,h):
    tree[i].height = max(h,tree[i].height)
    if tree[i].parent != -1:
        findParentAndsetHeight(tree,tree[i].parent,h+1)
    return

def setHeight(tree):
    for tmp in tree:
        if tmp.type == 'leaf':
            tmp.height = 0
            findParentAndsetHeight(tree,tmp.parent,1)

if __name__ == '__main__':
    n = int(input())
    tree = [None]*n

    for i in range(0,n):
        tmp = list(map(int,input().split()))
        tree[tmp[0]] = Node(tmp[1],tmp[2])
    
    root = setParentAndTypeAndSibling(tree)
    setdepth(tree,root,0)
    setHeight(tree)
    for i, tmp in enumerate(tree):
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(i,tmp.parent,tmp.sibling,tmp.degree,tmp.depth,tmp.height,tmp.type))