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

class binaryTree:

    def __init__(self, datas):
        #format of datas
        #id, left, right
        self.T=[]
        for d in datas:
            self.T.append(node(-1, -1, -1))

        for d in datas:
            self.T[d[0]].left=d[1]
            self.T[d[0]].right=d[2]

        for d in datas:

            id=d[0]
            if(self.T[id].left != -1):
                self.T[self.T[id].left].parent = id
            if (self.T[id].right != -1):
                self.T[self.T[id].right].parent = id

        rootid=-1
        for d in datas:
            if(self.T[d[0]].parent == -1):
                rootid = d[0]
                #print(rootid)

        self.Depth=[-1 for _ in range(len(datas))]
        self.Height=[-1 for _ in range(len(datas))]

        self.setDepth(rootid,0)

        for i in range(len(datas)):
            self.setHeight(i)


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

    def setHeight(self, id):
        h1=0
        h2=0

        if(self.T[id].left != -1):
            h1=self.setHeight(self.T[id].left)+1
        if(self.T[id].right !=-1):
            h2=self.setHeight(self.T[id].right)+1
        self.Height[id]=max(h1,h2)
        return max(h1,h2)

    def getSibring(self,id):
        p=self.T[id].parent
        right=-1
        left=-1

        if(p!=-1):
            right=int(self.T[p].right)
        if(p!=-1):
            left=int(self.T[p].left)

        #print("id="+str(id)+"r="+ str(right) +" l="+str(left))

        if(p == -1):
            return -1
        elif id != left and left != -1 :
            return left
        elif id != right and right != -1 :
            return right
        else:
            return -1


    def printNode(self,id):
        p=self.T[id].parent
        r=self.T[id].right
        l=self.T[id].left

        strs=""
        strs = strs+"node "+ str(id)+":"

        if(p==-1):
            strs=strs+" parent = -1"
        else:
            strs = strs + " parent = " + str(self.T[id].parent)
        strs=strs+", sibling = "+str(self.getSibring(id))

        deg=0
        if(r!=-1):
            deg=deg+1
        if(l!=-1):
            deg=deg+1
        strs=strs+", degree = "+str(deg)
        strs=strs+", depth = "+str(self.Depth[id])
        strs=strs+", height = "+str(self.Height[id])

        if(self.T[id].parent == -1):
            strs=strs+", root"
        elif(self.T[id].right == -1 and self.T[id].left == -1):
            strs=strs+", leaf"
        else:
            strs=strs+", internal node"

        return strs

n=int(input())
dlist=[]
for i in range(n):
    dlist.append(list(map(int,(input().split()))))
t=binaryTree(dlist)
for i in range(n):
    print(t.printNode(i))

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
C = [[] for i in range(n)]
Cnum = [0 for i in range(n)]
P = [-1 for i in range(n+1)]
S = [-1 for i in range(n+1)]
Dep = [0 for i in range(n)]
Deg = [0 for i in range(n)]
H = [0 for i in range(n)]
Typ = ["leaf" for i in range(n)]
for i in range(n):
    id,left,right=map(int,input().split( ))
    C[id] = [left,right]
    P[left] = id
    P[right] = id
    S[left] = right
    S[right] = left
    if left != -1:#完全二分木でなかった
            Deg[id] += 1
            Typ[id] = "internal node"
    if right != -1:
            Deg[id] += 1
            Typ[id] = "internal node"
for i in range(n):
    if P[i] == -1:
        root = i

Typ[root] = "root"

D = deque()
D.append(root)

while len(D)>0:#また-1の扱いがおかしかった
    t = D.popleft()#()忘れてた
    d = Dep[t]
    left = C[t][0]
    right = C[t][1]
    if left != -1:
        D.append(left)
        Dep[left] = d+1
    if right != -1:
        D.append(right)
        Dep[right] = d+1

def height_child(i):
    global C,Cnum,H

    if C[i] == [-1,-1]:
        return [0,0]

    h = max(height_child(C[i][0])[0], height_child(C[i][1])[0])+1
    c = height_child(C[i][0])[1] + height_child(C[i][1])[1] + 2
    H[i] = h
    Cnum[i] = c

    return [h,c]

height_child(root)

