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, parent =None ,left =None ,right = None):
        self.parent = parent
        self.left = left
        self.right = right

def get_depth(u,tree_list):
    d = 0
    while tree_list[u].parent != -1:
        u = tree_list[u].parent
        d += 1
    return d


def get_sibling(i, tree_list):
    if tree_list[i].parent == -1:
        return -1
    p = tree_list[i].parent
    if tree_list[p].left != i and tree_list[p].left != -1:
        return tree_list[p].left

    if tree_list[p].right != i and tree_list[p].right != -1:
        return tree_list[p].right

    return -1

def get_higt(i, tree_list):
    h1 = 0
    h2 = 0
    if tree_list[i].left != -1:
        h1 = get_higt(tree_list[i].left, tree_list) + 1
    if tree_list[i].right != -1:
        h2 = get_higt(tree_list[i].right, tree_list) + 1

    return max(h1,h2)

if __name__ == "__main__":
    n = int(input())

    tree_list = [Node(-1,-1,-1) for m in range(n)]
    for i in range(n):
        l = input().split()
        v = int(l[0])
        c_list = [int(l[m]) for m in range(1,len(l))]
        tree_list[v].left = c_list[0]
        tree_list[v].right = c_list[1]
        if c_list[0] != -1:
            tree_list[c_list[0]].parent = v
        if c_list[1] != -1:
            tree_list[c_list[1]].parent = v

    for i,t in enumerate(tree_list):
        sibling = get_sibling(i,tree_list)
        degree = 0
        if tree_list[i].left != -1:
            degree += 1
        if tree_list[i].right != -1:
            degree += 1

        depth = get_depth(i, tree_list)
        higt = get_higt(i,tree_list)
        tree_type = ''
        if tree_list[i].parent == -1:
            tree_type = 'root'
        elif tree_list[i].left == -1 and tree_list[i].right == -1:
            tree_type = 'leaf'
        else:
            tree_type = 'internal node'

        print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
            i,t.parent,sibling,degree,depth,higt,tree_type))

Solution (Python):
n = int(input())
tree = [0] * n
root = set(range(n))
def type(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)
    h = node[6] = max(type(l, i, r, depth + 1), type(r, i, l, depth + 1)) + 1
    return h
 
while n:
    i, l, r = list(map(int, input().split()))
    tree[i] = [l, r] + [0] * 5
    root -= {l, r}
    n -= 1
type(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):
def depth(id):
    depth = 0
    target_id = id
    while nodes[target_id][0] !=-1:
        depth += 1
        target_id = nodes[target_id][0]
    return depth

def height(id):
    return 1 + max({0}.union([height(value) for value in nodes[id][1:] if value != -1]))

nodes = dict()
n = int(input())
for _ in range(n):
    id,l,r = list(map(int, input().split()))
    if id not in nodes:
        nodes[id] = (-1, -1, -1)
    node = nodes[id]
    node = (node[0], l, r)
    nodes[id] = node
    for child_id in [child_id for child_id in node[1:] if child_id != -1]:
        if child_id not in nodes:
            nodes[child_id] = (-1, -1, -1)
        child_node = nodes[child_id]
        child_node = (id, child_node[1], child_node[2])
        nodes[child_id] = child_node

for id, node in sorted(nodes.items()):
    node_type = "root" if node[0] == -1 else "internal node" if node[1] != -1 or node[2] != -1 else "leaf"
    sibling = -1 if node[0] == -1 else [value for value in nodes[node[0]][1:] if value != id][0]
    degree = len([1 for value in node[1:] if value != -1])
    print(f"node {id}: parent = {node[0]}, sibling = {sibling}, degree = {degree}, depth = {depth(id)}, height = {height(id)-1}, {node_type}")

