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, value):
        self.value = value
        self.deep = -1
        self.parent = None
        self.left = -1
        self.right = -1
        self.height = -1
        self.sib = -1

def setdeep(tree, i, deep):
    tree[i].deep = deep
    if tree[i].left != -1:
        setdeep(tree, tree[i].left, deep + 1)
    if tree[i].right != -1:
        setdeep(tree, tree[i].right, deep + 1)

def setheight(tree, i):
    if tree[i].height != -1:
        pass
    elif tree[i].left == -1 and tree[i].right == -1:
        tree[i].height = 0
    elif tree[i].left == -1:
        tree[i].height = setheight(tree, tree[i].right)
    elif tree[i].right == -1:
        tree[i].height = setheight(tree, tree[i].left)
    else:
        tree[i].height = max(setheight(tree, tree[i].right), setheight(tree, tree[i].left))
    return tree[i].height + 1

if __name__ == '__main__':
    n = int(input())
    tree = {}

    for _ in range(n):
        datas = [int(num) for num in input().split(' ')]
        nodeid = datas[0]
        if nodeid not in tree.keys():
            tree[nodeid] = Node(nodeid)
        tree[nodeid].left = left = int(datas[1])
        tree[nodeid].right = right = int(datas[2])
        if left != -1:
            if left not in tree.keys():
                tree[left] = Node(left)
            tree[left].parent = nodeid
            tree[left].sib = right
        if right != -1:
            if right not in tree.keys():
                tree[right] = Node(right)
            tree[right].parent = nodeid
            tree[right].sib = left

    for i in range(n):
        curnode = tree[i]
        if curnode.parent is None:
            
            setdeep(tree, i, 0)
            setheight(tree, i)
            break
            
    for i in range(n):
        curnode = tree[i]
        deg = 0
        if curnode.left == -1 and curnode.right == -1:
            nodetype = 'leaf'
            deg = 0
        else:
            if curnode.left != -1:
                deg += 1
            if curnode.right != -1:
                deg += 1
            nodetype = 'internal node'
        if curnode.parent == None:
            nodetype = 'root'
            parent = -1
        else:
            parent = curnode.parent
        print('node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s' \
            % (i, parent,curnode.sib, deg,  curnode.deep, curnode.height, nodetype) )

Solution (Python):

N = int(input())
answer1= []

def get_parent(node):
    parent = -1
    if "parent" in node:
        return node["parent"]
    return parent

def get_depth(node):
    depth = 0
    while "parent" in node:
        depth += 1
        parent = node["parent"]
        node = rooted_tree[parent]
    return depth

def get_node_type(node):
    if "parent" not in node:
        return "root"
    if node["left"] == -1 and node["right"] == -1:
        return "leaf"
    return "internal node"

def get_sibling(id, node):
    sibling = -1
    if "parent" not in node:
        return sibling
    parent_rchild= rooted_tree[node["parent"]]["right"]
    parent_lchild= rooted_tree[node["parent"]]["left"]
    if id == parent_rchild:
        sibling = parent_lchild
    else:
        sibling = parent_rchild
    return sibling

def get_degree(node):
    degree = 0
    if node["left"] > -1:
        degree += 1
    if node["right"] > -1:
        degree += 1        
    return degree

def get_height(node):
    h1 = h2 = 0
    if node["right"] > -1:
        h1 = get_height(rooted_tree[node["right"]]) + 1
    if node["left"] > -1:
        h2 = get_height(rooted_tree[node["left"]]) + 1
    h =  max(h1, h2)
    return h

rooted_tree = [{} for i in range(N)]
for _ in range(N):
    row = input()
    id, left, right = list(map(int, row.split()))
    rooted_tree[id]["right"] = right
    rooted_tree[id]["left"] = left
    
    if left > -1:
        left_child_id = left
        rooted_tree[left_child_id]["parent"] = id
    if right > -1:
        right_child_id = right
        rooted_tree[right_child_id]["parent"] = id

for id in range(N):
    node = rooted_tree[id]
    parent = get_parent(node)
    sibling = get_sibling(id, node)
    degree = get_degree(node)
    depth = get_depth(node)
    height = get_height(node)
    node_type = get_node_type(node)
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(id, parent, sibling, degree, depth, height, node_type))