#for i in range(n):
#    print(f"node :{i} parent = {P[i]}, sibling = {S[i]}, degree = {Deg[i]}, depth = {Dep[i]}, height = {H[i]}, {Typ[i]}")
for i in range(n):
 print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i,P[i],S[i],Deg[i],Dep[i],H[i],Typ[i]))

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, p=-1, l=-1, r=-1):
        self._p = p
        self._l = l
        self._r = r

T = []
Depth = []
Height = []

def get_sibling(index):
    global T
    if T[index]._p == -1:
        return -1
    if T[T[index]._p]._l != index:
        return T[T[index]._p]._l
    if T[T[index]._p]._r != index:
        return T[T[index]._p]._r
    return -1

def print_node(index):
    global Depth
    global Height
    global T
    
    deg = 0
    if T[index]._l != -1:
        deg += 1
    if T[index]._r != -1:
        deg += 1
    
    print('node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, '%(index, T[index]._p, get_sibling(index), deg, Depth[index], Height[index]), end='')

    if T[index]._p == -1:
        print('root')
    elif T[index]._l == -1 and T[index]._r == -1:
        print('leaf')
    else:
        print('internal node')

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

    for i in range(n):
        T.append(Node(-1, -1, -1))
        Depth.append(-1)
        Height.append(-1)

    for i in range(n):
        index, l_child, r_child = map(int, input().split())
        T[index]._l = l_child
        T[index]._r = r_child
        if l_child != -1:
            T[l_child]._p = index
        if r_child != -1:
            T[r_child]._p = index

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

    def rec(node, dep):
        Depth[node] = dep

        lh = rh = 0
        if T[node]._l != -1:
            lh = rec(T[node]._l, dep + 1) + 1
        if T[node]._r != -1:
            rh = rec(T[node]._r, dep + 1) + 1

        Height[node] = max(lh, rh)
        return Height[node]

    rec(root, 0)

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

Submission status: Accepted

Solution code:
def compute_depth(node: int, depth: int) -> None:
    global trees
    trees[node]["depth"] = depth
    for child in trees[node]["children"]:
        compute_depth(child, depth + 1)


def compute_height(node: int, height: int) -> None:
    global trees
    trees[node]["height"] = height
    parent = trees[node]["parent"]
    if -1 != parent:
        compute_height(parent, height + 1)


if __name__ == "__main__":
    node_num = int(input())
    trees = {idx:
             {"parent": -1, "sibling": -1, "children": [], "depth": 0, "height": 0,
              "node_type": ""} for idx in range(node_num)}

    for _ in range(0, node_num):
        node, *children = map(lambda x: int(x), input().split())
        if (-1 != children[0]) and (-1 != children[1]):
            trees[node]["children"] = children
            trees[children[0]]["sibling"], trees[children[1]]["sibling"] = children[1], children[0]
            trees[children[0]]["parent"] = trees[children[1]]["parent"] = node
        elif [-1, -1] != children:
            child = children[0] * children[1] * (-1)
            trees[node]["children"] = [child]
            trees[child]["parent"] = node

    for node, values in sorted(trees.items(), key=lambda x: x[1]["parent"]):
        if -1 == values["parent"]:
            trees[node]["node_type"] = "root"
            compute_depth(node, 0)
        else:
            if [] == values["children"]:
                trees[node]["node_type"] = "leaf"
            else:
                trees[node]["node_type"] = "internal node"

    for node, values in sorted(filter(lambda x: x[1]["node_type"] == "leaf", trees.items()), key=lambda x: x[1]["depth"]):
        compute_height(node, 0)

    for node, values in trees.items():
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
            node, values["parent"], values["sibling"], len(values["children"]), values["depth"], values["height"], values["node_type"]
        ))

Submission status: Accepted

Solution code:
NIL = -1
MAX = 25


class Node:
    def __init__(self):
        self.parent = NIL
        self.left = NIL
        self.right = NIL
        self.depth = NIL
        self.height = NIL
        self.sibling = NIL


T = [Node() for i in range(MAX)]


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


def set_depth(u, d):
    T[u].depth = d
    if T[u].left != NIL:
        set_depth(T[u].left, d + 1)
    if T[u].right != NIL:
        set_depth(T[u].right, d + 1)


