Problem:

Binary Tree

A rooted binary tree is a tree with a root node in which every node has at most two children.

Your task is to write a program which reads a rooted binary tree T and prints the following information for each node u of T:

node ID of u

parent of u

sibling of u

the number of children of u

depth of u

height of u

node type (root, internal node or leaf)

If two nodes have the same parent, they are siblings. Here, if u and v have the same parent, we say u is a sibling of v (vice versa).

The height of a node in a tree is the number of edges on the longest simple downward path from the node to a leaf.

Here, the given binary tree consists of n nodes and evey node has a unique ID from 0 to n-1.

Input

The first line of the input includes an integer n, the number of nodes of the tree.

In the next n lines, the information of each node is given in the following format:

id left right

id is the node ID, left is ID of the left child and right is ID of the right child. If the node does not have the left (right) child, the left(right) is indicated by -1.

Output

Print the information of each node in the following format:

node id: parent = p, sibling = s, degree = deg, depth = dep, height = h, type

p is ID of its parent. If the node does not have a parent, print -1.

s is ID of its sibling. If the node does not have a sibling, print -1.

deg, dep and h are the number of children, depth and height of the node respectively.

type is a type of nodes represented by a string (root, internal node or leaf. If the root can be considered as a leaf or an internal node, print root.

Please follow the format presented in a sample output below.

Constraints

1 ≤ n ≤ 25

Sample Input 1

9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1

Sample Output 1

node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node
node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf
node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf
node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node
node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node
node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf
node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf
node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1


Sample output:
node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node
node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf
node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf
node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node
node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node
node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf
node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf
node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):#u : 自分ノードの番号
    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))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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)

Submission status: Accepted

Solution code:
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に高さ情報をセットしていく
    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)

Submission status: Accepted

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

#make_tree
for _ in range(N):
    #id, 子供の数k, c_0~c_k
    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"
        

#search_root
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)


#answer_output
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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

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()

Submission status: Accepted

Solution code:
###
# 二分木
###

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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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)

Submission status: Accepted

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

#for i in range(n):
#  print("debug:",T[i].p)

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)

#d=deque()
#d.append(T[root].left)
#d.append(T[root].right)
#while len(d)>0:
#  tmp=d.popleft()
#  d.append(tmp.left)
#  d.append(tmp.right)

#node id: parent = p, siling = s, degree = deg, depth = dep, height = h, type
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='')

Submission status: Accepted

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