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

Solution (Python):



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


def settype(u):
    if T[u].parent == -1:
        Type[u] = "root"
    elif Deg[u] == 0:
        Type[u] = "leaf"
    else:
        Type[u] = "internal node"


def setdepth(u, p):
    Dep[u] = p
    if T[u].left != -1:
        setdepth(T[u].left, p + 1)
    if T[u].right != -1:
        setdepth(T[u].right, p + 1)


def setheight(u):
    hl, hr = 0, 0
    if T[u].left != -1:
        hl = setheight(T[u].left) + 1
    if T[u].right != -1:
        hr = setheight(T[u].right) + 1
    H[u] = max(hl, hr)
    return H[u]


n = int(input())
T = [Node() for i in range(n)]
S = [-1 for i in range(n)]
Deg = [0 for i in range(n)]

for i in range(n):
    id, left, right = (int(j) for j in input().split())
    if left != -1:
        T[id].left = left
        T[left].parent = id
        S[left] = right
        Deg[id] += 1
    if right != -1:
        T[id].right = right
        T[right].parent = id
        S[right] = left
        Deg[id] += 1

rootid = -1

for id in range(n):
    if T[id].parent == -1:
        rootid = id
        break

Dep = [-1 for i in range(n)]
setdepth(rootid, 0)

Type = ["" for i in range(n)]
for id in range(n):
    settype(id)

H = [-1 for i in range(n)]
setheight(rootid)

for id in range(n):
    print("node ", id, ": parent = ", T[id].parent, ", sibling = ", S[id], ", degree = ", Deg[id], ", depth = ", Dep[id], ", height = ", H[id], ", ", Type[id], sep="")

Solution (Python):
class Node:
    def __init__(self):
        self.parent = -1
        self.sibling = -1

def dfs(v,d=0):
    G[v].depth,G[v].height = d,0
    if G[v].left != -1:
        G[v].height = max(G[v].height,dfs(G[v].left,d+1)+1)
    if G[v].right != -1:
        G[v].height = max(G[v].height,dfs(G[v].right,d+1)+1)
    return G[v].height

N = int(input()) 
G =[Node() for _ in range(N)]
for _ in range(N):
    idx,*children = [int(x) for x in input().split()] 
    G[idx].left,G[idx].right = children
    if G[idx].left != -1 and G[idx].right != -1:
        G[G[idx].left].sibling,G[G[idx].right].sibling  = G[idx].right,G[idx].left 
    if G[idx].left != -1 or G[idx].right != -1:
        G[idx].type = "internal node"
    else:
        G[idx].type = "leaf"
    for child in children:
        if child != -1:
            G[child].parent =idx
root = [i for i,x in enumerate(G) if x.parent == -1][0]
G[root].type = "root"
dfs(root)
for i,node in enumerate(G):
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(i,node.parent,node.sibling,(node.left != -1) + (node.right != -1),node.depth,node.height,node.type))

Solution (Python):
def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    A_list = [[int(item) for item in input().split()] for _ in range(N)]
    A_list.sort(key=lambda x:x[0])

    
    T = [[0 for _ in range(7)] for _ in range(N)]

    
    def bfs(root):
        que = collections.deque([[root, 0, -1]])
        temp_depth = 0
        while que:
            
            temp = que.popleft()
            temp_node = temp[0]
            temp_depth = temp[1]
            temp_parent = temp[2]
            T[temp_node][0] = temp_node
            T[temp_node][1] = temp_parent 
            T[temp_node][4] = temp_depth
            children = A_list[temp_node][1:3]
            cnt = 0
            
            for child in children:
                if child >= 0:
                    cnt +=1
                    que.append([child, temp_depth+1, temp_node])
                    
            T[temp_node][3] = cnt

            siblings = A_list[temp_parent][1:3]
            for sibling in siblings:
                if sibling != temp_node:
                    T[temp_node][2] = sibling


    def height(node):

        max_depth = 0
        height_que = collections.deque([[node, 0]])

        while height_que:
            temp = height_que.popleft()
            temp_node = temp[0]
            temp_depth = temp[1]
            children = A_list[temp_node][1:3]
            
            for child in children:
                if child >= 0:
                    height_que.append([child, temp_depth+1])
            max_depth = max(max_depth, temp_depth)
        
        return max_depth 

    def is_root(node):
        root_check_que = collections.deque([node])
        foot_print = [False for _ in range(N)]

        while root_check_que:
            temp_node = root_check_que.popleft()
            foot_print[temp_node] = True
            children = A_list[temp_node][1:3]

            for child in children:
                if child >= 0 and foot_print[child] == False:
                    root_check_que.append(child)

        return all(foot_print)

    
    for i in range(N):
        if is_root(i):
            root = i
            break

    bfs(root)

    for node, left, right in A_list:

        if T[node][1] == -1:
            T[node][6] = 'root' 
        elif left == -1 and right == -1:
            T[node][6] = 'leaf'
        else:
            T[node][6] = 'internal node'

        T[node][5] = height(node)


    for node, parent, sibling, degree, depth, height, node_type in T:
        print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(node, parent, sibling, degree, depth, height, node_type))
    