if __name__ == '__main__':
    n = int(raw_input())
    for i in range(n):
        u, left, right = map(int, raw_input().split())
        if left != NIL:
            T[left].parent = u
            T[u].left = left
        if right != NIL:
            T[right].parent = u
            T[u].right = right
        if left != NIL and right != NIL:
            T[left].sibling = right
            T[right].sibling = left

    # find root
    root = 0
    for i in range(n):
        if T[i].parent == NIL:
            root = i
            break
   # print "root=", root

    set_height(root)
    set_depth(root, 0)
    for i in range(n):
        print "node %d: parent = %d, sibling = %d," % (
            i, T[i].parent, T[i].sibling),

        degree = 0
        if T[i].left != NIL:
            degree += 1
        if T[i].right != NIL:
            degree += 1
        print "degree = %d," % degree,

        print "depth = %d, height = %d," % (T[i].depth, T[i].height),

        if T[i].parent == NIL:
            print "root"
        elif T[i].left == NIL and T[i].right == NIL:
            print "leaf"
        else:
            print "internal node"

Submission status: Accepted

Solution code:
class Node_information():
    def __init__(self):
        self.id = -1
        self.parent = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = ""
        self.left = -1
        self.right = -1
        self.sibling = -1

def get_tree_id_type(left, right):
    if left == -1 and right == -1:
        return "leaf"
    else:
        return "internal node"

def get_tree_id_degree(left, right):
    if left == -1 and right == -1:
        return 0
    elif left != -1 and right != -1:
        return 2
    else:
        return 1

def get_depth(tree_information, now_id, now_depth):
    tree_information[now_id].depth = now_depth
    if tree_information[now_id].left != -1:
        get_depth(tree_information, tree_information[now_id].left, now_depth + 1)
    if tree_information[now_id].right != -1:
        get_depth(tree_information, tree_information[now_id].right, now_depth + 1)

def get_height(tree_information, now_id):
    h1 = 0
    h2 = 0
    if tree_information[now_id].left != -1:
        h1 = get_height(tree_information, tree_information[now_id].left)
    if tree_information[now_id].right != -1:
        h2 = get_height(tree_information, tree_information[now_id].right)
    tree_information[now_id].height = max(h1,h2)
    return tree_information[now_id].height + 1

def print_tree_information(tree_information, N):
    for i in range(N):
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
        .format(tree_information[i].id,tree_information[i].parent,tree_information[i].sibling,tree_information[i].degree,
        tree_information[i].depth,tree_information[i].height,tree_information[i].type))

def main():
    N = int(input())
    tree_information = list()
    for i in range(N):
        tree_information.append(Node_information())
    for i in range(N):
        information = [int(i) for i in input().split()]
        tree_information[information[0]].id = information[0]
        tree_information[information[0]].left = information[1]
        tree_information[information[0]].right = information[2]
        if information[1] != -1:
            tree_information[information[1]].parent = information[0]
        if information[2] != -1:
            tree_information[information[2]].parent = information[0]
        if information[1] != -1 and information[2] != -1:
            tree_information[information[1]].sibling = information[2]
            tree_information[information[2]].sibling = information[1]
        tree_information[information[0]].type = get_tree_id_type(tree_information[information[0]].left,tree_information[information[0]].right)
        tree_information[information[0]].degree = get_tree_id_degree(tree_information[information[0]].left,tree_information[information[0]].right)
    for i in range(N):
        if tree_information[i].parent == -1:
            tree_information[i].type = "root"
            get_depth(tree_information,i,0)
            break
    for i in range(N):
        if tree_information[i].type == "root":
            get_height(tree_information,i)
            break
    print_tree_information(tree_information,N)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Node2:
    def __init__(self):
        self.parent = -1
        self.left = -1
        self.right = -1
    
def getSibling(u):
    if Nodes[u].parent == -1:
        return -1
    p = Nodes[u].parent
    if Nodes[p].left == u:
        return Nodes[p].right
    else:
        return Nodes[p].left

def getDepth(u):
    depth = 0
    while Nodes[u].parent != -1:
        depth += 1
        u = Nodes[u].parent
        
    return depth

def getDegree(u):
    if Nodes[i].left != -1 and Nodes[i].right != -1:
        return 2
    elif Nodes[i].left == -1 and Nodes[i].right == -1:
        return 0
    else:
        return 1