Solution (Python):
class binarytree:
    def __init__(self, num_parts, parts):
        self.num_parts = num_parts
        self.nodes = [None]*self.num_parts
        self.root = 0
        for i in range(self.num_parts):
            self.nodes[parts[i][0]] = binarynode(parts[i][0],parts[i][1],parts[i][2])

    def set_families(self):
        for i in range(self.num_parts):
            if self.nodes[i].left != -1:
                self.nodes[self.nodes[i].left].set_parent(i)
                self.nodes[self.nodes[i].left].set_sibling(self.nodes[i].right)
            if self.nodes[i].right != -1:
                self.nodes[self.nodes[i].right].set_parent(i)
                self.nodes[self.nodes[i].right].set_sibling(self.nodes[i].left)
        for i in range(self.num_parts):
            if self.nodes[i].parent == -1:
                self.root = i
            
    def set_type(self):
        for i in range(self.num_parts):
            self.nodes[i].check_type()

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

    def set_height(self, pos, height):
        self.nodes[pos].set_height(height)
        if self.nodes[pos].parent != -1:
            self.set_height(self.nodes[pos].parent, height+1)
        return
            
class binarynode:
    def __init__(self, id, left, right):
        self.id = id
        self.parent = -1
        self.left = left
        self.right = right
        self.sibling = -1
        self.degree = 2
        self.depth = 0
        self.height = 0
        self.type = "internal node"

        if self.left == -1:
            self.degree -= 1
        if self.right == -1:
            self.degree -= 1
        
    def set_parent(self,parent):
        self.parent = parent
        return
    def set_sibling(self,sibling):
        self.sibling = sibling
        return
        
    def check_type(self):
        if self.parent == -1:
            self.type = "root"
        elif self.left == -1 and self.right == -1:
            self.type = "leaf"
        else:
            self.type = "internal node"
        return
            
    def set_depth(self,depth):
        self.depth = depth
        return
    def set_height(self,height):
        self.height = max(self.height, height)
        return
        
n = int(input())
obj = []
for i in range(n):
    obj.append(list(map(int, input().split())))

new_tree = binarytree(n, obj)
new_tree.set_families()
new_tree.set_type()
new_tree.set_depth(new_tree.root, 0)
for i in range(n):
    if new_tree.nodes[i].type == "leaf":
        new_tree.set_height(i, 0)

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

Solution (Python):
from sys import stdin
N=int(input())
nodes=[None]*N
sibling=[None]*N
dep=[0]*N
parent_list=[None]*N
degree=[0]*N
class node_tree():
    def __init__(self,node):
        self.node=node
        self.left=None
        self.right=None
        self.brother=None
        self.up=None
for i in range(N):
    node,left,right = list(map(int, (stdin.readline().strip().split())))
    if nodes[node] is not None:
        parent=nodes[node]
    else:parent=node_tree(node)
    if left!=-1:
        if nodes[left] is not None:
            left_node=nodes[left]
        else:left_node=node_tree(left)
        parent.left=left_node
        left_node.up=parent

    if right!=-1:
        if nodes[right] is not None:
            right_node=nodes[right]
        else:right_node=node_tree(right)
        parent.right=right_node
        right_node.up=parent
    if left!=-1 and right!=-1:
        left_node.brother=right_node
        right_node.brother=left_node
    if left!=-1:
        nodes[left] = left_node
    if right!=-1:
        nodes[right] = right_node
    nodes[node]=parent

def search_root(u):
    if u.up!=None:
        return search_root(u.up)
    else:
        return u.node
oya=search_root(nodes[0])

def search_depth(u,p):
    dep[u.node]=p
    if u.right is not None and u.left is not None:
        degree[u.node]=2
    elif u.left is not None:
        degree[u.node]=1
    elif u.right is not None:
        degree[u.node] = 1
    else:degree[u.node]=0

    if u.right is not None:
        parent_list[u.right.node]=u.node
        search_depth(u.right,p+1)
    if u.left is not None:
        parent_list[u.left.node]=u.node
        search_depth(u.left,p+1)
def search_height(u):
    h1,h2=0,0
    if u.right is not None:
        h1=search_height(u.right)+1
    if u.left is not None:
        h2=search_height(u.left)+1
    return max(h1,h2)