if __name__ == "__main__":
    resolve()

Solution (Python):



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


class BinaryTree():
    def __init__(self, n):
        self.T = [Node(i) for i in range(n)]

    def set_children(self, idx, l, r):
        node = self.T[idx]
        node.left = l
        node.right = r

        deg = 0
        if l != -1:
            deg += 1
            self.T[l].parent = idx
            self.T[l].sibling = r

        if r != -1:
            deg += 1
            self.T[r].parent = idx
            self.T[r].sibling = l

        node.degree = deg

    def get_root(self):
        for idx, node in enumerate(self.T):
            if node.parent == -1:
                return idx

    def set_type(self):
        for i, node in enumerate(self.T):
            if node.parent == -1:
                node.type = 'root'
            elif node.left == -1 and node.right == -1:
                node.type = 'leaf'
            else:
                node.type = 'internal node'

    def set_depth(self):
        root = self.get_root()
        self.set_depth_rec(root, 0)

    def set_depth_rec(self, idx, depth):
        node = self.T[idx]
        node.depth = depth
        if node.left != -1:
            self.set_depth_rec(node.left, depth+1)
        if node.right != -1:
            self.set_depth_rec(node.right, depth+1)

    def set_height(self):
        root = self.get_root()
        self.set_height_rec(root)

    def set_height_rec(self, idx):
        node = self.T[idx]
        if node.left == -1 and node.right == -1:
            node.height = 0
            return 0

        height = max(
            self.set_height_rec(node.left),
            self.set_height_rec(node.right)
        ) + 1

        node.height = height
        return height


N = int(input())
tree = BinaryTree(N)

for _ in range(N):
    idx, l, r = map(int, input().split())

    tree.set_children(idx, l, r)

tree.set_type()
tree.set_depth()
tree.set_height()

for node in tree.T:
    i = node.idx
    p = node.parent
    s = node.sibling
    deg = node.degree
    dep = node.depth
    h = node.height
    typ = node.type

    print(
        f'node {i}: parent = {p}, sibling = {s}, degree = {deg}, depth = {dep}, height = {h}, {typ}')

Solution (Python):
import sys
n = int(input())
class Node:
  def __init__(self):
    self.p = -1 
    self.l = -1 
    self.r = -1 

T = [Node() for _ in range(n)]
D = [0]*n
sys.setrecursionlimit(1500)
def rec(u,p):
  D[u] = p
  if T[u].r != -1: rec(T[u].r,p+1)
  if T[u].l != -1: rec(T[u].l,p+1)

H = [0]*n
def rec1(u):
  r = l = 0
  if T[u].r != -1: r = rec1(T[u].r)+1
  if T[u].l != -1: l = rec1(T[u].l)+1
  H[u] = max(r,l)
  return H[u]
def sib(n):
  if T[n].p == -1:
    return -1
  if T[T[n].p].l == n:
    return T[T[n].p].r
  if T[T[n].p].r == n:
    return T[T[n].p].l