def getHeight(u):
    a = 0
    b = 0
    if Nodes[u].left != -1:
        a = getHeight(Nodes[u].left) + 1
    if Nodes[u].right != -1:
        b = getHeight(Nodes[u].right) + 1
    return max(a, b)

def getType(u):
    if Nodes[u].parent == -1:
        return "root"
    elif Nodes[u].right != -1 or Nodes[u].left != -1:
        return "internal node"
    else:
        return "leaf"
    
def printNode(u):
    print_str = "node " + str(u) + ": parent = " + str(Nodes[u].parent) + ", "
    print_str = print_str + "sibling = " + str(getSibling(u)) + ", "
    print_str = print_str + "degree = " + str(getDegree(u)) + ", "
    print_str = print_str + "depth = " + str(getDepth(u)) + ", "
    print_str = print_str + "height = " + str(getHeight(u)) + ", " + getType(u)
    print(print_str)
    
        

    
# 入力
n = int(input())

Nodes = []
for i in range(n):
    tmp_obj = Node2()
    Nodes.append(tmp_obj)

# 登録作業
for i in range(n):
    num, left, right = map(int, input().split())
    Nodes[num].left = left
    Nodes[num].right = right
    if left != -1:
        Nodes[left].parent = num
    if right != -1:
        Nodes[right].parent = num
    
# 出力
for i in range(n):
    printNode(i)

Submission status: Accepted

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


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


def main():
    n = int(input())
    global Nodes
    Nodes = [Node() for i in range(n)]

    for i in range(n):
        id, *children = map(int, input().split())
        left = children[0]
        right = children[1]
        if left != -1 and right != -1:
            Nodes[id].type = "internal node"
            Nodes[id].degree = 2
            Nodes[id].left = left
            Nodes[id].right = right
            Nodes[left].sibling = right
            Nodes[right].sibling = left
        elif left != -1 or right != -1:
            Nodes[id].type = "internal node"
            Nodes[id].degree = 1
            if left != -1:
                Nodes[id].left = left
            else:
                Nodes[id].left = right
        else:
            Nodes[id].type = "leaf"
            Nodes[id].degree = 0
        for child in children:
            if child != -1:
                Nodes[child].parent = id

    rootid = ""
    for i, node in enumerate(Nodes):
        if node.parent == -1:
            rootid = i
    Nodes[rootid].type = "root"
    dfs(rootid)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def calc_height(list_child, id_now):
    height_left = 0
    height_right = 0

    id_child_left = list_child[id_now][0]
    if id_child_left != -1:
        height_left = calc_height(list_child, id_child_left) + 1
    
    id_child_right = list_child[id_now][1]
    if id_child_right != -1:
        height_right = calc_height(list_child, id_child_right) + 1

    return max(height_left, height_right)


# INPUT
n = int(input())


list_child = [[] for _ in range(n)]
list_parent = [-1 for _ in range(n)]

for _ in range(n):

    id, *C = map(int, input().split())

    list_child[int(id)].extend(C)

    for c in C:
        if c == -1:
            continue

        list_parent[int(c)] = int(id)


# PROCESS, OUTPUT
for id in range(n):

    parent = list_parent[id]

    if parent == -1:
        sibling = -1
    else:
        if list_child[parent][0] == id:
            sibling = list_child[parent][1]
        else:
            sibling = list_child[parent][0]

    degree = 2 - list_child[id].count(-1)

    depth = 0
    parent_now = parent

    while parent_now != -1:
        depth += 1
        parent_now = list_parent[parent_now]


    if depth == 0:
        type_node = "root"
        height = calc_height(list_child, id)
    elif list_child[id][0] == list_child[id][1] == -1:
        type_node = "leaf"
        height = 0
    else:
        type_node = "internal node"
        height = calc_height(list_child, id)

    print(f"node {id}: parent = {parent}, sibling = {sibling}, degree = {degree}, depth = {depth}, height = {height}, {type_node}")

Submission status: Accepted

