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

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


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

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

    return -1

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

    return max(h1,h2)

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

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

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
tree = [0] * n
root = set(range(n))
def type(i, parent, sibling, depth):
    if i == -1:
        return -1
    node = tree[i]
    l, r = node[0], node[1]
    node[2], node[3], node[5] = parent, sibling, depth
    node[4] = (l != -1) + (r != -1)
    h = node[6] = max(type(l, i, r, depth + 1), type(r, i, l, depth + 1)) + 1
    return h
 
while n:
    i, l, r = list(map(int, input().split()))
    tree[i] = [l, r] + [0] * 5
    root -= {l, r}
    n -= 1
type(root.pop(), -1, -1, 0)
for i, node in enumerate(tree):
    l, r, p, s, deg, dep, h = node
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i, p, s, deg, dep, h,
    'root' if not dep else 'internal node' if deg else 'leaf'))

Submission status: Accepted

Solution code:
def depth(id):
    depth = 0
    target_id = id
    while nodes[target_id][0] !=-1:
        depth += 1
        target_id = nodes[target_id][0]
    return depth

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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


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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

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

        return self.parent.get_depth() + 1

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

        return max(l, r) + 1

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

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


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

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

Submission status: Accepted

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

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

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

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

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


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

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

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

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


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

    # set children's parent if Node idx is not leaf
    if left != -1:
        T[left].parent = idx
    if right != -1:
        T[right].parent = idx

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

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

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000000)

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

T = [Node(NIL, NIL, NIL) for _ in range(n)]
#入力から二分木の情報を受け取る 
for _ in range(n):
    data = [int(i) for i in input().split()]
    node_id = data[0]
    cl = data[1]
    cr = data[2]
    T[node_id].l = cl
    T[node_id].r = cr
    cnt_child = 0
    if cl != NIL:
        T[cl].p = node_id
        T[cl].s = cr
        cnt_child += 1
    if cr != NIL:
        T[cr].p = node_id
        T[cr].s = cl
        cnt_child += 1
    T[node_id].c = cnt_child 

#node id: parent = p, sibling = s, degree = deg, height = h, typeを出力するプログラムを作る

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

#rootのノードを探す関数
def searchRoot():
    for i in range(n):
        if T[i].p == NIL:
            return i
    return 

#高さを求める関数
#sovelHeight関数はnode_idの高さを返す関数
def solveHeight(node_id):
    hl = 0
    hr = 0
    #node_idから子を辿る
    if T[node_id].l != NIL: 
        hl = solveHeight(T[node_id].l)+1
    if T[node_id].r != NIL:
        hr = solveHeight(T[node_id].r)+1
    res = max(hl, hr)
    T[node_id].h = res
    return res


#nodeの種類を求める関数
def nodeType(node_id):
    if T[node_id].p == NIL:
        T[node_id].t = 'root'
        return  

    if (T[node_id].l == NIL) and (T[node_id].r == NIL):
        T[node_id].t = 'leaf'
        return 
    #rootでもleafでもないnodeはindternal nodeである
    T[node_id].t = 'internal node'

#全てのnodeの種類を決める
def allNodeTypeDiff():
    for i in range(n):
        nodeType(i)

#node_idのノードの情報をprintする
def nodeInfo(node_id):
    p = T[node_id].p
    s = T[node_id].s
    c = T[node_id].c
    d = T[node_id].d
    h = T[node_id].h
    t = T[node_id].t
    node_info = "node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(node_id, p, s, c, d, h, t)
    print(node_info)
#全てのノードの情報をprintする
def allNodeInfo():
    for i in range(n):
        nodeInfo(i)

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

Submission status: Accepted

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

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


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

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

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

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


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

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

  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**20)
n = int(input())
NIL = -1
class node:
    def __init__(self,parent,left,right,key):
        self.parent = parent
        self.left = left
        self.right = right
        self.key = key
T = [node(NIL,NIL,NIL,NIL) for _ in range(n)]
D = [0]*n
def setDepth(u,p):#uはノードの番号、pはノードpの深さ。
    if u == NIL:
        return
    D[u] = p      #uより下にあるノードの深さをDに保存し、かえす
    if T[u].left != NIL:
        setDepth(T[u].left,p+1)
    if T[u].right != NIL:
        setDepth(T[u].right,p+1)
    return D
H = [0]*n
def setHeight(u,H):
    hl = 0
    hr = 0
    if T[u].left != NIL:
        hl = 1 + setHeight(T[u].left,H)
    if T[u].right != NIL:
        hr = 1 + setHeight(T[u].right,H)
    ret = max(hl,hr)
    H[u] = ret
    return ret
def getDegree(u):
    cc = 0
    if T[i].left != NIL:
        cc += 1
    if T[i].right != NIL:
        cc += 1
    return cc
def getDepth(u):
    d = 0
    while T[u].parent != NIL:
        u = T[u].parent
        d += 1
    return d
def getBrother(u):
    if T[u].parent == NIL:
        return NIL
    elif T[T[u].parent].left == u:
        return T[T[u].parent].right
    elif T[T[u].parent].right == u:
        return T[T[u].parent].left
def printChildren(u):#番号uのノードの子供をlistでかえす
    child = []
    if T[u].left != NIL:
        child.append(T[u].left)
    if T[u].right != NIL:
        child.append(T[u].right)
    return child
def ppp():
	for i in range(n):
  		ccc = T[i]
  		print(i,ccc.parent,ccc.left,ccc.right)
def findroot(u): #根をみつける
    while T[u].parent != NIL:
        u = T[u].parent
    return u
#巡回
rl = []
def rootleft(u,rl): #どのパターンでもrootからスタート
    if u == NIL:
        return
    rl.append(u)
    rootleft(T[u].left,rl)
    rootleft(T[u].right,rl)
lro = []
def leftroot(u,lro):
    if u == NIL:
        return
    leftroot(T[u].left,lro)
    lro.append(u)
    leftroot(T[u].right,lro)
lri = []
def leftright(u,lri):
    if u == NIL:
        return
    leftright(T[u].left,lri)
    leftright(T[u].right,lri)
    lri.append(u)
# 入力
firstid = 0
for i in range(n):
    id,left,right = map(int,input().split())
    if n == 0:
        firstid = id
    if left != NIL:
        T[id].left = left
        T[left].parent = id
    if right != NIL:
        T[id].right = right
        T[right].parent = id
r = findroot(firstid)
D = setDepth(r,0)
setHeight(r,H)
leftright(r,lri)
leftroot(r,lro)
rootleft(r,rl)
#挿入
#ここから問題によって変わる
for i in range(n):
    node = i
    parent = T[i].parent
    sibling = getBrother(i)
    degree = getDegree(i)
    depth = D[i]
    height = H[i]
    s = "internal node"
    if i == r:
        s = "root"
    elif degree == 0:
        s = "leaf"
    print(f'node {i}: parent = {parent}, sibling = {sibling}, degree = {degree}, depth = {depth}, height = {height}, {s}')