Solution (Python):
def binary(node,parent,sibling,depth,root):
    if node!=-1:
        id,left,right=A[node]
        degree = len([i for i in (right, left) if i != -1])
        if parent==-1:root="root"
        elif degree!=0:root="internal node"
        else:root="leaf"
        B.append([node,parent,sibling,degree,depth,root])
        binary(left,node,right,depth+1,root)
        binary(right,node,left,depth+1,root)


def setHight(H,u):
    h1,h2=0,0
    if A[u][2]!=-1:
        h1=setHight(H,A[u][2])+1
    if A[u][1]!=-1:
        h2=setHight(H,A[u][1])+1
    H[u]=max(h1,h2)
    return H[u]


n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
B,H=[],[0]*n
top=[i for i in range(n)]
for i in range(n):
    for j in (A[i][1],A[i][2]):
        if j!=-1:top.remove(j)
top=top[0]
A=sorted(A)
binary(top,-1,-1,0,"root")
setHight(H,top)
for j,i in enumerate(sorted(B)):
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
          .format(i[0],i[1],i[2],i[3],i[4],H[j],i[5]))

Solution (Python):
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u, d=0):
        dep[u] = d
        h = 0
        for cu in chi[u]:
            h = max(h, dfs(cu, d + 1) + 1)
        hig[u] = h
        return h

    n = int(input())
    par = [-1] * n
    sib = [-1] * n
    deg = [0] * n
    dep = [-1] * n
    hig = [-1] * n
    typ = ["internal node"] * n
    chi = [[] for _ in range(n)]
    for _ in range(n):
        u, l, r = map(int, input().split())
        if l != -1:
            par[l] = u
            sib[l] = r
            deg[u] = 1
            chi[u] = [l]
        if r != -1:
            par[r] = u
            sib[r] = l
            deg[u] += 1
            chi[u] += [r]
        if deg[u] == 0:
            typ[u] = "leaf"
    root = par.index(-1)
    typ[root] = "root"
    dfs(root)
    for u in range(n):
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format
              (u, par[u], sib[u], deg[u], dep[u], hig[u], typ[u]))

main()

Solution (Python):

class Node:
  def __init__(self, id):
    self.id = id
    self.parent = None
    self.left = None
    self.right = None

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

  def get_children(self):
    return list(filter(None, [self.left, self.right]))

  def get_sibling(self):
    parent = self.parent
    if parent == None:
      return -1
    children = parent.get_children()
    if len(children) == 1:
      return -1
    return list(filter(lambda x: x != self, children))[0].id

  def get_depth(self):
    count = 0
    tmp = self
    while tmp.parent:
      count += 1
      tmp = tmp.parent
    return count
    
  def get_height(self):
    l, r = 0, 0
    if self.left != None:
      l = self.left.get_height() + 1
    if self.right != None:
      r = self.right.get_height() + 1
    return max(l, r)
  
  def get_type(self):
    if self.parent == None:
      return "root"
    if len(self.get_children()) == 0:
      return "leaf"
    return "internal node"


num = int(input())
nodes = [None] * num
children = []

for i in range(num):
  id, left, right = map(int, input().split())
  n = nodes[id] if nodes[id] else Node(id)
  nodes[id] = n

  if left != -1:
    if nodes[left] == None:
      l = Node(left)
      l.parent = n
      nodes[left] = l
      n.left = l
    else:
      nodes[left].parent = n
      n.left = nodes[left]

  if right != -1:
    if nodes[right] == None:
      r = Node(right)
      r.parent = n
      nodes[right] = r
      n.right = r
    else:
      nodes[right].parent = n
      n.right = nodes[right]
    

for i in range(num):
  node = nodes[i]
  print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(node.id, node.get_parent(), node.get_sibling(), len(node.get_children()), node.get_depth(), node.get_height(), node.get_type()))

Solution (Python):