for i in range(n):
    v,l,r = map(int,input().split())
    T[v].r = r
    if r != -1:
      T[r].p = v
    T[v].l = l
    if l != -1:
      T[l].p = v
    

for i in range(n):
  
  if T[i].p == -1 : r = i

rec(r,0)
rec1(r)

for i in range(n):
  
  d = 0
  if T[i].l != -1:
    d += 1
  if T[i].r != -1:
    d += 1  
  if T[i].p == -1:
    kind = "root"
  elif d == 0: kind = "leaf"
  else: kind = "internal node"
  print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
        .format(i,T[i].p,sib(i),d,D[i],H[i],kind))

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

def GetDepth(T, u):
    d = 0
    n = T[u]

    while n.parent != -1:
        n = T[n.parent]
        d += 1

    return d

def GetHight(T, u, d):

    if T[u].left != -1:
        h1 = GetHight(T, T[u].left, d + 1)
    else:
        h1 = d

    if T[u].right != -1:
        h2 = GetHight(T, T[u].right, d + 1)
    else:
        h2 = d

    return max(h1, h2)

def Main():

    n = int(input())

    T = [Node(-1, -1, -1, -1, -1) for i in range(n)]
    D = [0 for i in range(n)]
    H = [0 for i in range(n)]

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

        if left != -1 and right != -1:
            degree = 2
        elif left == -1 and right == -1:
            degree = 0
        else:
            degree = 1

        T[node_id].left = left
        T[node_id].right = right
        T[node_id].degree = degree

        if left != -1 and right != -1:
            T[left].sibling = right
            T[right].sibling = left

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

    for i in range(len(T)):

        if T[i].parent == -1:
            node_type = "root"
        elif T[i].left == -1 and T[i].right == -1:
            node_type = "leaf"
        else:
            node_type = "internal node"

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

Main()

Solution (Python):
from collections import defaultdict

class TreeNode():

  def __init__(self, val):
    self.val = val
    self.parent = -1
    self.sibling = -1
    self.left = None
    self.right = None
    self.depth = -1
    self.height = -1

  def node_type(self):
    if self.depth == 0:
      return "root"
    elif self.left or self.right:
      return "internal node"
    else:
      return "leaf"

  def get_degree(self):
    deg = 0
    if self.left: deg += 1
    if self.right: deg += 1

    return deg

  def __str__(self):
    
    return "node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}".format(
      str(self.val), str(self.parent), str(self.sibling), str(self.get_degree()), str(self.depth), str(self.height), str(self.node_type()))

def calc_depth(root, level):
  if root is None: return
  root.depth = level

  calc_depth(root.left, level+1)
  calc_depth(root.right, level+1)

def calc_height(root):
  if root is None: return 0

  leftHeight = calc_height(root.left)
  rightHeight = calc_height(root.right)

  return 1 + max(leftHeight, rightHeight)

num = int(input())
nodes = defaultdict(int)

for i in range(num):
  ins = list(map(int, input().split()))
  val = ins[0]

  if nodes[val] == 0:
    nodes[val] = TreeNode(val)
  n = nodes[val]

  left_val, right_val = ins[1], ins[2]
  
  if left_val != -1:
    
    if nodes[left_val] == 0:
      nodes[left_val] = TreeNode(left_val)

    
    n.left = nodes[left_val]
    n.left.parent = n.val
    
    if right_val != -1:
      n.left.sibling = right_val

  if right_val != -1:
    if nodes[right_val] == 0:
      nodes[right_val] = TreeNode(right_val)

    n.right = nodes[right_val]
    n.right.parent = n.val
    if left_val != -1:
      n.right.sibling = left_val

root = [node for node in nodes.values() if node.parent == -1][0]
calc_depth(root, 0)
for i in range(num):
  n  = nodes[i]
  n.height = calc_height(n) - 1

sort_nodes = sorted(nodes.items(), key=lambda x:x[0] )
for _, node in sort_nodes:
  print(node)

