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):
import sys
from typing import no_type_check_decorator
sys.setrecursionlimit(2**20)

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: dict, D: dict, u: int, p: int):
    """
    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: dict, u: int):
    """
    ノード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: dict, u: int):
    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 

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, id):
        self.id = id
        self.parent = -1
        self.right = -1
        self.left = -1
        self.sibling = -1
    def getDegree(self):
        count=0
        if self.right is not -1:
            count += 1
        if self.left is not -1:
            count += 1
        return count
    def getDepth(self):
        count = 0
        parent= self.parent
        while parent is not -1:
            count += 1
            parent = parent.parent
        return count
    def getType(self):
        if self.parent == -1:
            return 'root'
        elif self.left is -1 and self.right is -1:
            return 'leaf'
        else:
            return 'internal node'
    def getHeight(self, node, count =0):
        if node == -1:
            return -1
        if (node.left == -1 and node.right == -1):
            return 0
        else:
            return max(self.getHeight(node.left, count+1)+1, self.getHeight(node.right,count+1)+1)
n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
    id, left, right = map(int, input().split())
    if left != -1:
        nodes[id].left = nodes[left]
        nodes[left].parent = nodes[id]
    if right != -1:
        nodes[id].right = nodes[right]
        nodes[right].parent = nodes[id]
    if left != -1 and right != -1:
        nodes[left].sibling = nodes[right]
        nodes[right].sibling = nodes[left]

for i in nodes:
    output = ""
    output +=f'node {i.id}: '
    output +=f'parent = {i.parent if i.parent == -1 else i.parent.id}, '
    output +=f'sibling = {i.sibling if i.sibling == -1 else i.sibling.id}, '
    output +=f'degree = {i.getDegree()}, '
    output +=f'depth = {i.getDepth()}, '
    output +=f'height = {i.getHeight(i)}, '
    output +=f'{i.getType()}'
    print(output)

Solution (Python):
class Node():
    def __init__(self):
        self.parent = -1
        self.left = -1
        self.right = -1
        self.depth = 0
        self.sibling = -1
        self.degree = 0
        self.height = -1
        return

def getAncestor(t, n):
    for i in range(n):
        if t[i].parent == -1:
            return i

def setDepth(t, u, p=0):
    t[u].depth = p
    if t[u].left != -1:
        setDepth(t, t[u].left,p+1)
    if t[u].right != -1:
        setDepth(t, t[u].right,p+1)
    return

def seeHeight(h, u):
    h1 = 0
    h2 = 0
    if t[u].right != -1:
        h1 = seeHeight(t[u].height, t[u].right) + 1
    if t[u].left != -1:
        h2 = seeHeight(t[u].height, t[u].left) + 1

    t[u].height = max(h1, h2)
    return t[u].height

import sys

n = int(input())
t = []
for _ in range(n):
    t.append(Node())

for i in range(n):
    a = list(map(int, sys.stdin.readline().split()))
    m = a[0]
    t[m].left = a[1]
    t[m].right = a[2]
    if a[1] != -1:
        t[m].degree += 1
        t[a[1]].parent = m
        t[a[1]].sibling = a[2]
    if a[2] != -1:
        t[m].degree += 1
        t[a[2]].parent = m
        t[a[2]].sibling = a[1]

r = getAncestor(t, n)
setDepth(t, r)
seeHeight(-1, r)

for i in range(n):
    if i == r:
        print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, root'.format(i, t[i].parent, t[i].sibling, t[i].degree, t[i].depth, t[i].height))
    elif t[i].degree == 0:
        print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, leaf'.format(i, t[i].parent, t[i].sibling, t[i].degree, t[i].depth, t[i].height))
    else:
        print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, internal node'.format(i, t[i].parent, t[i].sibling, t[i].degree, t[i].depth, t[i].height))

Solution (Python):



class Node:
    def __init__(self):
        self.parentId=-1
        self.sibling=-1
        self.children=[]
        self.degree=0
        self.depth=-1
        self.height=-1
        self.type=""
        
def calcDepth(x,depth):
    global node
    node[x].depth=depth
    for i in node[x].children:
        calcDepth(i,depth+1)

def calcHeight(x,height):
    global node
    node[x].height=max([height,node[x].height])
    if node[x].parentId != -1:
        calcHeight(node[x].parentId,height+1)

n=int(input())
a=[[int(i)for i in input().split()]for j in range(n)]
node=[Node()for i in range(n)]