def search_sib(u):
    if u.brother is not None:
        sibling[u.node]=u.brother.node
        sibling[u.brother.node]=u.node
    if u.left is not None:
        search_sib(u.left)
    if u.right is not None:
        search_sib(u.right)
search_sib(nodes[oya])
search_depth(nodes[oya],0)
word_list=["internal node","leaf"]
for i in range(N):
    height = search_height(nodes[i])
    if height>=1:word=word_list[0]
    else:word=word_list[1]
    if i==oya:
        parent_list[oya]=-1
        sibling[oya]=-1
        word="root"
    if sibling[i] is None:sibling[i]=-1
    print(("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s" % \
           (nodes[i].node, parent_list[i],sibling[i],degree[i], dep[i], height,word)))

Solution (Python):
n=int(input())
childs=[0]*n

for i in range(n):
    node=list(map(int,input().split()))
    childs[node[0]] = node[1:]

class BisectTree:
    def __init__(self,childs):
        self.n=len(childs) 
        self.left_child=[0]*self.n
        self.right_child=[0]*self.n
        self.parent=[-1]*self.n
        for i in range(self.n):
            self.left_child[i]=childs[i][0]
            self.right_child[i]=childs[i][1]
            if childs[i][0] != -1:
                self.parent[childs[i][0]]=i
            if childs[i][1] != -1:
                self.parent[childs[i][1]]=i
        
        self.root=self.parent.index(-1)
        self.d=[0]*self.n
        self.degree=[0]*self.n
        self.sibling=[-1]*self.n
        self.node_type=[0]*self.n
        self.height=[-1]*self.n

    def set_depth(self,id,d):
        if id != -1:
            self.d[id]=d
            self.set_depth(self.left_child[id],d+1)
            self.set_depth(self.right_child[id],d+1)
    
    def set_degree(self):
        for i in range(self.n):
            deg=0
            if self.left_child[i] != -1:
                deg += 1
            if self.right_child[i] != -1:
                deg += 1
            self.degree[i]=deg
    
    def set_sibling(self):
        for i in range(self.n):
            if self.right_child[i] != -1 and self.left_child[i] != -1:
                self.sibling[self.right_child[i]]=self.left_child[i]
                self.sibling[self.left_child[i]]=self.right_child[i]
    
    def set_height(self,id):
        if self.left_child[id] == -1 and self.right_child[id] == -1:
            self.height[id]=0
        else:
            h1=self.set_height(self.left_child[id])
            h2=self.set_height(self.right_child[id])
            self.height[id]=max(h1,h2)+1
        return self.height[id]


    
    def set_node_type(self):
        for i in range(self.n):
            if self.parent[i] == -1:
                self.node_type[i]="root"
            elif self.left_child[i] == -1 and self.right_child[i] == -1:
                self.node_type[i]="leaf"
            else:
                self.node_type[i]="internal node"
    
tree = BisectTree(childs)
tree.set_sibling()
tree.set_degree()
tree.set_depth(tree.root,0)
tree.set_height(tree.root)
tree.set_node_type()

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

Solution (Python):
n = int(input())
parent = [-1]*n
depth = [0]*n
height = [0]*n
G = [[-1, -1] for _ in range(n)]
for i in range(n):
    id, *g  = map(int, input().split())
    G[id] = g
    for child in g:
        if child != -1:
            parent[child] = id

def dfs(r, d):
    if r == -1:
        return -1
    depth[r] = d
    height[r] = max(dfs(G[r][0], d + 1), dfs(G[r][1], d + 1)) + 1
    return height[r]

for i in range(n):
    if parent[i] == -1:
        dfs(i, 0)
        break

for i in range(n):
    T = ''
    if parent[i] == -1:
        T = 'root'
    elif G[i][0] == G[i][1] == -1:
        T = 'leaf'
    else:
        T = 'internal node'
    sibling = -1
    if parent[i] != -1:
        for child in G[parent[i]]:
            if child != i:
                sibling = child
    degree = (G[i][0] != -1) + (G[i][1] != -1)
    print(f'node {i}: parent = {parent[i]}, sibling = {sibling}, degree = {degree}, depth = {depth[i]}, height = {height[i]}, {T}')

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

