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 = -1, left = -1, right = -1, depth = 0, height = -1, degree = 0):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.height = height
        self.degree = degree

def input_depth(node, i, n):
    node[i].depth = n
    if node[i].left != -1:
        input_depth(node, node[i].left, n + 1)
    if node[i].right != -1:
        input_depth(node, node[i].right, n + 1)

def input_height(node, i):
    hl = 0
    hr = 0
    if node[i].left != -1:
        input_height(node, node[i].left)
        hl = node[node[i].left].height + 1
    if node[i].right != -1:
        input_height(node, node[i].right)
        hr = node[node[i].right].height + 1
    node[i].height = max(hl, hr)

def print_node(node, i):
    print("node " + str(i) + ": ", end = "")
    print("parent = " + str(node[i].parent) + ", ", end = "")
    if node[i].parent == -1:
        print("sibling = -1, ", end = "")
    elif i == node[node[i].parent].left:
        print("sibling = " + str(node[node[i].parent].right) + ", ", end = "")
    else:
        print("sibling = " + str(node[node[i].parent].left) + ", ", end = "")
    print("degree = " + str(node[i].degree) + ", ", end = "")
    print("depth = " + str(node[i].depth) + ", ", end = "")
    print("height = " + str(node[i].height) + ", ", end = "")
    if node[i].parent == -1:
        print("root")
    elif node[i].degree == 0:
        print("leaf")
    else:
        print("internal node")
        
n = int(input())
ns = [Node() for i in range(n)]
for i in range(n):
    p, l, r = map(int, input().split())
    if l != -1:
        ns[p].left = l
        ns[p].degree += 1
        ns[l].parent = p
    if r != -1:
        ns[p].right = r
        ns[p].degree += 1
        ns[r].parent = p

for i in range(n):
    if ns[i].parent == -1:
        input_depth(ns, i, 0)
        input_height(ns, i)
        break

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

Submission status: Accepted

Solution code:
from enum import Enum, auto
import sys

class NodeType(Enum):
    LEAF = auto()
    INTERNAL_NODE = auto()
    ROOT = auto()