for i in a:
    id=i[0]
    left=i[1]
    right=i[2]
    node[id].children=[left,right]
    if left != -1:node[left].sibling,node[left].parentId=right,id
    if right != -1:node[right].sibling,node[right].parentId =left,id

for i in node:
    while -1 in i.children:
        i.children.remove(-1)

for i in node:
    i.degree=len(i.children)

for i in range(n):
    if node[i].parentId==-1:
        calcDepth(i,0)
        break

for i in range(n):
    if node[i].degree==0:
        calcHeight(i,0)

for i in node:
    if i.parentId == -1:
        i.type="root"
    elif i.height==0:
        i.type="leaf"
    else:
        i.type="internal node"


for i in range(n):
    print("node "+str(i)+": parent = "+str(node[i].parentId)+", sibling = "+str(node[i].sibling)+", degree = "+str(node[i].degree)+", depth = "+str(node[i].depth)+", height = "+str(node[i].height)+", "+node[i].type)

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

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_left = 0
    h_right = 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:int, p:int):
    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 == None:
        return -1
    if T[parent].left == u:
        ret = T[parent].right
    else:
        ret = T[parent].left

    if ret == None:
        return -1

    return ret

def ret_degree(T,u):
    ret = 0
    if T[u].left != None:
        ret += 1
    if T[u].right != 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 i in range(n):
    if T[i].parent is None:
        ROOT = i
        break
else:
    raise ValueError("ROOTが存在しないなんておかしい")


D = {}
get_all_depth(T,D,i,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.degree = 0
        self.sibling = -1

def cal_depth(node_id, d = 0):
    Tree[node_id].depth = d
    if Tree[node_id].left !=-1:
        cal_depth(Tree[node_id].left, d+1)
    if Tree[node_id].right !=-1:
        cal_depth(Tree[node_id].right, d+1)
        
def cal_height(node_id):
    left_h = 0
    right_h = 0
    if Tree[node_id].left != -1:
        left_h = cal_height(Tree[node_id].left) + 1
    if Tree[node_id].right != -1:
        right_h = cal_height(Tree[node_id].right) + 1
    Tree[node_id].height = max(left_h, right_h)
    return max(left_h, right_h)
    
    
    
    
    
N = int(input())
Tree = [Node() for _ in range(N)]


for _ in range(N):
    
    tree_info = list(map(int, input().split()))
    node_id = tree_info[0]
    left = tree_info[1]
    right = tree_info[2]
    
    Tree[node_id].left = left
    Tree[node_id].right = right
    
    if left != -1:
        Tree[left].parent = node_id
    if right != -1:
        Tree[right].parent = node_id
    
    if left == -1 and right == -1:
        Tree[node_id].type = "leaf"
    elif left == -1 or right == -1:
        Tree[node_id].degree = 1
        Tree[node_id].type = "internal node"
    else:
        
        Tree[right].sibling = left
        Tree[left].sibling = right
        Tree[node_id].degree = 2
        Tree[node_id].type = "internal node"
        


root_id =[i for i,t in enumerate(Tree) if t.parent == -1][0]
Tree[root_id].type = "root"
cal_depth(root_id)
cal_height(root_id)



for i, t in enumerate(Tree):
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(i, t.parent, t.sibling, t.degree, t.depth, t.height, t.type))

Solution (Python):
class Node:
    def __init__(self,num,leftchild,rightchild):
        self.id = num
        self.parent = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = 'leaf'
        self.leftchild = leftchild
        self.rightchild = rightchild
    
    def get_infomation(self):
        print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}'.format(self.id,self.parent,self.sibling,self.degree, self.depth,self.height,self.type))
 
def set_propaties(num,parent,sibling,depth):
    if num == -1:     
        return -1
    node = tree[num]
    lc = node.leftchild
    rc = node.rightchild
    node.parent = parent
    node.sibling = sibling
    node.depth = depth
    node.degree = (node.leftchild != -1) + (node.rightchild != -1)
    if lc != -1 or rc != -1:
        node.type = 'internal node'
    node.height = max(set_propaties(lc, num, rc, depth + 1),set_propaties(rc, num, lc, depth + 1)) + 1
    return node.height

n = int(input())
tree = [None]*n

root_num = int(n*(n-1)/2)

for x in range(n):
    num, leftchild, rightchild = list(map(int,input().split()))
    node = Node(num, leftchild, rightchild)
    tree[num] = node
    root_num -= (max(0, leftchild) + max(0, rightchild))