N = int(input())
T = [Node(None, None, None) for _ in range(N)]
for t in T:
    i, left, right = map(int, input().split())
    if left != -1:
        T[i].left = left
        T[left].parent = i
    if right != -1:
        T[i].right = right
        T[right].parent = i

def get_sibling(i):
    if T[i].parent == None:
        return -1
    if i != T[T[i].parent].left and T[T[i].parent].left != None:
        return T[T[i].parent].left
    if i != T[T[i].parent].right and T[T[i].parent].right != None:
        return T[T[i].parent].right
    return -1

def get_depth(i):
    depth = 0
    while T[i].parent != None:
        depth += 1
        i = T[i].parent
    return depth

def get_height(i):
    h1, h2 = 0, 0
    if T[i].left != None:
        h1 = get_height(T[i].left) + 1
    if T[i].right != None:
        h2 = get_height(T[i].right) + 1
    return max(h1, h2)

for i, t in enumerate(T):
    print('node {}:'.format(i), end=' ')
    parent = t.parent if t.parent != None else -1
    print('parent = {},'.format(parent), end=' ')
    sibling = get_sibling(i)
    print('sibling = {},'.format(sibling), end=' ')
    degree = 0
    if t.left != None:
        degree += 1
    if t.right != None:
        degree += 1
    print('degree = {},'.format(degree), end=' ')
    depth = get_depth(i)
    print('depth = {},'.format(depth), end=' ')
    height = get_height(i)
    print('height = {},'.format(height), end=' ')
    if t.parent == None:
        node = 'root'
    elif t.left == None and t.right == None:
        node = 'leaf'
    else:
        node = 'internal node'
    print(node)

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

    def get_depth(self):
        if self.parent is None:
            return 0

        return self.parent.get_depth() + 1

    def get_height(self):
        if self.left is None and self.right is None:
            return 0
        l = 0 if self.left is None else self.left.get_height()
        r = 0 if self.right is None else self.right.get_height()

        return max(l, r) + 1

    def print(self):
        depth = self.get_depth()
        height = self.get_height()
        p = str(self.parent.value if self.parent else -1)
        s = -1
        if self.parent and self.parent.right == self and self.parent.left:
            s = self.parent.left.value
        if self.parent and self.parent.left == self and self.parent.right:
            s = self.parent.right.value
        s = str(s)
        d = bool(self.left) + bool(self.right)
        t = 'leaf'
        if self.parent is None:
            t = 'root'
        elif self.left or self.right:
            t = 'internal node'

        print('node ' + str(self.value) + ': parent = ' + p + ', sibling = ' + s + ', degree = ' + str(d) + ', depth = ' + str(depth) + ', height = ' + str(height) + ', ' + t)


n = int(input())
m = {}
for _ in range(n):
    l = list(map(int, input().split()))
    p = m[l[0]] if m.get(l[0]) else Node(l[0])
    left = None
    right = None
    if l[1] != -1:
        left = m[l[1]] if m.get(l[1]) else Node(l[1])
    if l[2] != -1:
        right = m[l[2]] if m.get(l[2]) else Node(l[2])
    if left:
        left.value = l[1]
        left.parent = p
        p.left = left
        m[left.value] = left
    if right:
        right.value = l[2]
        right.parent = p
        p.right = right
        m[right.value] = right
    m[l[0]] = p

for i in range(n):
    m[i].print()

Solution (Python):
import sys
sys.setrecursionlimit(2 ** 20)

class Node():
    def __init__(self, parent=-1, left=-1, right=-1):
        '''
        :param parent: parent node
        :param left: left child
        :param right: right child
        '''
        self.parent = parent
        self.left = left
        self.right = right

    def __repr__(self):
        return '<Node object: parent={}, left={}, right={}>' .format(self.parent, self.left, self.right)

    def get_node_type(self):
        if self.parent == -1:
            return 'root'
        elif self.left == -1 and self.right == -1:
            return 'leaf'
        else:
            return 'internal node'

    def get_degree(self):
        degree = 0
        if self.left != -1:
            degree += 1
        if self.right != -1:
            degree += 1
        return degree