class Node:
    id = None
    parent = None
    left = None
    right = None
    sibling = -1
    depth = None
    height = None

    def __str__(self):
        degree = None
        _type = None

        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(self.id, self.parent, self.sibling, self.get_degree(), self.depth, self.height, self.get_type())

    def get_degree(self):
        degree = 0
        if self.left is not None:
            degree += 1
        if self.right is not None:
            degree += 1
        return degree

    def get_type(self):
        if self.parent == -1:
            return 'root'
        if self.get_degree() == 0:
            return 'leaf'
        else:
            return 'internal node'


def set_depth(node_id, depth):
    if node_id is None:
        return

    global T
    T[node_id].depth = depth
    set_depth(T[node_id].left, depth + 1)
    set_depth(T[node_id].right, depth + 1)


def set_height(node_id):
    global T

    h1, h2 = 0, 0
    if T[node_id].left is not None:
        h1 = set_height(T[node_id].left) + 1
    if T[node_id].right is not None:
        h2 = set_height(T[node_id].right) + 1

    T[node_id].height = max(h1, h2)

    return max(h1, h2)


n = int(input())
T = []
root = 0

for i in range(n):
    T.append(Node())

for i in range(n):
    _ = list(map(int, input().split()))
    _id = _[0]
    left = _[1]
    right = _[2]
    if left == -1:
        left = None
    if right == -1:
        right = None

    T[_id].id = _id
    T[_id].left = left
    T[_id].right = right

    if left is not None:
        T[left].parent = _id
    if right is not None:
        T[right].parent = _id

    if left is not None and right is not None:
        T[left].sibling = right
        T[right].sibling = left

for i in range(n):
    if T[i].parent is None:
        T[i].parent = -1
        root = i
        break

set_depth(root, 0)
set_height(root)


for i in range(n):
    print(T[i])

Solution (Python):
class Node():
    def __init__(self,parent=-1,left=-1,right=-1,depth=0,height=-1,degree=0,sibling=-1,typ='internal node'):
        self.parent=parent
        self.left=left
        self.right=right
        self.depth=depth
        self.height=height
        self.degree=degree
        self.sibling=sibling
        self.typ=typ
        
def depth(node,i,n):
    node[i].depth=n
    if node[i].left!=-1:
        depth(node,node[i].left,n+1)
    if node[i].right!=-1:
        depth(node,node[i].right,n+1)

def height(node,i):
    hl,hr=0,0
    if node[i].left!=-1:
        height(node,node[i].left)
        hl=node[node[i].left].height+1
    if node[i].right!=-1:
        height(node,node[i].right)
        hr=node[node[i].right].height+1
    node[i].height=max(hl,hr)
    

n=int(input())
N=[Node() for i in range(n)]
for i in range(n):
    p,l,r=[int(i) for i in input().split()]
    if l!=-1:
        N[p].left=l
        N[l].parent=p
        N[p].degree+=1
        if r != -1:
            N[l].sibling=r
            N[r].sibling=l
    if r!=-1:
        N[p].right=r
        N[r].parent=p
        N[p].degree+=1
    elif l==-1 and r==-1:
        N[p].typ='leaf'
        N[p].height=0


for i in range(n):
    height(N,i)
    if N[i].parent==-1:
        N[i].typ='root'
        depth(N,i,0)

for i in range(n):
    print('node '+str(i)+': parent = '+str(N[i].parent)+', sibling = '+str(N[i].sibling)+', degree = '+str(N[i].degree)+', depth = '+str(N[i].depth)+', height = '+str(N[i].height)+', '+N[i].typ)

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


n = int(input())
node = {key: Node(-1, -1, -1) for key in range(n)} 
for i in range(n):
    tmp = list(map(int, input().split()))
    if tmp[1] != -1:
        node[tmp[0]].left = tmp[1]
        node[tmp[1]].parent = tmp[0]
    if tmp[2] != -1:
        node[tmp[0]].right = tmp[2]
        node[tmp[2]].parent = tmp[0]

def get_depth(node, D, u, d):
    D[u] = d
    if node[u].left != -1:
        get_depth(node, D, node[u].left, d+1)
    if node[u].right != -1:
        get_depth(node, D, node[u].right, d+1)