set_propaties(root_num, -1, -1, 0)
tree[root_num].type = 'root'

for n in tree:
    n.get_infomation()

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

class Node:
    def __init__(self):
        self.parent_id = -1
        self.sib = -1
        self.left = -1
        self.right = -1
        self.deg = 0
        self.height = 0
        self.depth = 0
        self.children = []

def cal_depth (node,x):
    node.depth = x

    for children_id in node.children:
        cal_depth(nodes[children_id],x+1)

def cal_height(node):

    h1 = 0
    h2 = 0
    if node.left != -1:
       h1 = cal_height(nodes[node.left]) + 1
    if node.right != -1:
       h2 = cal_height(nodes[node.right]) +1

    node.height = max(h1,h2)

    return max(h1,h2)



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

for i in range(n):
    deg = 0
    table = list(map(int,input().split()))
    node_id = table[0]
    nodes[node_id].left = table[1]
    nodes[node_id].right = table[2]
    if table[1] == -1 and table[2] == -1:
        nodes[node_id].deg = 0
    elif table[1] == -1 or table[2] == -1:
        nodes[node_id].deg = 1
        if table[1] != -1:
            nodes[table[1]].parent_id = node_id
            nodes[node_id].children.append(table[1])
        else:
            nodes[table[2]].parent_id = node_id
            nodes[node_id].children.append(table[2])
    else:
        nodes[node_id].deg = 2
        nodes[table[1]].parent_id = node_id
        nodes[table[2]].parent_id = node_id
        nodes[table[1]].sib = table[2]
        nodes[table[2]].sib = table[1]
        nodes[node_id].children.append(table[1])
        nodes[node_id].children.append(table[2])

for node in nodes:
    if node.parent_id == -1:
        cal_depth(node,0)
        cal_height(node)
        break



for i in range(n):

    print("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, "%(i,nodes[i].parent_id,nodes[i].sib,nodes[i].deg,nodes[i].depth,nodes[i].height),end = "")

    if nodes[i].parent_id == -1:
        print("root")
    else:
        if len(nodes[i].children) == 0: 
            print("leaf")
        else: 
            print("internal node")

Solution (Python):
class BinaryTree:
    class Node:
        def __init__(self):
            self.parent = -1
            self.sibling = -1
            self.degree = 0
            self.depth = 0
            self.height = 0
            self.children = []
            
            
    def __init__(self, n):
        self.nodes_num = n
        self.max_depth = 0
        self.nodes = [None] * n
        for i in range(self.nodes_num):
            node = self.Node()
            self.nodes[i] = node


    def load(self, node_info):
        for _node_info in node_info:
            node_num = _node_info[0]
            self.nodes[node_num].children.append(_node_info[1])
            self.nodes[node_num].children.append(_node_info[2])
            for child in self.nodes[node_num].children:
                if child != -1:
                    self.nodes[child].parent = node_num
            if not -1 in self.nodes[node_num].children:
                self.nodes[self.nodes[node_num].children[0]].sibling = self.nodes[node_num].children[1]
                self.nodes[self.nodes[node_num].children[1]].sibling = self.nodes[node_num].children[0]

                
    def _calc_depth(self, p):
        if self.nodes[p].parent == -1:
            return 0
        return 1 + self._calc_depth(self.nodes[p].parent) 

    
    def calc_depth(self):
        for i in range(self.nodes_num):
            self.nodes[i].depth = self._calc_depth(i)


    def _calc_height(self, p):
        h1, h2 = 0, 0
        if self.nodes[p].children[0] != -1:
            h1 = self._calc_height(self.nodes[p].children[0]) + 1
        if self.nodes[p].children[1] != -1:
            h2 = self._calc_height(self.nodes[p].children[1]) + 1
        return max(h1, h2)


    def calc_height(self):
        height = 0
        for i in range(self.nodes_num):
            self.nodes[i].height = self._calc_height(i)
    
    
    def print_nodes(self):
        for i in range(self.nodes_num):
            degree = len(self.nodes[i].children) - self.nodes[i].children.count(-1)
            if self.nodes[i].parent == -1:
                type = 'root'
            elif degree == 0:
                type = 'leaf'
            else:
                type = 'internal node'
            print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}'.format(i, self.nodes[i].parent, self.nodes[i].sibling, degree, self.nodes[i].depth, self.nodes[i].height, type ))


    def print_test(self):
        for i in range(self.nodes_num):
            print('node:' + str(i) + ' parent:' + str(self.nodes[i].parent) + ' sibling:' + str(self.nodes[i].sibling) + ' depth:' + str(self.nodes[i].depth) + ' height:' + str(self.nodes[i].height))