Solution code:
n = int(input())

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

    def setChildNodes(self, r, l):
        self.right = r
        self.left = l
        if r == -1 and l == -1:
            self.degree = 0
        elif r != -1 and l != -1:
            self.degree = 2
        else:
            self.degree = 1

    def setParent(self, parent):
        self.parent = parent

    def getParent(self):
        return self.parent

    def setSibling(self, sibling):
        self.sibling = sibling

    def recDepth(self, depth, nodes):
        self.depth = depth
        rheight = -1
        lheight = -1
        if self.right != -1:
            rheight = nodes[self.right].recDepth(self.depth + 1, nodes)
        if self.left != -1:
            lheight = nodes[self.left].recDepth(self.depth + 1, nodes)
        if self.right == -1 and self.left == -1:
            self.height = 0
        elif rheight > lheight:
            self.height = rheight + 1
        else:
            self.height = lheight + 1

        return self.height

    def printInfo(self):
        info = ''
        if self.parent == -1:
            info = 'root'
        elif self.degree == 0:
            info = 'leaf'
        else:
            info = 'internal node'

        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
              self.id, self.parent, self.sibling, self.degree,
              self.depth, self.height, info))

nodes = []

for i in range(n):
    nodes.append(Node(i, -1, -1))

for i in range(n):
    arr = list(map(int, input().split()))
    nodes[arr[0]].setChildNodes(arr[1], arr[2])
    if arr[1] != -1:
        nodes[arr[1]].setParent(arr[0])
    if arr[2] != -1:
        nodes[arr[2]].setParent(arr[0])
    if arr[1] != -1 and arr[2] != -1:
        nodes[arr[1]].setSibling(arr[2])
        nodes[arr[2]].setSibling(arr[1])

for i in range(n):
    if nodes[i].getParent() == -1:
        root = nodes[i]

root.recDepth(0, nodes)

for node in nodes:
    node.printInfo()

Submission status: Accepted

Solution code:
NIL = -1


class Node():
    def __init__(self, p, l, r):
        self.p = p
        self.l = l
        self.r = r
        self.s = NIL
        self.deg = NIL
        self.dep = NIL
        self.h = NIL


def set_attr(u):
    def set_height(u_):
        h1 = 0
        h2 = 0
        if T[u_].l != NIL:
            h1 = set_height(T[u_].l) + 1
        if T[u_].r != NIL:
            h2 = set_height(T[u_].r) + 1
        res = h1 if h1 > h2 else h2
        T[u_].h = res
        return res

    def set_depth(u_, d):
        if u_ == NIL:
            return
        T[u_].dep = d
        set_depth(T[u_].l, d + 1)
        set_depth(T[u_].r, d + 1)

    set_height(u)
    set_depth(u, 0)


N = int(input())
T = [Node(NIL, NIL, NIL) for _ in range(N)]
for _ in range(N):
    n, l, r = map(int, input().split())
    T[n].l = l
    T[n].r = r
    deg = 0
    if l != NIL:
        T[l].p = n
        deg += 1
    if r != NIL:
        T[r].p = n
        deg += 1
    if l != NIL and r != NIL:
        T[r].s = l
        T[l].s = r
    T[n].deg = deg
root = 0
for n, t in enumerate(T):
    if t.p == NIL:
        root = n
set_attr(root)
for n, t in enumerate(T):
    if t.p == NIL:
        type_ = 'root'
    elif t.l == NIL and t.r == NIL:
        type_ = 'leaf'
    else:
        type_ = 'internal node'
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, '
          'height = {}, {}'.format(n, t.p, t.s, t.deg, t.dep, t.h, type_))

Submission status: Accepted

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

nodedict = {}

class Node:
    def __init__(self, id, left, right):
        self.id = id
        self.parent = -1
        self.depth = -1
        self.sibling = -1
        self.height = -1
        self.left = left
        self.right = right
        self.degree = 0
        if left != -1:
            self.degree += 1
        if right != -1:
            self.degree += 1

    def __repr__(self):
        return str(self.__dict__)

    def get_height(self):
        if self.height != -1:
            pass
        else:
            if self.degree == 0:
                self.height = 0
            else:
                lh, rh = 0, 0
                if self.left != -1:
                    lh = nodedict[self.left].get_height()
                if self.right != -1:
                    rh = nodedict[self.right].get_height()
                self.height = max(lh, rh) + 1

        return self.height

def assign_info(node, current_depth):
    node.depth = current_depth
    if node.left != -1:
        left = nodedict[node.left]
        left.parent = node.id
        left.sibling = node.right
        assign_info(left, current_depth + 1)

    if node.right != -1:
        right = nodedict[node.right]
        right.parent = node.id
        right.sibling = node.left
        assign_info(right, current_depth + 1)