Solution (Python):
import sys
readline = sys.stdin.readline
writelines = sys.stdout.writelines
N = int(readline())
L = [None]*N; R = [None]*N
S = [-1]*N
P = [-1]*N
D = [-1]*N
DG = [0]*N
H = [-1]*N
for i in range(N):
    i, l, r = map(int, readline().split())
    L[i] = l; R[i] = r
    if l != -1:
        P[l] = i
        DG[i] += 1
    if r != -1:
        P[r] = i
        DG[i] += 1
    if l != -1 != r:
        S[l] = r; S[r] = l
def dfs(v, d):
    D[v] = d
    H[v] = h = max((dfs(L[v], d+1) if L[v] != -1 else 0), (dfs(R[v], d+1) if R[v] != -1 else 0))
    return h+1
dfs(P.index(-1), 0)
writelines(["node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n" % (i, P[i], S[i], DG[i], D[i], H[i], 'root' if P[i] == -1 else 'leaf' if DG[i] == 0 else 'internal node') for i in range(N)])

Solution (Python):
class Node:
    def __init__(self, num=None, parent=None, left=None, right=None, depth=None, height=None, sibling=None
                 , degree=None, type=None):
        self.num = num
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.height = height
        self.sibling = sibling
        self.degree = degree
        self.type = type

    def __str__(self):
        if self.parent is None:
            resParent = '-1'
        else:
            resParent = str(self.parent.num)

        if self.sibling is None:
            resSibling = '-1'
        else:
            resSibling = str(self.sibling.num)

        return 'node ' + str(self.num) + ': parent = ' + resParent + ', sibling = ' + resSibling \
               + ', degree = ' + str(self.degree) + ', depth = ' + str(self.depth) + ', height = ' + str(self.height) \
               + ', ' + self.type

def setDepth(node, depth):
    """
    :param node: Root node (in order to set height value to all nodes underneath
    :param depth: Depth of root node (=0)
    :return: nothing
    """
    if node == None:
        return
    node.depth = depth
    setDepth(node.left, depth+1)
    setDepth(node.right, depth+1)

def setHeight(node):
    """
    :param node: Root node (in order to set height value to all nodes underneath
    :return: height + set height value to all nodes underneatha
    """
    h1, h2 = 0, 0
    if node.left is not None:
        h1 = setHeight(node.left) + 1
    if node.right is not None:
        h2 = setHeight(node.right) + 1
    height = max(h1, h2)
    node.height = height
    return height

def getSibling(node):
    parent = node.parent
    if parent is None:
        return None
    elif parent.left != node and parent.left is not None:
        return parent.left
    elif parent.right != node and parent.right is not None:
        return parent.right
    return None

def getDegree(node):
    if node.left is None and node.right is None:
        return 0
    elif node.left is None or node.right is None:
        return 1
    else:
        return 2

def getType(node):
    if node.parent is None:
        return 'root'
    elif node.left is None and node.right is None:
        return 'leaf'
    else:
        return 'internal node'




n = int(input())
nodes = []


for i in range(n):
    node = Node(i)
    nodes.append(node)


for i in range(n):
    num, leftNum, rightNum = map(int, input().split())
    node = nodes[num]
    if leftNum != -1:
        node.left = nodes[leftNum]
        node.left.parent = node
    if rightNum != -1:
        node.right = nodes[rightNum]
        node.right.parent = node

for node in nodes:
    node.sibling = getSibling(node)
    node.degree = getDegree(node)
    node.type = getType(node)
    if node.type == 'root':
        root = node

setDepth(root, 0)
setHeight(root)

for node in nodes:
    print(node)

Solution (Python):



class Node:
    def __init__(self, id):
        self.id = id
        self.parent = -1
        self.sibling = -1
        self.children = []
        self.depth = 0
        self.height = 0
        self.ntype = None
    
    def __str__(self):
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.\
            format(self.id, self.parent, self.sibling, len(self.children), self.depth, self.height, self.ntype)
        
N = int(input())

nodes = [Node(i) for i in range(N)]