if __name__ == '__main__':
    n = int(input())
    node_info = []
    for _ in range(n):
        node_info.append(list(map(int, input().rstrip().split())))
    bt = BinaryTree(n)
    bt.load(node_info)
    bt.calc_depth()
    bt.calc_height()
    bt.print_nodes()

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def get_depth(parent, node):
    depth = 0
    n = node
    while True:
        if parent[n] == -1: break
        n = parent[n]
        depth += 1

    return depth


def get_sibling(parent, tree, node):
    p = parent[node]
    if p == -1:
        return -1
    else:
        return tree[p][0] if tree[p][0] != node else tree[p][1]


def get_degree(tree, node):
    l, r = tree[node]
    ret = 0
    if l != -1: ret += 1
    if r != -1: ret += 1
    return ret


def get_height(tree, node):
    h1, h2 = 0, 0
    if tree[node][0] != -1:
        h1 = get_height(tree, tree[node][0]) + 1
    if tree[node][1] != -1:
        h2 = get_height(tree, tree[node][1]) + 1
    return max(h1, h2)


def get_type(parent, tree, node):
    type = ''
    if parent[node] == -1:
        type = 'root'
    elif tree[node][0] == -1 and tree[node][1] == -1:
        type = 'leaf'
    else:
        type = 'internal node'
    return type


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    parent = [-1] * N
    tree = collections.defaultdict(list)

    for n in range(N):
        id, l, r = il()
        tree[id] = [l, r]
        if l != -1:
            parent[l] = id
        if r != -1:
            parent[r] = id

    for node in range(N):
        print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}'.format(
            node, parent[node], get_sibling(parent, tree, node), get_degree(tree, node), get_depth(parent, node),
            get_height(tree, node), get_type(parent, tree, node)
        ))


if __name__ == '__main__':
    main()

Solution (Python):




import sys

class Node:
    def __init__(self, val):
        self.val = val
        self.parent = None
        self.left = None
        self.right = None
        self.depth = 0
    
    def get_depth(self):
        if not self.parent:
            return 0
        else:
            return self.parent.get_depth()+1
    
    def get_sibling(self):
        if not self.parent:
            return - 1
        else:
            if self.parent.right and self.parent.right.val == self.val:
                if self.parent.left:
                    return self.parent.left.val
                else:
                    return - 1
            elif self.parent.left and self.parent.left.val == self.val:
                if self.parent.right:
                    return self.parent.right.val
                else:
                    return - 1
    
    def get_parent(self):
        if not self.parent:
            return -1
        return self.parent.val
    
    def get_degree(self):
        degree = 0
        if self.left:
            degree += 1
        if self.right:
            degree += 1
        return degree
    
    def get_type(self):
        if not self.parent:
            return "root"
        elif self.left or self.right:
            return "internal node"
        else:
            return "leaf"
    
    def get_height(self):
        if not self.left and not self.right:
            return 0
        l,r = 0,0
        if self.left:
            l = self.left.get_height()
        if self.right:
            r = self.right.get_height()
        return max(l + 1,r + 1)


def main():
    n = int(input().strip())
    nodes = [Node(i) for i in range(n)]
    for _ in range(n):
        val, left, right = [int(i) for i in input().strip().split()]
        if left != -1:
            nodes[val].left,nodes[left].parent = nodes[left],nodes[val]
        if right != -1:
            nodes[val].right,nodes[right].parent = nodes[right],nodes[val]

    for id in range(n):
        p = nodes[id].get_parent()
        s = nodes[id].get_sibling()
        deg = nodes[id].get_degree()
        dep = nodes[id].get_depth()
        h = nodes[id].get_height()
        _type = nodes[id].get_type()
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(id, p, s, deg, dep, h, _type))


if __name__ == "__main__":
    main()

Solution (Python):
import queue
from collections import namedtuple
U = namedtuple("U", "id parent sib degree dep height type")

dic, link = (dict() for _ in range(2))

n = int(input())
se = set(int(x) for x in range(n))

for _ in range(n):
    a, b, c = map(int, input().split())
    link[a] = list()
    for bc in [b, c]:
        if bc != -1: link[a].append(bc)
        se.discard(bc)