def solve():
    n = int(input())

    # Node作成
    childlist = []
    for i in range(n):
        id, left, right = map(int, input().split())
        nodedict[id] = Node(id, left, right)
        childlist.append(left)
        childlist.append(right)


    # 根を探す
    rootid = -1
    for i in range(n):
        if i not in childlist:
            rootid = i

    # 根から順に情報割り当て
    assign_info(nodedict[rootid], 0)

    # 高さ割り当て
    for i in range(n):
        nodedict[i].get_height()

    # 出力
    for i in range(n):
        node = nodedict[i]
        if node.depth == 0:
            type = "root"
        elif node.height == 0:
            type = "leaf"
        else:
            type = "internal node"

        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
            node.id, node.parent, node.sibling, node.degree, node.depth, node.height, type))

solve()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, idnum):
        self.id = idnum
        self.parent = -1
        self.left = -1
        self.right = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = "root"
#input
n = int(input())
T = [Node(i) for i in range(n)]
for ni in range(n):
    idnum, left, right = [int(i) for i in input().split()]
    T[idnum].left = left
    T[idnum].right = right
    T[idnum].degree = 2 - [left, right].count(-1)
    if left != -1:
        T[left].parent = idnum
        T[left].sibling = right
    if right != -1:
        T[right].parent = idnum
        T[right].sibling = left


#teach node type
leaf_id = []
for ni in range(n):
    if T[ni].parent == -1:
        T[ni].type = "root"
        root_id = ni
    elif T[ni].degree == 0:
        T[ni].type = "leaf"
        leaf_id.append(ni)
    else:
        T[ni].type = "internal node"

def setDepth(p, d):
    T[p].depth = d
    if T[p].left != -1:
        setDepth(T[p].left, d+1)
    if T[p].right != -1:
        setDepth(T[p].right, d+1)
setDepth(root_id,0)

def setHeight(p, h):
    if T[p].height < h:
        T[p].height = h
    if T[p].parent != -1:
        setHeight(T[p].parent, h+1)

for l in leaf_id:
    setHeight(l, 0)

#output
for ni in range(n):
    print("node "+str(T[ni].id)+\
        ": parent = "+str(T[ni].parent)+\
            ", sibling = "+str(T[ni].sibling)+\
                ", degree = "+str(T[ni].degree)+\
                    ", depth = "+str(T[ni].depth)+\
                        ", height = "+str(T[ni].height)+\
                            ", "+T[ni].type)

Submission status: Accepted

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

def get_depth(u, p):
  D[u] = p
  if result[u].right is not None:
    get_depth(result[u].right, p)
  if result[u].left is not None:
    get_depth(result[u].left, p+1)

def get_depth_1(u, p):
  i = u
  d = 0
  while result[u].parent != -1:
    u = result[u].parent
    d += 1
  D[i] = d

def get_hight(H, u):
  lh, rh = 0, 0
  if result[u].left != -1:
    lh = get_hight(H, result[u].left)+1
  if result[u].right != -1:
    rh = get_hight(H, result[u].right)+1

  H[u] = max(lh, rh)
  return H[u]

n = int(input())
node  = [list(map(int, input().split())) for _ in range(n)] 
result = [Node() for _ in range(n)]
D = [0 for _ in range(n)]
H = [0 for _ in range(n)]


def initiate(li):
  for l in li:
    n = l[0]
    left = l[1]
    right = l[2]
    if left != -1:
      result[left].parent = n
      result[n].left = left
    if right != -1:
      result[right].parent = n
      result[n].right = right


initiate(node)

for u in range(n):
  get_depth_1(u, 0)
  
for u in range(n):
    get_hight(H, u)

final = []

for i in range(n):
  node = i 
  parent = result[node].parent 
  depth = D[i]
  height = H[i]
  degree = 0
  if result[node].left == -1 and result[node].right == -1:
    typ = "leaf"
    degree = 0
  elif result[node].left >= 0 and result[node].right >= 0:
    typ = "internal node"
    degree = 2
  else:
    degree = 1
    typ = "internal node"

  if parent == -1:
    typ = "root"
  if result[parent].left == node:
    sibling = result[parent].right
  else:
    sibling = result[parent].left
  print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(node, parent, sibling, degree, depth, height, typ))