def get_sibling(T, u):
    if T[u].parent == -1:
        return -1
    elif T[T[u].parent].left != u:
        return T[T[u].parent].left
    else:
        return T[T[u].parent].right

def set_depth(u, p):
    '''
    u: Node ID
    p: Initial depth
    '''
    if u == -1:
        return
    D[u] = p
    set_depth(T[u].right, p + 1)
    set_depth(T[u].left, p + 1)

def set_height(u):
    h1 = h2 = 0
    if T[u].right != -1:
        h1 = set_height(T[u].right) + 1
    if T[u].left != -1:
        h2 = set_height(T[u].left) + 1

    H[u] = max(h1, h2)
    return H[u]


n = int(input())

T = [Node() for _ in range(n)]
for i in range(n):
    idx, left, right = map(int, input().split())
    T[idx].left = left
    T[idx].right = right

    
    if left != -1:
        T[left].parent = idx
    if right != -1:
        T[right].parent = idx

D = [0] * n
H = [0] * n
for i in range(n):
    if T[i].parent == -1:
        set_depth(i, 0)
        set_height(i)
        break

for i, node in enumerate(T):
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
        i, node.parent, get_sibling(T, i), node.get_degree(), D[i], H[i], node.get_node_type())
    )

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(100000000)

NIL = -1
n = int(input())
class Node:
    def __init__(self, p, l, r, s=-1, c=0, d=0, h=0, t='nil'):
        self.p = p 
        self.l = l
        self.r = r
        self.s = s
        self.c = c
        self.d = d
        self.h = h
        self.t = t

T = [Node(NIL, NIL, NIL) for _ in range(n)]

for _ in range(n):
    data = [int(i) for i in input().split()]
    node_id = data[0]
    cl = data[1]
    cr = data[2]
    T[node_id].l = cl
    T[node_id].r = cr
    cnt_child = 0
    if cl != NIL:
        T[cl].p = node_id
        T[cl].s = cr
        cnt_child += 1
    if cr != NIL:
        T[cr].p = node_id
        T[cr].s = cl
        cnt_child += 1
    T[node_id].c = cnt_child 



def setDepth(node_id, depth):
    T[node_id].d = depth
    l = T[node_id].l
    r = T[node_id].r
    if l != NIL:
        setDepth(l, depth+1)
    if r != NIL:
        setDepth(r, depth+1)


def searchRoot():
    for i in range(n):
        if T[i].p == NIL:
            return i
    return 



def solveHeight(node_id):
    hl = 0
    hr = 0
    
    if T[node_id].l != NIL: 
        hl = solveHeight(T[node_id].l)+1
    if T[node_id].r != NIL:
        hr = solveHeight(T[node_id].r)+1
    res = max(hl, hr)
    T[node_id].h = res
    return res



def nodeType(node_id):
    if T[node_id].p == NIL:
        T[node_id].t = 'root'
        return  

    if (T[node_id].l == NIL) and (T[node_id].r == NIL):
        T[node_id].t = 'leaf'
        return 
    
    T[node_id].t = 'internal node'


def allNodeTypeDiff():
    for i in range(n):
        nodeType(i)


def nodeInfo(node_id):
    p = T[node_id].p
    s = T[node_id].s
    c = T[node_id].c
    d = T[node_id].d
    h = T[node_id].h
    t = T[node_id].t
    node_info = "node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(node_id, p, s, c, d, h, t)
    print(node_info)

def allNodeInfo():
    for i in range(n):
        nodeInfo(i)

def main():
    root = searchRoot()
    solveHeight(root)
    setDepth(root, 0)
    allNodeTypeDiff()
    allNodeInfo()
main()

Solution (Python):
class Node:
    def __init__(self):
        self.c = []
        self.p = -1
        self.sib = -1