for i in range(N):
    id, l, r = [int(i) for i in input().split()]
    deg = 0
    if l >= 0 and r >= 0:
        nodes[id].children += [l, r]
        nodes[l].parent = id
        nodes[l].sibling = r
        nodes[r].parent = id
        nodes[r].sibling = l
        nodes[id].ntype = 'internal node'
    elif l >= 0:
        nodes[l].parent = id
        nodes[id].children.append(l)
        nodes[id].ntype = 'internal node'
    elif r >= 0:
        nodes[r].parent = id
        nodes[id].children.append(r)
        nodes[id].ntype = 'internal node'
    else:  
        nodes[id].ntype = 'leaf'


root = -1
for i in range(N):
    if nodes[i].parent == -1:
        root = i
        nodes[i].ntype = 'root'
        break

def nfs(node, dep):
    node.depth = dep
    
    if not node.children:
        node.height = 0
        return 0
    
    for child in node.children:
        h = nfs(nodes[child], dep+1)
        node.height = max(node.height, h+1)
    
    return node.height

nfs(nodes[root], 0)

for node in nodes:
    print(node)

Solution (Python):
from collections import defaultdict as dd
dicLeft = dd(lambda: -1)
dicRight = dd(lambda: -1)
dicParent = dd(lambda: -1)

n = int(input())
for i in range(n):
  id, left, right = map(int, input().split())
  dicLeft[id] = left
  dicRight[id] = right
  dicParent[left] = id
  dicParent[right] = id

def depth(dicPar, id):
  if dicPar[id] == -1:
    return 0
  else:
    return depth(dicPar, dicPar[id]) + 1

def height(dicLeft, dicRight, id):
  left = dicLeft[id]
  right = dicRight[id]
  if left == -1 and right == -1:
    return 0
  elif left == -1:
    return height(dicLeft, dicRight, right) + 1
  elif right == -1:
    return height(dicLeft, dicRight, left) + 1
  else:
    return max(height(dicLeft, dicRight, left), height(dicLeft, dicRight, right)) + 1

def degree(dicLeft, dicRight, id):
  counter = 0
  if dicLeft[id] != -1:
    counter += 1
  if dicRight[id] != -1:
    counter += 1
  return counter

def sibling(dicParent, dicLeft, dicRight, id):
  parent = dicParent[id]
  if parent == -1:
    return -1
  else:
    if dicLeft[parent] == id:
      return dicRight[parent]
    elif dicRight[parent] == id:
      return dicLeft[parent]

def nodeType(dicPar, dicLeft, dicRight, id):
  if dicPar[id] == -1:
    return "root"
  elif dicLeft[id] == -1 and dicRight[id] == -1:
    return "leaf"
  else:
    return "internal node"


for id in range(n):
  print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(id, dicParent[id], sibling(dicParent, dicLeft, dicRight, id), degree(dicLeft, dicRight, id), depth(dicParent, id), height(dicLeft, dicRight, id), nodeType(dicParent, dicLeft, dicRight, id)))

Solution (Python):
n = int(input())
p = [-1] * n
c = [None] * n
dp = [-1] * n
h = [None] * n
sb = [-1] * n
k = [None] * n
deg = [-1] * n

for i in range(n):
    id, l, r = map(int, input().split())
    c[id] = [l, r]

for i in range(n):
    l, r = c[i]
    if l>=0:
        p[l] = i
    if r>=0:
        p[r] = i

for i in range(n):
    d = 0
    pr = p[i]
    while pr>=0:
        d += 1
        pr = p[pr]
    dp[i] = d
    
def get_height(idx):
    if sum(c[idx]) == -2:
        return 0
    else:
        return max(get_height(c[idx][0]), get_height(c[idx][1])) + 1

h = [get_height(i) for i in range(n)]

for l, r in c:
    if l>=0 and r>=0:
        sb[l] = r
        sb[r] = l
for i in range(n):
    if p[i]==-1:
        k[i]='root'
    elif sum(c[i]) == -2:
        k[i]='leaf'
    else:
        k[i]='internal node'
        