def bfs(s):
    q = queue.Queue()
    q.put(U(s, -1, -1, len(link[s]), 0, 0, "root"))

    while q.qsize() != 0:
        u0 = q.get()
        dic[u0.id] = u0

        if link[u0.id] == []:
            h = 0
            p = u0.parent
            while p != -1:
                dic[p] = dic[p]._replace(height=h + 1)
                p = dic[p].parent
                h += 1

        for u1 in link[u0.id]:
            sib = -1
            if len(link[u0.id]) == 2:
                sib = (set(link[u0.id]) - {u1}).pop()
            n_type = "internal node" if link[u1] != [] else "leaf"
            q.put(U(u1, u0.id, sib, len(link[u1]), u0.dep + 1, 0, n_type))


bfs(se.pop())
for i in range(n):
    print("node", i, end="")
    print(": parent =", dic[i].parent, end="")
    print(", sibling =", dic[i].sib, end="")
    print(", degree =", dic[i].degree, end="")
    print(", depth =", dic[i].dep, end="")
    print(", height =", dic[i].height, end="")
    print(",", dic[i].type)

Solution (Python):


class BinaryTree:
    def __init__(self, parent, left, right):
        self.parent = parent
        self.left = left
        self.right = right
        self.sibling = -1
    

T = []
n = int(input().rstrip())
 
for _ in range(n):
    T.append(BinaryTree(-1, -1, -1))

for i in range(n):
    input_line = list(map(int, input().rstrip().split(" ")))
    u, left, right = input_line
    T[u].left = left
    T[u].right = right
    if left != -1:
        T[left].parent = u
    if right != -1:
        T[right].parent = u
    if (left != -1) and (right != -1):
        T[left].sibling = right
        T[right].sibling = left

def get_degree(T, u):
    return int(T[u].left != -1) + int(T[u].right != -1)

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

for i, t in enumerate(T):
    if t.parent == -1:
        root = i
        break
H = [0] * n

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

set_height(root)

def print_info(T, u):
    node = u
    parent = T[u].parent
    sibling = T[u].sibling
    degree = get_degree(T, u)
    depth = get_depth(T, u)
    height = H[u]
    type_ = "root" if parent == -1 else "leaf" if degree == 0 else "internal node"
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(node, parent, sibling, degree, depth, height, type_))
    
for i in range(n):
    print_info(T, i)

Solution (Python):
from collections import deque

class Node:
  def __init__(self,l,r,p):
    self.l=l
    self.r=r
    self.p=p

n=int(input())

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




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

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

def getSubling(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



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

setHeight(root)
setDepth(root,0)










for i in range(n):
  node=T[i]
  deg=0
  if node.l!=-1:
    deg+=1
  if node.r!=-1:
    deg+=1
  s=getSubling(i)
  t='root' if i==root else 'leaf' if deg==0 else 'internal node'
  print('node ',i,': parent = ',node.p,', sibling = ',s,', degree = ',deg,', depth = ',D[i],', height = ',H[i],', ',t,sep='')

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

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

def get_depth(T:dict,u:int):
    d = 0
    while T[u] != -1:
        u = T[u].parent
        d += 1

D = {}

def get_all_depth(T:dict,u:int,p:int):
    D[u] = p
    if T[u].left != -1:
        get_all_depth(T,T[u].left,p+1)
    if T[u].right != -1:
        get_all_depth(T,T[u].right,p+1)

H = {}

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

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

def PRINT(T:dict,node:int,D:dict,H:dict):
    dig = (T[node].right!=-1)+(T[node].left!=-1)
    if (T[node].left==-1) and (T[node].right==-1):
        node_type = "leaf"
    else:
        node_type = "internal node"
    if T[node].parent == -1:
        node_type = "root"
    print(f"node {node}: parent = {T[node].parent}, sibling = {get_sibling(T,node)}, degree = {dig}, depth = {D[node]}, height = {H[node]}, {node_type}")

n = int(input())
T = {k: Node(-1,-1,-1) for k in range(n)}
    
for _ in range(n):
    a,b,c = map(int,input().split())
    T[a].left = b
    T[a].right = c
    if b != -1:
        T[b].parent = a
    if c != -1:
        T[c].parent = a
for node in range(n):
    if T[node].parent == -1:
        get_all_depth(T,node,0)
        get_all_height(T,node)
        break
for node in range(n):
    PRINT(T,node,D,H)