def get_height(node, H, u):
    h_l = 0   
    h_r = 0
    if node[u].left != -1:
        h_l = get_height(node, H, node[u].left) + 1
    if node[u].right != -1:
        h_r = get_height(node, H, node[u].right) + 1
    ans = max(h_l, h_r)
    H[u] = ans
    return ans

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

def get_degree(node, u):
    deg = 0
    if node[u].left != -1:
        deg +=1
    if node[u].right != -1:
        deg +=1
    return deg

for k, v in node.items():
    if v.parent is -1:
        root = k

D = {}
get_depth(node, D, root, 0)
H = {}
get_height(node, H, root)

def print_for_a_node(u):
    parent = node[u].parent
    sib = get_sibling(node, u)
    deg = get_degree(node, u)

    node_type = 'internal node' if deg != 0 else 'leaf'
    if parent == -1:
        node_type = 'root'

    print(f'node {u}: parent = {parent}, sibling = {sib}, degree = {deg}, depth = {D[u]}, height = {H[u]}, {node_type}')


for i in range(n):
    print_for_a_node(i)

Solution (Python):
n = int(input())

tree_dict = {}
node_info_dict = {}

for _ in range(n):
    row = list(map(int, input().split(" ")))
    
    tree_dict[row[0]] = {
        "left": row[1],
        "right": row[2], 
    }
    
    node_info_dict[row[1]] = {
        "parent": row[0], 
        "sibling": row[2], 
    }
        
    node_info_dict[row[2]] = {
        "parent": row[0], 
        "sibling": row[1], 
    }
        
def get_depth(node_id):
    count = 1
    parent_node_id = node_info_dict[node_id]["parent"]
    while parent_node_id in node_info_dict:
        count += 1
        parent_node_id = node_info_dict[parent_node_id]["parent"]
    
    return count

def get_height(node_id, height):
    right_height, left_height = 0, 0
    if tree_dict[node_id]["right"] != -1:
        right_height = get_height(tree_dict[node_id]["right"], height) + 1
    
    if tree_dict[node_id]["left"] != -1:
        left_height = get_height(tree_dict[node_id]["left"], height) + 1

    height = right_height if right_height > left_height else left_height
    return height
    
for i in range(n):
    if i in node_info_dict:
        parent = node_info_dict[i]['parent']
        sibling = node_info_dict[i]['sibling']
        depth = get_depth(i)
    else:
        parent = -1
        sibling = -1
        depth = 0
        
    degree = 0
    if tree_dict[i]["right"] != -1:
        degree += 1
    if tree_dict[i]["left"] != -1:
        degree += 1
        
    height = get_height(i, 0)
    
    if parent == -1:
        node_type = "root"
    elif tree_dict[i]["right"] == -1 and tree_dict[i]["left"] == -1:
        node_type = "leaf"
    else:
        node_type = "internal node"
        
    print(f"node {i}: parent = {parent}, sibling = {sibling}, degree = {degree}, depth = {depth}, height = {height}, {node_type}")

Solution (Python):
n=int(input())
p_list=[-1]*n
s_list=[-1]*n
c_list=[0]*n
degree=[0]*n
depth=[0]*n
height=[0]*n
type=[0]*n
for _ in range(n):
    id,l,r=map(int,input().split())
    c_list[id]=[l,r]
    if l!=-1 and r!=-1:
        degree[id]=2
        type[id]="internal node"
        p_list[l]=id
        p_list[r]=id
        s_list[l]=r
        s_list[r]=l
    elif r!=-1:
        degree[id]=1
        type[id]="internal node"
        p_list[r]=id
        s_list[r]=l
    elif l!=-1:
        degree[id]=1
        type[id]="internal node"
        p_list[l]=id
        s_list[l]=r
    else:
        degree[id]=0
        type[id]="leaf"
root=p_list.index(-1)
type[root]="root"
def dsf1(v,d):
    if v!=-1:
        depth[v]=d
        dsf1(c_list[v][0],d+1)
        dsf1(c_list[v][1],d+1)