for i in range(n):
    l, r = c[i]
    if l==-1 and r==-1:
        deg[i]=0
    elif l>=0 and r>=0:
        deg[i]=2
    else:
        deg[i]=1
    print('node %i: parent = %i, sibling = %i, degree = %i, depth = %i, height = %i, %s'%(i, p[i], sb[i], deg[i], dp[i], h[i], k[i]))

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

for _ in range(N):
    inp = [int(n) for n in input().split()]
    tree[inp[0]]['left'] = inp[1]
    tree[inp[0]]['right'] = inp[2]
    tree[inp[0]]['degree'] = sum([inp[1]!= -1, inp[2] != -1])

    if inp[1] != -1:
        tree[inp[1]]['parent'] = inp[0]
        tree[inp[1]]['sibling'] = inp[2]
    if inp[2] != -1:
        tree[inp[2]]['parent'] = inp[0]
        tree[inp[2]]['sibling'] = inp[1]

    parent = parent.difference(inp[1:])

def set_depth(n, depth):
    tree[n]['depth'] = depth

    if tree[n]['left'] != -1:
        set_depth(tree[n]['left'], depth+1)
    if tree[n]['right'] != -1:
        set_depth(tree[n]['right'], depth+1)

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

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

set_height(root)

for n in range(N):
    if tree[n]['parent'] == -1:
        tree[n]['type'] = 'root'
    elif tree[n]['degree'] == 0:
        tree[n]['type'] = 'leaf'
    else:
        tree[n]['type'] = 'internal node'

    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"\
        .format(n, tree[n]['parent'], tree[n]['sibling'], tree[n]['degree'], tree[n]['depth'], tree[n]['height'], tree[n]['type']))

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

T.sort(key = lambda x: x[0])

def calc_parent(T,data):
    for i in range(n):
        if T[i][1] == data or T[i][2] == data:
            return T[i][0]
    return -1

def calc_sibling(T,data):
    if T[calc_parent(T,data)][1] == data:
        return T[calc_parent(T,data)][2]
    elif T[calc_parent(T,data)][2] == data:
        return T[calc_parent(T,data)][1]
    else:
        return -1

def calc_degree(T,data):
    count = 0
    if T[data][1] != -1:
        count += 1
    if T[data][2] != -1:
        count += 1
    return count

def calc_depth(T,data):
    depth = 0
    while calc_parent(T,data) != -1:
        data = calc_parent(T,data)
        depth += 1
    return depth

def calc_height(T,data):
    if data == -1:
        return -1
    else:
        return max(1+calc_height(T,T[data][1]),
                    1+calc_height(T,T[data][2]))

def calc_type(T,data):
    if calc_parent(T,data) == -1:
        return "root"
    elif calc_degree(T,data) == 0:
        return "leaf"
    else:
        return "internal node"

for i in range(n):
    print("node "+str(i), end="")
    print(": parent = "+str(calc_parent(T,i)),end="")
    print(", sibling = "+str(calc_sibling(T,i)), end="")
    print(", degree = "+str(calc_degree(T,i)), end="")
    print(", depth = "+str(calc_depth(T,i)), end="")
    print(", height = "+str(calc_height(T,i)), end="")
    print(", "+str(calc_type(T,i)))

Solution (Python):
def det_par_sib_deg(nodes):
    n = len(nodes)
    parent = [-1] * n
    sibling = [-1] * n
    degree = [0] * n
    
    for i in range(n):
        p = nodes[i][0]
        l = nodes[i][1]
        r = nodes[i][2]
        if l==-1 and r==-1:
            degree[i] = 0
        elif l!=-1 and r==-1:
            parent[l] = p
            degree[i] = 1
        elif l==-1 and r!=-1:
            parent[r] = p
            degree[i] = 1
        else:
            parent[l] = parent[r] = p
            sibling[l] = r
            sibling[r] = l
            degree[i] = 2
    
    return parent, sibling, degree

def get_root(parent):
    n = len(parent)
    for i in range(n):
        if parent[i]==-1:
            return i

def det_types(root,nodes,degree):
    n = len(nodes)
    types = [""] * n
    for i in range(n):
        if degree[i]==0:
            types[i] = "leaf"
        else:
            types[i] = "internal node"
    types[root] = "root"
    return types