def main():
    n = int(input())
    t = [Node() for _ in range(n)]
    for _ in range(n):
        a,b,c = map(int,input().split())
        t[a].c = [b,c]
        if b!=-1:
            t[b].p = a
            t[b].sib = c
        if c!=-1:
            t[c].p = a
            t[c].sib = b

    def depth(i):
        res = 0
        while t[i].p!=-1:
            i = t[i].p
            res+=1
        return res

    def height(i):
        res = 0
        if t[i].c[0]!=-1:res = max(res,height(t[i].c[0])+1)
        if t[i].c[1]!=-1:res = max(res,height(t[i].c[1])+1)
        return res

    for i in range(n):
        print ('node %d: parent = %d, sibling = %d, degree = %d, '%(i, t[i].p, t[i].sib, 2-t[i].c.count(-1)),end='')
        print ('depth = %d, height = %d, '%(depth(i),height(i)),end='')
        if t[i].p==-1           :print ('root')
        elif t[i].c.count(-1)==2:print ('leaf')
        else                    :print ('internal node')


if __name__ == '__main__':
    main()

Solution (Python):


class Node():
  def __init__(self, id):
    self.id = id
    self.parent = self.right = self.left = None
    self.depth = -1
    self.height = -1
    self.degree = -1
    self.sibiling = -1

class BinaryTree():
  def __init__(self, node_ids, child_info):
    self.root = None
    tmp = sorted(zip(node_ids, child_info), key=lambda x:x[0])
    node_ids = [x[0] for x in tmp]
    child_info = [x[1] for x in tmp]
    self.nodes = [Node(x) for x in node_ids]
    for n, c in zip(self.nodes, child_info):
      self.set_children(n, *c)
    self.set_root()
    self.set_depth(self.root, 0)
    self.set_height()
    self.set_sibilings()
  
  def set_root(self):
    for n in self.nodes:
      if n.parent is None:
        self.root = n
    
  def set_children(self, node, left, right):
    degree = 0
    if left != -1:
      node.left = self.nodes[left]
      node.left.parent = node
      degree += 1
    if right != -1:
      node.right = self.nodes[right]
      node.right.parent = node
      degree += 1
    node.degree = degree 

  def set_depth(self, node, d):
    node.depth = d
    if node.left is not None:
      self.set_depth(node.left, d + 1)
    if node.right is not None:
      self.set_depth(node.right, d + 1)
  
  def set_height(self):
    def get_height(n:Node):
      h1=0
      h2 = 0
      if n.left is not None:
        h1 = get_height(n.left) + 1
      if n.right is not None:
        h2 = get_height(n.right) + 1
      n.height = max(h1,h2)
      return max(h1,h2)
    get_height(self.root)
    
  
  def set_sibilings(self):
    for n in self.nodes:
      if n.parent is None:
        n.sibiling = -1
      else:
        if n.parent.right is not None and n.parent.right != n:
          n.sibiling = n.parent.right.id
        elif n.parent.left is not None and n.parent.left != n: 
          n.sibiling = n.parent.left.id
        else:
          n.sibiling = -1

def print_node(n: Node):
  if n.parent is None:
    ntype = "root"
  elif n.right is None and n.left is None:
    ntype = "leaf"
  else:
    ntype = "internal node"
  template = "node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
  parent = n.parent.id if n.parent is not None else -1
  print(template.format(n.id, parent, n.sibiling, n.degree, n.depth, n.height, ntype))


def main():
  n = int(input())
  tmp = [list(map(int, input().split())) for _ in range(n)]
  n = [x[0] for x in tmp]
  c = [x[1:] for x in tmp]
  T = BinaryTree(n,c)
  nodes = T.nodes

  for n in nodes:
    print_node(n)

if __name__ == "__main__":
  import sys, io

  main()

Solution (Python):
import sys
sys.setrecursionlimit(2**20)
n = int(input())
NIL = -1
class node:
    def __init__(self,parent,left,right,key):
        self.parent = parent
        self.left = left
        self.right = right
        self.key = key