dsf1(root,0)
def dsf2(v):
    if c_list[v]==[-1,-1]:
        height[v]=0
    else:
        dsf2(c_list[v][0])
        dsf2(c_list[v][1])
        height[v]=max(height[c_list[v][0]],height[c_list[v][1]])+1
dsf2(root)
for i in range(n):
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(i,p_list[i],s_list[i],degree[i],depth[i],height[i],type[i]))

Solution (Python):
n = int(input())
lst = [list(map(int,input().split())) for i in range(n)]
B = [lst[i][0] for i in range(n)]
node = [[] for i in range(n)]

def Insertion_Sort(lst,B,n):
    for i in range(1,n):
        v = B[i]
        w = lst[i]
        j = i-1
        while j>=0 and B[j]>v:
            B[j+1]=B[j]
            lst[j+1]=lst[j]
            j-=1
        B[j+1]=v
        lst[j+1]=w
        
def find_root():
    A = []
    for i in range(n):
        A.extend(lst[i][1:])
    for i in range(n):
        if not i in A:
            return i

def make_node(arg_parent, arg_sibling, arg_num, arg_depth):
    if arg_num == root:
        type = "root"
    elif lst[arg_num][1] == lst[arg_num][2] == -1:
        type = "leaf"
    else:
        type = "internal node"
    children_lst = lst[arg_num][1:]
    degree = 0
    for i in children_lst:
        if i != -1:
            degree+=1
    height = -1
    node[arg_num] = [arg_parent, arg_sibling, degree, arg_depth, height, type]
    if children_lst[0]!=-1:
        make_node(arg_num, children_lst[1], children_lst[0], arg_depth+1)
    if children_lst[1]!=-1:
        make_node(arg_num, children_lst[0], children_lst[1], arg_depth+1)

def make_height(arg_num, arg_height):
    if arg_height > node[arg_num][4]:
        node[arg_num][4] = arg_height
        if node[arg_num][0] != -1:
            make_height(node[arg_num][0], arg_height+1)

def make_height_0_list():
    A = []
    for i in range(n):
        if node[i][2] == 0:
            A.append(i)
    return A

Insertion_Sort(lst, B, n)
root = find_root()
make_node(-1, -1, root, 0)
height_0_list = make_height_0_list()
for i in height_0_list:
    make_height(i, 0)

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

Solution (Python):
import sys
input = sys.stdin.readline


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


N = int(input())
btree = [Node(-1, -1, -1) for i in range(N)]
root_cand_list = [i for i in range(N)]
depth = [-1 for i in range(N)]
height = [-1 for i in range(N)]
degree = [0 for i in range(N)]
sibling = [-1 for i in range(N)]


def main():

    for i in range(N):
        num, left, right = map(int, input().split())

        if left != -1:
            btree[num].left = left
            btree[left].parent = num
            root_cand_list.remove(left)
        if right != -1:
            btree[num].right = right
            btree[right].parent = num
            root_cand_list.remove(right)

    setDepth(root_cand_list[0], 0)
    setHeight(root_cand_list[0])
    showBTree()


def setDepth(num, d):
    depth[num] = d
    node = btree[num]
    dgr = 0
    if node.left != -1:
        setDepth(node.left, d + 1)
        dgr += 1
    if node.right != -1:
        setDepth(node.right, d + 1)
        dgr += 1

    if node.parent != -1:
        parent = btree[node.parent]
        if parent.left != -1 and parent.left != num:
            sibling[num] = parent.left
        elif parent.right != -1 and parent.right != num:
            sibling[num] = parent.right

    degree[num] = dgr


def setHeight(num):
    lh = 0
    rh = 0
    if btree[num].left != -1:
        lh = setHeight(btree[num].left)
    if btree[num].right != -1:
        rh = setHeight(btree[num].right)

    if btree[num].left == -1 and btree[num].right == -1:
        
        height[num] = 0
        h = 1
    else:
        height[num] = max(lh, rh)
        h = max(lh, rh) + 1
    return h


def showBTree():
    for i in range(N):
        if depth[i] == 0:
            TYPE = "root"
        elif height[i] == 0:
            TYPE = "leaf"
        else:
            TYPE = "internal node"

        print("node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}".format(i, btree[i].parent, sibling[i], degree[i], depth[i], height[i], TYPE))