def get_child(num,nodes,degree):
    deg = degree[num]
    if deg==2:
        return deg, [nodes[num][1], nodes[num][2]]
    if deg==1:
        if nodes[num][1]==-1:
            return deg, [nodes[num][2]]
        else:
            return deg, [nodes[num][1]]
    if deg==0:
        return deg, []

def get_leaves(nodes,types):
    n = len(nodes)
    leaves = []
    for i in range(n):
        if types[i]=="leaf":
            leaves.append(i)
    return leaves

def det_height_depth(root,nodes,parent,types):
    n = len(nodes)
    height = [0] * n
    depth = [0] * n
    
    leaves = get_leaves(nodes,types)    
    for leaf in leaves:
        branch = [leaf]
        h = 1
        p = parent[leaf]
        while p!=-1:
            branch.append(p)
            if h>height[p]:
                height[p] = h
            p = parent[p]
            h += 1
        for i,node in enumerate(branch):
            depth[node] = (h-1) - i
        
    return height, depth




    

    










        


def print_res(n, nodes):
    parent, sibling, degree = det_par_sib_deg(nodes)
    root = get_root(parent)
    types = det_types(root,nodes,degree)
    height, depth = det_height_depth(root,nodes,parent,types)
    for i in range(n):
        num = nodes[i][0]        
        print("node " + str(num) + \
              ": parent = " + str(parent[i]) + \
              ", sibling = " + str(sibling[i]) + \
              ", degree = " + str(degree[i]) + \
              ", depth = " + str(depth[i]) + \
              ", height = " + str(height[i]) + \
              ", " + types[i] )

if __name__ == "__main__":
    n = int(input())
    nodes = [[]] * n
    for i in range(n):
        node = list(map(int, input().split()))
        nodes[node[0]] = node
    print_res(n,nodes)

Solution (Python):
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    from collections import defaultdict

    NIL = -1

    n = int(input())

    T = defaultdict(lambda: {'left':NIL, 'right':NIL, 'parent':NIL})
    D = {}
    H = {}

    for _ in range(n):
        u, left, right = map(int, input().split())
        T[u]['left'] = left
        T[u]['right'] = right
        if left != NIL:
            T[left]['parent'] = u
        if right != NIL:
            T[right]['parent'] = u

    def set_depth(u, d):
        if u == NIL:
            return
        D[u] = d
        set_depth(T[u]['left'], d+1)
        set_depth(T[u]['right'], d+1)

    def set_height(u):
        h1 = 0
        h2 = 0
        if T[u]['left'] != NIL:
            h1 = set_height(T[u]['left'])+1
        if T[u]['right'] != NIL:
            h2 = set_height(T[u]['right'])+1
        height = max(h1, h2)
        H[u] = height
        return height

    for u, value in T.items():
        if value['parent'] == NIL:
            root = u
            break

    set_depth(root, 0)
    set_height(root)

    
    def get_sibling(u):
        if T[u]['parent'] == NIL:
            return NIL
        if T[T[u]['parent']]['left'] != u:  
            return T[T[u]['parent']]['left']
        if T[T[u]['parent']]['right'] != u:  
            return T[T[u]['parent']]['right']
        return NIL

    for u in range(n):
        value = T[u]
        parent = value['parent']
        sibling = get_sibling(u)
        deg = 0
        if T[u]['left'] != NIL:
            deg += 1
        if T[u]['right'] != NIL:
            deg += 1
        if value['parent'] == NIL:
            type = 'root'
        elif value['left'] == NIL and value['right'] == NIL:
            type = 'leaf'
        else:
            type = 'internal node'
        depth = D[u]
        height = H[u]
        print('node ' + str(u) + ': ', end='')
        print('parent = ' + str(parent) +', ', end='')
        print('sibling = ' + str(sibling) + ', ', end='')
        print('degree = ' + str(deg) + ', ', end='')
        print('depth = ' + str(depth) + ', ', end='')
        print('height = ' + str(height) + ', ', end='')
        print(type)