class BinaryTreeNode():
    def __init__(self, parent=None, left=None, right=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.sibling = None
        self.degree = None
        self.depth = None
        self.height = None
        self.type = None

n = int(input())
nodes = [BinaryTreeNode() for i in range(n)]
for i in range(n):
    id, left, right = list(map(int, input().split(' ')))
    degree = 0
    if left != -1:
        degree += 1
        nodes[id].left = left
        nodes[left].parent = id
        nodes[left].sibling = right
    if right != -1:
        degree += 1
        nodes[id].right = right
        nodes[right].parent = id
        nodes[right].sibling = left
    nodes[id].degree = degree
    if degree == 0:
        nodes[id].type = NodeType.LEAF
    else:
        nodes[id].type = NodeType.INTERNAL_NODE

root = 0
for i in range(n):
    if nodes[i].parent == None:
        root = i
        nodes[i].type = NodeType.ROOT

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

def set_height(u):
    h1, h2 = 0, 0
    if nodes[u].left != None:
        h1 = set_height(nodes[u].left) + 1
    if nodes[u].right != None:
        h2 = set_height(nodes[u].right) + 1
    nodes[u].height = h1 if h1 > h2 else h2
    return nodes[u].height

set_depth(root, 0)
set_height(root)

for i in range(n):
    parent = -1 if nodes[i].parent == None else nodes[i].parent
    sibling = -1 if nodes[i].sibling == None else nodes[i].sibling
    type = ''
    if nodes[i].type == NodeType.INTERNAL_NODE:
        type = 'internal node'
    elif nodes[i].type == NodeType.LEAF:
        type = 'leaf'
    elif nodes[i].type == NodeType.ROOT:
        type = 'root'
    print('node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d,'%(i, parent, sibling, nodes[i].degree, nodes[i].depth, nodes[i].height), type)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May 19 19:34:44 2018
ALDS1_7_B
@author: maezawa
"""

n = int(input())

parent = [-1 for _ in range(n)]
left = [-1 for _ in range(n)]
right = [-1 for _ in range(n)]
height = [None for _ in range(n)]
depth = [None for _ in range(n)]

def set_parent():
    global parent
    for i in range(n):
        if left[i] != -1:
            parent[left[i]] = i
        if right[i] != -1:
            parent[right[i]] = i

    
def set_depth(i, p):
    global depth
    if depth[i] != None:
        return
    depth[i] = p
    if right[i] != None:
        set_depth(right[i], p)
    if left[i] != None:
        set_depth(left[i], p+1)
       
def get_depth(i):
    global depth
    if depth[i] != None:
        return depth[i]
    d = 0
    u = i
    while parent[u] != -1:
        u = parent[u]
        d += 1
    depth[i] = d
    return d

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

def get_sib(i):
    if right[parent[i]] == i:
        return left[parent[i]]
    else:
        return right[parent[i]]
    
def get_deg(i):
    deg = 0
    if right[i] != -1:
        deg += 1
    if left[i] != -1:
        deg += 1
    return deg    

def get_height(i):
    return height[i]
    
for i in range(n):
    line = list(map(int, input().split()))
    left[line[0]] = line[1]
    right[line[0]] = line[2]

set_parent()

for i in range(n):
    set_height(i)
    
for i in range(n):
    out_str = 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, '.format(i,parent[i],get_sib(i), get_deg(i), get_depth(i), get_height(i))
    if parent[i] == -1:
        out_str += 'root'
    elif right[i] == -1 and left[i] == -1:
        out_str += 'leaf'
    else:
        out_str += 'internal node'
    print(out_str)

Submission status: Accepted

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


n = int(input())
binary_tree = [Node() for i in range(n)]
h, d = [0 for j in range(n)], [0 for k in range(n)]


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

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


def set_depth(u, dep):
    d[u] = dep
    if binary_tree[u].right != -1:
        set_depth(binary_tree[u].right, dep+1)
    if binary_tree[u].left != -1:
        set_depth(binary_tree[u].left, dep+1)

    return d[u]


def set_sibling(u):
    if binary_tree[binary_tree[u].parent].left != u:
        return binary_tree[binary_tree[u].parent].left
    else:
        return binary_tree[binary_tree[u].parent].right


def set_degree(u):
    cnt = 0
    if binary_tree[u].left != -1:
        cnt += 1
    if binary_tree[u].right != -1:
        cnt += 1
    return cnt


def set_type(u):
    if binary_tree[u].parent == -1:
        return "root"
    elif binary_tree[u].left == -1 and binary_tree[u].right == -1:
        return "leaf"
    else:
        return "internal node"


def main():
    for i in range(n):
        idx, left, right = map(int, input().split())
        binary_tree[idx].left = left
        binary_tree[idx].right = right
        if left != -1:
            binary_tree[left].parent = idx
        if right != -1:
            binary_tree[right].parent = idx

    # 根の探索
    root_idx = 0
    for i in range(n):
        if binary_tree[i].parent == -1:
            root_idx = i
            break

    # 各ノードの高さを求める
    set_height(root_idx)

    # 各ノードの深さを求める
    set_depth(root_idx, 0)

    for i in range(n):
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, "
              "height = {}, {}".format(i, binary_tree[i].parent,
                set_sibling(i), set_degree(i), d[i], h[i], set_type(i)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
root = set(range(n))
binary_tree = [0 for i in range(n)]
#out = [0 for i in range(n)]
for i in range(n):
    l = list(map(int, input().split()))
    binary_tree[l[0]] = l
    s = set(l[1:3])
    root -= s

def binary(id, parent, depth, sibling, height):
    output = {}
    hline = []
    hline.append(height)
    output['node'] = id
    output['parent'] = parent
    output['sibling'] = sibling
    output['depth'] = depth
    left = binary_tree[id][1]
    right = binary_tree[id][2]
    degree = 0
    if(parent == -1):
        output['type'] = 'root'
    elif(left == -1 and right == -1):
        output['type'] = 'leaf'
    else:
        output['type'] = 'internal node'
    if(left != -1):
        degree += 1
        hline.append(binary(left, id, depth+1, right, height))
    if(right != -1):
        degree += 1
        hline.append(binary(right, id, depth+1, left, height))
    max_height = max(hline)
    output['degree'] = degree
    output['height'] = max_height
    binary_tree[id] = output
    return max_height + 1

binary(list(root)[0], -1, 0, -1, 0)
for line in binary_tree:
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(line['node'], line['parent'], line['sibling'], line['degree'], line['depth'], line['height'], line['type']))

Submission status: Accepted

Solution code:
class Tree:
    def __init__(self, ary):
        self.nodes = [
            Node(node, self) for node in sorted(ary, key=lambda x: x[0])
        ]
        [node.set() for node in self.nodes]
        for node in self.nodes:
            if node.parent == -1:
                node.set_depth(0)
                node.set_height()
                break

    def output(self):
        [node.output() for node in self.nodes]


class Node:
    def __init__(self, node, tree):
        self.tree = tree
        self.no = node[0]
        self.left = node[1]
        self.right = node[2]
        self.parent = -1
        self.sibling = -1
        self.degree = 0

    def set(self):
        if self.left > -1:
            self.tree.nodes[self.left].parent = self.no
            if self.right > -1:
                self.tree.nodes[self.right].sibling = self.left
            self.degree += 1

        if self.right > -1:
            self.tree.nodes[self.right].parent = self.no
            if self.left > -1:
                self.tree.nodes[self.left].sibling = self.right
            self.degree += 1

    def set_depth(self, d):
        self.depth = d
        if self.left > -1:
            self.tree.nodes[self.left].set_depth(d + 1)
        if self.right > -1:
            self.tree.nodes[self.right].set_depth(d + 1)

    def set_height(self):
        if self.degree == 0:
            self.height = 0
        else:
            self.tree.nodes[self.right].set_height()
            self.tree.nodes[self.left].set_height()
            self.height = 1 + max(self.tree.nodes[self.right].height,
                                  self.tree.nodes[self.left].height)

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

        print(
            'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.
            format(self.no, self.parent, self.sibling, self.degree, self.depth,
                   self.height, kind))


if __name__ == '__main__':
    # import sys
    n = int(input())
    ary = [[int(_) for _ in input().split()] for i in range(n)]
    tree = Tree(ary)
    tree.output()

Submission status: Accepted

Solution code:
class NullNode():
    def __init__(self):
        self.id = -1

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

    def __str__(self):
        return '{} {} {} {} {}'.format(self.id, self.parent.id, self.left.id, self.right.id, self.sibling.id)

    def getHeight(self, right_height=0, left_height=0):
        if self.left.id != -1:
            left_height += 1
            left_height = self.left.getHeight(left_height, left_height)
        if self.right.id != -1:
            right_height += 1
            right_height = self.right.getHeight(right_height, right_height)
        return max(left_height, right_height)

    def getDepth(self, depth=0):
        if self.parent.id != -1:
            depth += 1
            depth = self.parent.getDepth(depth)
        return depth

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

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

n = int(input())
node_list = [Node(id) for id in range(n)]
for i in range(n):
    [id, left, right] = [int(j) for j in input().split()]
    i_node = node_list[id]
    if left != -1:
        i_node.left = node_list[left]
        node_list[left].parent = node_list[id]
        if right != -1:
            node_list[left].sibling = node_list[right]
    if right != -1:
        i_node.right = node_list[right]
        node_list[right].parent = node_list[id]
        if left != -1:
            node_list[right].sibling = node_list[left]

for id in range(n):
    i_node = node_list[id]
    parent = i_node.parent.id
    sibling = i_node.sibling.id
    degree = i_node.getDegree()
    depth = i_node.getDepth()
    height = i_node.getHeight()
    type = i_node.getType()
    print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}'.format(id, parent, sibling, degree, depth, height, type))

Submission status: Accepted

Solution code:
#coding:utf-8

n = int(input())
T = [list(map(int, input().split())) for i in range(n)]
A = [False for i in range(n)]

class binaryTree:
    def __init__(self, node, x=-1):
        self.node = node
        self.p = x
    
    def partialTree(self,tree,left, right):
        node = tree.node
        if left != -1:
            if A[left]:
                A[left].p = tree
                tree.l = A[left]
            else:
                tree.l = binaryTree(left, node)
                A[left] = tree.l
                tree.l.p = tree
        else:
            tree.l = binaryTree(left, node)
            tree.l.node = -1
            
        if right != -1:
            if A[right]:
                A[right].p = tree
                tree.r = A[right]
            else:
                tree.r = binaryTree(right, node)
                A[right] = tree.r
                tree.r.p = tree
        else:
            tree.r = binaryTree(right, node)
            tree.r.node = -1
            
def searchParent():
    p_tree = A[0]
    while p_tree.p != -1:
        p_tree = p_tree.p
    return p_tree

     
def setHeight(tree):
    h1 = h2 = 0
    if tree.l.node != -1:
        h1 = setHeight(tree.l) + 1
    if tree.r.node != -1:
        h2 = setHeight(tree.r) + 1
    if tree.l.node == -1 and tree.r.node == -1:
        tree.hei = 0
        return 0
    tree.hei = max(h1,h2)
    return max(h1, h2)

def setDepth(tree,depth):
    tree.dep = depth
    depth += 1
    if tree.l.node != -1:
        setDepth(tree.l,depth)

    if tree.r.node != -1:
        setDepth(tree.r,depth)

def getSibling(tree):
    if tree.p == -1:
        return -1
    if tree.p.l.node != -1 and tree.p.l.node != tree.node:
        return tree.p.l.node
    if tree.p.r.node != -1 and tree.p.r.node != tree.node:
        return tree.p.r.node
    return -1

        
def makeTree():
    for i in range(n):
        t = T[i]
        node = t[0]
        left = t[1]
        right = t[2]
        if A[node]:
            tree = A[node]
        else:
            tree = binaryTree(node)
            A[node] = tree
        binaryTree.partialTree(binaryTree, tree,left,right)

makeTree()
p_tree = searchParent()
setHeight(p_tree)
depth = 0
setDepth(p_tree,depth)


for i in range(n):
    tree = A[i]
    tree.sib = getSibling(tree)
    deg = 0
    if tree.r.node != -1:
        deg += 1

    if tree.l.node != -1:
        deg += 1

    if tree.p == -1:
        kind = "root"
    else:
        if deg == 0:
            kind = "leaf"
        else:
            kind = "internal node"

    ID = i
    if tree.p == -1:
        parent = -1
    else:
        parent = tree.p.node
    sibling = tree.sib
    degree = deg
    depth = tree.dep
    height = tree.hei

    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"\
          .format(ID, parent, sibling, degree, depth, height, kind))

Submission status: Accepted

Solution code:
def search(ps, id):
    if ps[id] == -1:
        return 0
    else:
        return 1 + search(ps, ps[id])


def search_h(tree, id):
    if tree[id][0] == -1:
        left = -1
    else:
        left = search_h(tree, tree[id][0])

    if tree[id][1] == -1:
        right = -1
    else:
        right = search_h(tree, tree[id][1])

    return 1 + max(left, right)


n = int(input())
tree = [[] for _ in range(n)]
ps = [-1 for _ in range(n)]
ss = [-1 for _ in range(n)]
for _ in range(n):
    s = input().split()
    id = int(s[0])
    left = int(s[1])
    right = int(s[2])
    tree[id] = [left, right]
    if left >= 0:
        ps[left] = id
        ss[left] = right
    if right >= 0:
        ps[right] = id
        ss[right] = left

for id in range(n):
    p = ps[id]
    s = ss[id]
    deg = int(tree[id][0] >= 0) + int(tree[id][1] >= 0)
    d = search(ps, id)
    h = search_h(tree, id)
    if p == -1:
        type = "root"
    elif tree[id][0] == -1 and tree[id][1] == -1:
        type = "leaf"
    else:
        type = "internal node"

    print("node " + str(id) + ": parent = " + str(p) + ", sibling = " + str(s) + ", degree = " + str(
        deg) + ", depth = " + str(d) + ", height = " + str(h) + ", " + type)

Submission status: Accepted

Solution code:
Parent = 0
Lchild = 1
Rchild = 2

def depth(n):
    if n == -1: return -1
    return depth(parent(n)) + 1

def height(n):
    c1, c2 = childs(n)
    if (c1, c2) == (-1, -1): return 0
    return max(height(c1), height(c2)) + 1

def parent(n):
    return node[n][Parent]

def childs(n):
    return node[n][Lchild:Rchild+1]

def sibling(n):
    c1, c2 = childs(parent(n))
    if c1 == n: return c2
    elif c2 == n: return c1
    return -1

def degree(n):
    return 2 - childs(n).count(-1)

def nt(n):
    if parent(n) == -1:
        return 'root'
    elif degree(n) == 0:
        return 'leaf'
    else:
        return 'internal node'
    return

n = int(input())
node = [[-1, -1, -1] for i in range(n)]
for i in range(n):
    tmp = map(int, raw_input().split())
    j = tmp[0]
    e1, e2 = tmp[1:]
    if e1 != -1:
        node[j][Lchild] = e1
        node[e1][Parent] = j
    if e2 != -1:
        node[j][Rchild] = e2
        node[e2][Parent] = j

for i in range(n):
    msg = 'node {0}: parent = {1}, sibling = {2}, degree = {3}, '+\
          'depth = {4}, height = {5}, {6}'''
    c1 = parent(i)
    c2 = sibling(i)
    c3 = degree(i)
    c4 = depth(i)
    c5 = height(i)
    c6 = nt(i)
    print msg.format(i, c1, c2, c3, c4, c5, c6)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin

FORMAT = ('node {0.id}: parent = {0.parent}, sibling = {0.sibling}, '
          'degree = {0.degree}, depth = {0.depth}, height = {0.height}, '
          '{0.type}').format


class Node(object):
    def __init__(self, data):
        self.id = data[0]
        self.parent = -1
        self.sibling = -1
        self.degree = int(data[1] >= 0) + int(data[2] >= 0)
        #self.childs = [i for i in data[1:] if i > 0]
        self.childs = data[1:]
        self.depth = 0
        self.height = -1
        self.type = 'internal node' if self.degree else 'leaf'

    def __str__(self):
        return FORMAT(self)


def calc_depth(tree, i):
    h = 0
    for k, j in enumerate(tree[i].childs):
        if j >= 0:
            tree[j].depth += 1
            tree[j].sibling = tree[i].childs[1-k]
            h = max(h, calc_depth(tree, j))
    if tree[i].type == 'leaf':
        tree[i].height = 0
    else:
        tree[i].height = h
    return tree[i].height + 1


n = int(stdin.readline())
tree = [-1] * n

for _ in range(n):
    node = Node([int(s) for s in stdin.readline().split()])
    parent = tree[node.id]
    tree[node.id] = node
    if isinstance(parent, int):
        tree[node.id].parent = parent
    else:
        tree[node.id].parent = parent.id
    for i in node.childs:
        if i >= 0:
            if isinstance(tree[i], int):
                tree[i] = node.id
            else:
                tree[i].parent = node.id

for i in range(n):
    calc_depth(tree, i)

for node in tree:
    if node.parent == -1:
        node.type = 'root'
    print(node)

Submission status: Accepted

Solution code:
def getDepth(x):
    global nodes
    p = nodes[x][0]
    c = 0
    while p != -1:
        c += 1
        p = nodes[p][0]

    return c


def getHeight(x):
    global nodes
    h1, h2 = 0, 0
    if nodes[x][1] != -1:
        h1 = getHeight(nodes[x][1])+1
    if nodes[x][2] != -1:
        h2 = getHeight(nodes[x][2])+1

    return max(h1, h2)


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

for i in range(n):
    nodes.append([-1])


for i in range(n):
    a = list(map(int, input().split()))
    if a[1] != -1:
        nodes[a[1]][0] = a[0]
    if a[2] != -1:
        nodes[a[2]][0] = a[0]
    
    nodes[a[0]] += a[1:]

for i in range(n):
    par = nodes[i][0]
    sib = nodes[par][1]

    if nodes[par][1] == i:
        sib = nodes[par][2]

    if par == -1:
        sib = -1

    deg = 0
    if nodes[i][1] != -1:
        deg +=1
    if nodes[i][2] != -1:
        deg +=1

    dep = getDepth(i)
    hei = getHeight(i)

    typ = ' internal node'
    if hei == 0:
        typ = ' leaf'
    if par == -1:
        typ = ' root'

    print('node ' + str(i) + ': parent = ', end= '')
    print(str(par) + ', sibling = ', end= '')
    print(str(sib) + ', degree = ', end= '')
    print(str(deg) + ', depth = ', end= '')
    print(str(dep) + ', height = ', end = '')
    print(str(hei) + ',' + typ)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2**20)

class Node:
    def __init__(self):
        self.id = None
        self.p = None
        self.left = None
        self.right = None
        self.deg = None
        self.att = None
        self.depth = None
        self.height = None
        self.sibling = None

def SetDepth(u, p):
    T[u].depth = p
    pr, pl = 0, 0
    if T[u].right != -1:
        pr = SetDepth(T[u].right, p+1)
    if T[u].left != -1:
        pl = SetDepth(T[u].left, p+1)
    p = max(p, pr, pl)
    T[u].height = p - T[u].depth
    return p

n = int(input())
T = [None] * n
for i in range(n):
    temp = Node()
    T[i] = temp

for i in range(n):
    d = 0
    L = [int(x) for x in input().split()]
    v, l, r = L[0], L[1], L[2]
    T[v].id = v
    T[v].left = l
    T[v].right = r
    if l != -1:
        T[l].p = v
        d += 1
    if r != -1:
        T[r].p = v
        d += 1
    T[v].deg = d 

for i, t in enumerate(T):
    if t.p == None:
        t.att = 'root'
        t.p = -1
        maxd = SetDepth(i, 0)
    elif t.deg == 0:
        t.att = 'leaf'
    else:
        t.att = 'internal node'
    if t.p == -1:
        t.sibling = -1
    else:
        if T[t.p].left == t.id:
            if T[t.p].right == None:
                t.sibling = -1
            else:
                t.sibling = T[t.p].right
        else:
            if T[t.p].left == None:
                t.sibling = -1
            else:
                t.sibling = T[t.p].left

for i in range(n):
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(T[i].id, T[i].p, T[i].sibling, T[i].deg, T[i].depth, T[i].height, T[i].att))

Submission status: Accepted

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

class Node:
    def __init__(self, parent, left, right):
        self.parent = parent
        self.left = left #左の子ノード
        self.right = right #右の子ノード

def get_all_height(T: dict, H: dict, u: int):
    """
    深さ優先探索で各ノードを巡りながらHに高さ情報を容れる
    """
    h_left, h_right = 0, 0
    if T[u].left is not None:
        h_left = get_all_height(T, H, T[u].left) + 1
    if T[u].right is not None:
        h_right = get_all_height(T, H, T[u].right) + 1
    
    ret = max(h_left, h_right)
    H[u] = ret
    return ret

def get_all_depth(T: dict, D: dict, u: int, p: int):
    """
    D: 深さを格納する辞書
    p: 現在の深さ
    """
    D[u] = p
    if T[u].left is not None:
        get_all_depth(T, D, T[u].left, p+1)
    if T[u].right is not None:
        get_all_depth(T, D, T[u].right, p+1)

def ret_sibling(T: dict, u: int):
    """
    ノードuの兄弟を返す
    """
    parent = T[u].parent
    if parent is None:
        return -1 # root は兄弟なし
    # 自分のparentから見て子ノードはleft or rightの二つ。
    # 自分自身(ノードu)に一致していない方を返す
    ret = T[parent].left if T[parent].left != u else T[parent].right
    if ret is None: #兄弟がいない場合
        return -1
    return ret

def ret_degree(T: dict, u: int):
    ret = 2
    if T[u].left is None:
        ret -= 1
    if T[u].right is None:
        ret -= 1
    return ret


# input
n = int(input())
T = {key: Node(None, None, None) for key in range(n)}
for _ in range(n):
    tmp = list(map(int, input().split()))
    if tmp[1] != -1:
        T[tmp[0]].left = tmp[1]
        T[tmp[1]].parent = tmp[0]
    if tmp[2] != -1:
        T[tmp[0]].right = tmp[2]
        T[tmp[2]].parent = tmp[0]

for k, v in T.items():
    if v.parent is None:
        ROOT = k # 根を探す
        break 

D = {}
get_all_depth(T, D, ROOT, 0)
H = {}
get_all_height(T, H, ROOT)

def print_for_a_node(u):
    if T[u].parent is None:
        parent = -1
    else:
        parent = T[u].parent
    
    sib = ret_sibling(T, u)
    deg = ret_degree(T, u)
    node_type = "internal node" if deg != 0 else "leaf"
    if parent == -1:
        node_type = "root"
    
    print(
        f"node {u}: parent = {parent}, sibling = {sib}, degree = {deg}, depth = {D[u]}, height = {H[u]}, {node_type}"
    )

for node in range(n):
    print_for_a_node(node)