if __name__ == '__main__':
    main()

Solution (Python):
class node:
    def __init__(self, parent, left, right, depth, height):
        self.p = parent
        self.l = left
        self.r = right
        self.d = depth
        self.h = height

def setDepth(u, depthPosition):
    if u == -1:
        return
    T[u].d = depthPosition
    setDepth(T[u].r, depthPosition + 1)
    setDepth(T[u].l, depthPosition + 1)

def setHeight(u):
    h1 = h2 = 0
    if T[u].r != -1:
        h1 = setHeight(T[u].r) + 1
    if T[u].l != -1:
        h2 = setHeight(T[u].l) + 1
    T[u].h = max(h1, h2)
    return max(h1, h2)

def getDegree(u):
    degree = 0
    if T[u].r != -1:
        degree += 1
    if T[u].l != -1:
        degree += 1
    return degree

def getSibling(u):
    if T[u].p == -1:
        return -1
    if T[T[u].p].l != u and T[T[u].p].l != -1:
        return T[T[u].p].l
    if T[T[u].p].r != u and T[T[u].p].r != -1:
        return T[T[u].p].r
    return -1    

n = int(input())
T = [node(-1, -1, -1, 0, 0) for _ in range(n)]
for _ in range(n):
    info = list(map(int, input().split(" ")))
    T[info[0]].l = info[1]
    T[info[0]].r = info[2]
    if info[1] != -1:
        T[info[1]].p = info[0]
    if info[2] != -1:
        T[info[2]].p = info[0]

for x in T:
    if x.p == -1:
        setDepth(T.index(x), 0)
        setHeight(T.index(x))

for i in range(n):
    print("node", end = ' ')
    print(i, end = ': ')
    print("parent =", end = ' ')
    print(T[i].p, end = ', ')
    print("sibling =", end = ' ')
    print(getSibling(i), end = ', ')
    print("degree =", end = ' ')
    print(getDegree(i), end = ', ')
    print("depth =", end = ' ')
    print(T[i].d, end = ', ')
    print("height =", end = ' ')
    print(T[i].h, end = ', ')
    if T[i].p == -1: print("root")
    elif T[i].r == -1 and T[i].l == -1: print("leaf")
    else: print("internal node")

Solution (Python):
n = int(input())
NIL = -1
class Node():
    def __init__(self):
        self.D = [0] * 10000
        self.H = [0] * 10000
        self.parent = [0] * 10000
        self.left = [0] * 10000
        self.right = [0] * 10000
        
    def setdepth(self, u, d):
        if u == NIL:
            return
        self.D[u] = d
        self.setdepth(self.left[u], d + 1)
        self.setdepth(self.right[u], d + 1)
    
    def setheight(self, u):
        h1 = 0
        h2 = 0
        if T.left[u] != NIL:
            h1 = self.setheight(T.left[u]) + 1
        if T.right[u] != NIL:
            h2 = self.setheight(T.right[u]) + 1
        self.H[u] = max(h1, h2)
        return self.H[u]
    
    def getsibling(self, u):
        if self.parent[u] == NIL:
            return NIL
        if self.left[self.parent[u]] != u and self.left[self.parent[u]] != NIL:
            return self.left[self.parent[u]]
        if self.right[self.parent[u]] != u and self.right[self.parent[u]] != NIL:
            return self.right[self.parent[u]]
        return NIL
    
    def printf(self, u):
        if self.parent[u] == NIL:
            s = 'root'
        elif self.left[u] == NIL and self.right[u] == NIL:
            s = 'leaf'
        else:
            s = 'internal node'
        
        deg = 0
        if self.left[u] != NIL:
            deg += 1
        if self.right[u] != NIL:
            deg += 1
        
        print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'\
              .format(u, self.parent[u], self.getsibling(u), deg, self.D[u], self.H[u], s))
        
        
T = Node()
for i in range(n):
    T.parent[i] = NIL

for i in range(n):
    v, l, r = (int(x) for x in input().split())
    T.left[v] = l
    T.right[v] = r
    if l != NIL:
        T.parent[l] = v
    if r != NIL:
        T.parent[r] = v