T = [node(NIL,NIL,NIL,NIL) for _ in range(n)]
D = [0]*n
def setDepth(u,p):
    if u == NIL:
        return
    D[u] = p      
    if T[u].left != NIL:
        setDepth(T[u].left,p+1)
    if T[u].right != NIL:
        setDepth(T[u].right,p+1)
    return D
H = [0]*n
def setHeight(u,H):
    hl = 0
    hr = 0
    if T[u].left != NIL:
        hl = 1 + setHeight(T[u].left,H)
    if T[u].right != NIL:
        hr = 1 + setHeight(T[u].right,H)
    ret = max(hl,hr)
    H[u] = ret
    return ret
def getDegree(u):
    cc = 0
    if T[i].left != NIL:
        cc += 1
    if T[i].right != NIL:
        cc += 1
    return cc
def getDepth(u):
    d = 0
    while T[u].parent != NIL:
        u = T[u].parent
        d += 1
    return d
def getBrother(u):
    if T[u].parent == NIL:
        return NIL
    elif T[T[u].parent].left == u:
        return T[T[u].parent].right
    elif T[T[u].parent].right == u:
        return T[T[u].parent].left
def printChildren(u):
    child = []
    if T[u].left != NIL:
        child.append(T[u].left)
    if T[u].right != NIL:
        child.append(T[u].right)
    return child
def ppp():
	for i in range(n):
  		ccc = T[i]
  		print(i,ccc.parent,ccc.left,ccc.right)
def findroot(u): 
    while T[u].parent != NIL:
        u = T[u].parent
    return u

rl = []
def rootleft(u,rl): 
    if u == NIL:
        return
    rl.append(u)
    rootleft(T[u].left,rl)
    rootleft(T[u].right,rl)
lro = []
def leftroot(u,lro):
    if u == NIL:
        return
    leftroot(T[u].left,lro)
    lro.append(u)
    leftroot(T[u].right,lro)
lri = []
def leftright(u,lri):
    if u == NIL:
        return
    leftright(T[u].left,lri)
    leftright(T[u].right,lri)
    lri.append(u)

firstid = 0
for i in range(n):
    id,left,right = map(int,input().split())
    if n == 0:
        firstid = id
    if left != NIL:
        T[id].left = left
        T[left].parent = id
    if right != NIL:
        T[id].right = right
        T[right].parent = id
r = findroot(firstid)
D = setDepth(r,0)
setHeight(r,H)
leftright(r,lri)
leftroot(r,lro)
rootleft(r,rl)


for i in range(n):
    node = i
    parent = T[i].parent
    sibling = getBrother(i)
    degree = getDegree(i)
    depth = D[i]
    height = H[i]
    s = "internal node"
    if i == r:
        s = "root"
    elif degree == 0:
        s = "leaf"
    print(f'node {i}: parent = {parent}, sibling = {sibling}, degree = {degree}, depth = {depth}, height = {height}, {s}')

Solution (Python):
class Node:
    def __init__(self):
        self.p = -1
        self.l = -1
        self.r = -1

n = int(input())
T = [Node() for _ in range(n)]
for _ in range(n):
    i,left,right = map(int,input().split())
    T[i].l = left
    T[i].r = right
    if left != -1: T[left].p = i
    if right != -1: T[right].p = i

sib = [-1]*n
deg = [0]*n
dep = [0]*n
hei = [0]*n
ntype = ["internal node"]*n

def rec(u,d):
    dep[u] = d
    l = T[u].l
    r = T[u].r
    h1 = h2 = 0
    if l != -1:
        sib[l] = r
        deg[u] += 1
        h1 = rec(T[u].l,d+1)
    if r != -1:
        sib[r] = l
        deg[u] += 1
        h2 = rec(T[u].r,d+1)
    if deg[u] == 0:
        if ntype[u] != "root": ntype[u] = "leaf"
        hei[u] = 0
        return 1
    else:
        h = max(h1,h2)
        hei[u] = h
        return h+1

root = 0
while T[root].p != -1: root += 1
ntype[root] = "root"
rec(root,0)

for i in range(n):
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(i,T[i].p,sib[i],deg[i],dep[i],hei[i],ntype[i]))