for i in range(n):
    if (T.parent[i] == NIL):
        root = i

T.setdepth(root, 0)
T.setheight(root)

for i in range(n):
    T.printf(i)

Solution (Python):



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


def get_all_height(T: dict, H: dict, u: int):
    '''
    深さ優先探索で各地点をめぐりながらHに高さ情報セットしていく
    '''
    h_left, h_right = 0, 0  
    
    
    if T[u].left is not None:
        h_left = get_all_height(T, H, T[u].left) + 1
    if T[u].right is not None:
        h_right = get_all_height(T, H, T[u].right) + 1
    ret = max(h_left, h_right)
    H[u] = ret
    return ret


def get_all_depth(T, D: dict, u, p: int):
    '''
    まあHがわかってればdepthに変換可能なんだけど練習のために再帰関数で実装する。

    Dは深さを格納するための辞書
    pは現在の深さ
    '''
    D[u] = p
    if T[u].left is not None:
        get_all_depth(T, D, T[u].left, p+1)
    if T[u].right is not None:
        get_all_depth(T, D, T[u].right, p+1)


def ret_sibling(T, u):
    '''
    一度親を経由すれば良い
    '''
    parent = T[u].parent
    if parent is None:
        return -1  
    ret = T[parent].left if T[parent].left != u else T[parent].right
    if ret is None:
        return -1
    return ret


def ret_degree(T, u):
    ret = 2
    if T[u].left is None:
        ret -= 1
    if T[u].right is None:
        ret -= 1
    return ret



n = int(input())
T = {key: Node(None, None, None) for key in range(n)}  
for _ in range(n):
    tmp = list(map(int, input().split()))
    
    if tmp[1] != -1:
        T[tmp[0]].left = tmp[1]  
        T[tmp[1]].parent = tmp[0]  
    if tmp[2] != -1:
        T[tmp[0]].right = tmp[2]  
        T[tmp[2]].parent = tmp[0]  


for k, v in T.items():
    if v.parent is None:
        ROOT = k
        break
else:
    raise ValueError("ROOTが存在しないなんておかしい")


D = {}
get_all_depth(T, D, ROOT, 0)
H = {}
get_all_height(T, H, ROOT)


def print_for_a_node(u):
    if T[u].parent is None:
        parent = -1
    else:
        parent = T[u].parent

    sib = ret_sibling(T, u)
    deg = ret_degree(T, u)
    node_type = 'internal node' if deg != 0 else 'leaf'
    if parent == -1:
        node_type = 'root'

    print(
        f'node {u}: parent = {parent}, sibling = {sib}, degree = {deg}, depth = {D[u]}, height = {H[u]}, {node_type}')


for node in range(n):
    print_for_a_node(node)

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

def setDepth(id, depth):
	global T
	T[id].depth = depth
	left = T[id].left
	right = T[id].right
	if left != -1:
		setDepth(left, depth + 1)
	if right != -1:
		setDepth(right, depth + 1)


def setHeight(H: int, u: int):
	global T
	h1 = 0
	h2 = 0
	if T[u].right != -1:
		h1 = setHeight(H, T[u].right) + 1
	if T[u].left != -1:
		h2 = setHeight(H, T[u].left) + 1
	height = max(h1, h2)
	T[u].height = height
	return height


if __name__ == "__main__":
	n = int(input())
	T = []
	for _ in range(n):
		T.append(Node())
	for _ in range(n):
		id, left, right = map(int, input().split())
		T[id].left = left
		T[id].right = right
		if left != -1:
			T[left].sibling = right
			T[left].parent = id
		if right != -1:
			T[right].sibling = left
			T[right].parent = id
	
	for i in range(n):
		if T[i].left == -1:
			T[i].degree -= 1
		if T[i].right == -1:
			T[i].degree -= 1
		if T[i].left == -1 and T[i].right == -1:
			T[i].type = "leaf"
		if T[i].parent == -1:
			root_id = i
			T[i].type = "root"

	setDepth(root_id, 0)
	setHeight(0, root_id)

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