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, depth, height):
        self.p = parent
        self.l = left
        self.r = right
        self.d = depth
        self.h = height

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

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

def getDegree(u):
    degree = 0
    if T[u].r != -1:
        degree += 1
    if T[u].l != -1:
        degree += 1
    return degree

def getSibling(u):
    if T[u].p == -1:
        return -1
    if T[T[u].p].l != u and T[T[u].p].l != -1:
        return T[T[u].p].l
    if T[T[u].p].r != u and T[T[u].p].r != -1:
        return T[T[u].p].r
    return -1    

n = int(input())
T = [node(-1, -1, -1, 0, 0) for _ in range(n)]
for _ in range(n):
    info = list(map(int, input().split(" ")))
    T[info[0]].l = info[1]
    T[info[0]].r = info[2]
    if info[1] != -1:
        T[info[1]].p = info[0]
    if info[2] != -1:
        T[info[2]].p = info[0]

for x in T:
    if x.p == -1:
        setDepth(T.index(x), 0)
        setHeight(T.index(x))

for i in range(n):
    print("node", end = ' ')
    print(i, end = ': ')
    print("parent =", end = ' ')
    print(T[i].p, end = ', ')
    print("sibling =", end = ' ')
    print(getSibling(i), end = ', ')
    print("degree =", end = ' ')
    print(getDegree(i), end = ', ')
    print("depth =", end = ' ')
    print(T[i].d, end = ', ')
    print("height =", end = ' ')
    print(T[i].h, end = ', ')
    if T[i].p == -1: print("root")
    elif T[i].r == -1 and T[i].l == -1: print("leaf")
    else: print("internal node")

Submission status: Accepted

Solution code:
n = int(input())
NIL = -1
class Node():
    def __init__(self):
        self.D = [0] * 10000
        self.H = [0] * 10000
        self.parent = [0] * 10000
        self.left = [0] * 10000
        self.right = [0] * 10000
        
    def setdepth(self, u, d):
        if u == NIL:
            return
        self.D[u] = d
        self.setdepth(self.left[u], d + 1)
        self.setdepth(self.right[u], d + 1)
    
    def setheight(self, u):
        h1 = 0
        h2 = 0
        if T.left[u] != NIL:
            h1 = self.setheight(T.left[u]) + 1
        if T.right[u] != NIL:
            h2 = self.setheight(T.right[u]) + 1
        self.H[u] = max(h1, h2)
        return self.H[u]
    
    def getsibling(self, u):
        if self.parent[u] == NIL:
            return NIL
        if self.left[self.parent[u]] != u and self.left[self.parent[u]] != NIL:
            return self.left[self.parent[u]]
        if self.right[self.parent[u]] != u and self.right[self.parent[u]] != NIL:
            return self.right[self.parent[u]]
        return NIL
    
    def printf(self, u):
        if self.parent[u] == NIL:
            s = 'root'
        elif self.left[u] == NIL and self.right[u] == NIL:
            s = 'leaf'
        else:
            s = 'internal node'
        
        deg = 0
        if self.left[u] != NIL:
            deg += 1
        if self.right[u] != NIL:
            deg += 1
        
        print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'\
              .format(u, self.parent[u], self.getsibling(u), deg, self.D[u], self.H[u], s))
        
        
T = Node()
for i in range(n):
    T.parent[i] = NIL

for i in range(n):
    v, l, r = (int(x) for x in input().split())
    T.left[v] = l
    T.right[v] = r
    if l != NIL:
        T.parent[l] = v
    if r != NIL:
        T.parent[r] = v

for i in range(n):
    if (T.parent[i] == NIL):
        root = i

T.setdepth(root, 0)
T.setheight(root)

for i in range(n):
    T.printf(i)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7/ALDS1_7_B


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  # Noneによって代入されなかったとき用
    # 本では右から左の方に探索していったけど
    # キモいのでここでは左から右に探索していくことにする
    if T[u].left is not None:
        h_left = get_all_height(T, H, T[u].left) + 1
    if T[u].right is not None:
        h_right = get_all_height(T, H, T[u].right) + 1
    ret = max(h_left, h_right)
    H[u] = ret
    return ret


def get_all_depth(T, D: dict, u, p: int):
    '''
    まあHがわかってればdepthに変換可能なんだけど練習のために再帰関数で実装する。

    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, u):
    '''
    一度親を経由すれば良い
    '''
    parent = T[u].parent
    if parent is None:
        return -1  # 根は
    ret = T[parent].left if T[parent].left != u else T[parent].right
    if ret is None:
        return -1
    return ret


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


# データを読み込む
n = int(input())
T = {key: Node(None, None, None) for key in range(n)}  # 初期化
for _ in range(n):
    tmp = list(map(int, input().split()))
    # 左から処理
    if tmp[1] != -1:
        T[tmp[0]].left = tmp[1]  # 子の代入
        T[tmp[1]].parent = tmp[0]  # 親の代入
    if tmp[2] != -1:
        T[tmp[0]].right = tmp[2]  # 子の代入
        T[tmp[2]].parent = tmp[0]  # 親の代入

# 根の探索
for k, v in T.items():
    if v.parent is None:
        ROOT = k
        break
else:
    raise ValueError("ROOTが存在しないなんておかしい")

# 深さと高さの探索
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)

Submission status: Accepted

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

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


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


if __name__ == "__main__":
	n = int(input())
	T = []
	for _ in range(n):
		T.append(Node())
	for _ in range(n):
		id, left, right = map(int, input().split())
		T[id].left = left
		T[id].right = right
		if left != -1:
			T[left].sibling = right
			T[left].parent = id
		if right != -1:
			T[right].sibling = left
			T[right].parent = id
	
	for i in range(n):
		if T[i].left == -1:
			T[i].degree -= 1
		if T[i].right == -1:
			T[i].degree -= 1
		if T[i].left == -1 and T[i].right == -1:
			T[i].type = "leaf"
		if T[i].parent == -1:
			root_id = i
			T[i].type = "root"

	setDepth(root_id, 0)
	setHeight(0, root_id)

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

Submission status: Accepted

Solution code:
class node():
    def __init__(self, id, parent, child, depth, type_t, sibling, height=0):
        self.id = id
        self.parent = parent
        self.child = child
        self.depth = depth
        self.type_t = type_t
        self.sibling = sibling
        self.height = height


def add(t, d, i, parent, depth, sibling):
    type_t = 'internal node'
    if d[i][1] == -1 and d[i][2] == -1:
        type_t = 'leaf'
    if depth == 0:
        type_t = 'root'

    child = []
    if d[i][1] >= 0:
        child.append(d[i][1])
    if d[i][2] >= 0:
        child.append(d[i][2])

    new_node = node(i, parent, child, depth, type_t, sibling)
    t.append(new_node)
    sib = -1
    if len(child) == 1:
        add(t, d, child[0], i, depth + 1, sib)
    elif len(child) == 2:
        add(t, d, child[0], i, depth + 1, child[1])
        add(t, d, child[1], i, depth + 1, child[0])


def calc_height(t, i):
    if len(t[i].child) == 0:
        return 0
    max_h = -1
    for c in t[i].child:
        max_h = max(max_h, calc_height(t, c))
    return max_h + 1


N = int(input())
tree = []
data = [[] for i in range(N)]
for i in range(N):
    data[i] = [int(i) for i in input().split()]

data.sort(key=lambda x: x[0])
root = [True for i in range(N)]
for d in data:
    for c in d[1:]:
        if c == -1:
            continue
        root[c] = False

root_index = root.index(True)
add(tree, data, root_index, -1, 0, -1)

tree.sort(key=lambda x: x.id)

for i in range(N):
    h = calc_height(tree, i)
    tree[i].height = h


for t in tree:
    print(f'node {t.id}: parent = {t.parent}, sibling = {t.sibling},'
          f' degree = {len(t.child)}, depth = {t.depth},'
          f' height = {t.height}, {t.type_t}')

Submission status: Accepted

Solution code:
class BinaryTree:
    def __init__(self, node, children):
        self.node = node
        for i in range(2):
            try:
                children.remove(-1)
            except:
                pass
            
        self.children = children
        self.parent = -1
        try:
            self.sibling = self.parent.children.remove(self.node)[0]
        except:
            self.sibling = -1
        
        self.degree = len(children)
        self.depth = 0
        self.height = 0
        if len(children) == 0:    #子が両方とも-1の場合
            self.status = "leaf"
        else:
            self.status="root"
    
    def display(self):
        print("""node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s"""
             %(self.node, self.parent, self.sibling, self.degree, self.depth, self.height, self.status))

n = int(input())
NODE_DICT = {}
root_search = {}
for loop in range(n):
    tmp_input = list(map(int, input().split()))
    tmp = BinaryTree(tmp_input[0], tmp_input[1:])
    NODE_DICT[tmp_input[0]] = tmp
    root_search[tmp_input[0]] = True
    
for loop in range(n):
    for element in NODE_DICT[loop].children:
        root_search[element] = False

for element in range(n):
    if root_search[element]:
        root = element

def Process(NODE_DICT, node, depth):
    
    NODE_DICT[node].depth = depth
    
    if len(NODE_DICT[node].children) != 0:
        if depth != 0:
            NODE_DICT[node].status = "internal node"
        height_list = []
        if len(NODE_DICT[node].children) == 2:
            NODE_DICT[NODE_DICT[node].children[0]].sibling, NODE_DICT[NODE_DICT[node].children[1]].sibling \
            = NODE_DICT[node].children[1], NODE_DICT[node].children[0]
        
        for child in NODE_DICT[node].children:
            NODE_DICT[child].parent = NODE_DICT[node].node
            Process(NODE_DICT, child, depth+1)
            height_list.append(NODE_DICT[child].height+1)
            
        NODE_DICT[node].height = max(height_list)
        
    else:
        if depth == 0:
            NODE_DICT[node].status = "root"
        NODE_DICT[node].height = 0
    
Process(NODE_DICT, root, 0)

for loop in range(len(NODE_DICT)):
    NODE_DICT[loop].display()

Submission status: Accepted

Solution code:
# ALDS1_7_B Binary Tree
import sys


class Node:
    def __init__(self):
        self.parent = -1
        self.left = None
        self.right = None
        self.height = None
        self.depth = None
        self.sibling = -1
        self.type = 'internal node'
        self.deg = 0


def calc_depth(A, i):
    if A[i].depth:
        return A[i].depth

    if A[i].parent == -1:
        A[i].depth = 0
    else:
        A[i].depth = calc_depth(A, A[i].parent) + 1
    return A[i].depth


def calc_height(A, i):
    if A[i].height:
        return A[i].height

    if (A[i].left == -1) & (A[i].right == -1):
        A[i].height = 0
        return A[i].height

    if A[i].left == -1:
        A[i].height = calc_height(A, A[i].right) + 1
    elif A[i].right == -1:
        A[i].height = calc_height(A, A[i].left) + 1
    else:
        A[i].height = max(calc_height(A, A[i].left), calc_height(A, A[i].right)) + 1

    return A[i].height


n = int(input())

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

for i in range(n):
    A = list(map(int, sys.stdin.readline().strip().split()))
    tree[A[0]].left = A[1]
    tree[A[0]].right = A[2]
    if A[1] != -1:
        tree[A[1]].parent = A[0]
        tree[A[1]].sibling = A[2]
        tree[A[0]].deg += 1
    if A[2] != -1:
        tree[A[2]].parent = A[0]
        tree[A[2]].sibling = A[1]
        tree[A[0]].deg += 1
    if (A[1] == -1) & (A[2] == -1):
        tree[A[0]].type = 'leaf'

for i in range(n):
    calc_depth(tree, i)
    height = calc_height(tree, i)
    if tree[i].parent == -1:
        node_type = 'root'
    else:
        node_type = tree[i].type

    print('node {}: parent = {}, sibling = {},'
          ' degree = {}, depth = {}, height = {}, {}'.format(i, tree[i].parent, tree[i].sibling,
                                                             tree[i].deg, tree[i].depth, height,
                                                             node_type))

Submission status: Accepted

Solution code:
n = int(input())

nodes = []
for _ in range(n):
    x = list(map(int, input().split()))
    nodes.append(x)
    
class Tree:
    def __init__(self, n):
        # n : ノード数
        # sibling : 兄弟
        self.nodes = {node: {'parent': None, 'children': [], 'depth': None, 'height': None, 'sibling': None} for node in range(n)}
        
    def add_node_with_child(self, node, childlen):
        for c in childlen:
            self.nodes[node]['children'].append(c)
            self.nodes[c]['parent'] = node
    
    def get_parent(self, node):
        return self.nodes[node]['parent']
    
    def get_children(self, node):
        return self.nodes[node]['children']
        
    def get_depth(self, node):
        if self.nodes[node]['depth'] != None:
            return self.nodes[node]['depth']
        elif self.nodes[node]['parent'] == None:
            self.nodes[node]['depth'] = 0
            return 0
        else:
            depth = self.get_depth(self.nodes[node]['parent']) + 1
            self.nodes[node]['depth'] = depth
            return depth
        
    def get_height(self, node):
        if self.nodes[node]['height'] != None:
            return self.nodes[node]['height']
        elif len(self.nodes[node]['children']) == 0:
            self.nodes[node]['height'] = 0
            return 0
        elif self.nodes[node]['height'] == None:
            children = self.nodes[node]['children']
            children_h = [self.get_height(c)+1 for c in children]
            self.nodes[node]['height'] = max(children_h)
            return self.nodes[node]['height']
        
    def get_sibling(self, node):
        if self.nodes[node]['sibling'] != None:
            return self.nodes[node]['sibling']
        elif self.nodes[node]['parent'] == None:
            self.nodes[node]['sibling'] = []
            return self.nodes[node]['sibling']
        else:
            p = self.nodes[node]['parent']
            sibling = set(self.get_children(p))
            sibling.remove(node)
            self.nodes[node]['sibling'] = list(sibling)
            return self.nodes[node]['sibling']
        
RootedTree = Tree(n)
for t in nodes:
    node = t[0]
    childlen = []
    if t[1] != -1:
        childlen.append(t[1])
    if t[2] != -1:
        childlen.append(t[2])
    RootedTree.add_node_with_child(node, childlen)
    
for node in range(n):
    parent = RootedTree.get_parent(node)
    if parent == None:
        parent = -1
    depth = RootedTree.get_depth(node)
    height = RootedTree.get_height(node)
    childlen = RootedTree.get_children(node)
    degree = len(childlen)
    childlen = ', '.join(list(map(str, childlen)))
    sibling = RootedTree.get_sibling(node)
    if len(sibling) == 0:
        sibling = -1
    else:
        sibling = sibling[0]
    
    if parent == -1:
        node_type = 'root'
    elif childlen == '':
        node_type = 'leaf'
    else:
        node_type = 'internal node'
    
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(node, parent, sibling, degree, depth, height, node_type))

Submission status: Accepted

Solution code:
class Node:

    def __init__(self, _id):
        self.id = _id
        self.left = None
        self.right = None
        self.parent = None

    def add_left(self, node):
        node.parent = self
        self.left = node

    def add_right(self, node):
        node.parent = self
        self.right = node

    @property
    def parent_id(self):
        if self.parent is None:
            return -1
        else:
            return self.parent.id

    @property
    def deg(self):
        count = 0
        if self.right is not None:
            count += 1
        if self.left is not None:
            count += 1
        return count

    @property
    def sibling_id(self):
        if self.parent is None or self.parent.deg == 1:
            return -1
        else:
            if self.parent.left == self:
                return self.parent.right.id if self.parent.right is not None else -1
            else:
                return self.parent.left.id if self.parent.left is not None else -1

    @property
    def node_type(self):
        if self.parent is None:
            return 'root'
        if self.left is None and self.right is None:
            return 'leaf'
        return 'internal node'

    @property
    def height(self):
        if self.left is None:
            left = -1
        else:
            left = self.left.height
        if self.right is None:
            right = -1
        else:
            right = self.right.height
        return max(left, right) + 1

    @property
    def depth(self):
        if self.parent is None:
            return 0
        else:
            return self.parent.depth + 1

    def __eq__(self, other):
        return self.id == other.id

    def __repr__(self):
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
            self.id, self.parent_id, self.sibling_id, self.deg, self.depth, self.height, self.node_type)


def main():
    n = int(input())
    nodes = [Node(i) for i in range(n)]
    for _ in range(n):
        ID, left, right = map(int, input().split(' '))
        if left != -1:
            nodes[ID].add_left(nodes[left])
        if right != -1:
            nodes[ID].add_right(nodes[right])
    for node in nodes:
        print(node)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class Node:
    def __init__(self):
        self.parent = -1
        self.left = -1
        self.right = -1
        self.sibling = -1
        self.typ = "leaf"
        self.degree = 0

def getDepth(G, v, d=0):
    G[v].depth = d
    if G[v].right != -1:
        getDepth(G, G[v].right, d+1)
    if G[v].left != -1:
        getDepth(G, G[v].left, d+1)

def getHeight(G, v):
    h1, h2 = 0, 0
    if G[v].right != -1:
        getHeight(G, G[v].right)
        h1 = G[G[v].right].height + 1
    if G[v].left != -1:
        getHeight(G, G[v].left)
        h2 = G[G[v].left].height + 1
    G[v].height = max(h1, h2)

def main():
    n = int(input())
    G = [Node() for _ in range(n)]
    for _ in range(n):
        idx, l, r = map(int, input().split())
        G[idx].left = l
        G[idx].right = r
        if l != -1:
            G[l].parent = idx
            G[idx].typ = "internal node"
            G[idx].degree += 1
        if r != -1:
            G[r].parent = idx
            G[idx].typ = "internal node"
            G[idx].degree += 1
        if l != -1 and r != -1:
            G[l].sibling = r
            G[r].sibling = l
    root = [i for i, x in enumerate(G) if x.parent == -1][0]
    G[root].typ = 'root'
    getDepth(G, root)
    getHeight(G, root)
    for i, x in enumerate(G):
        print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i, x.parent, x.sibling, x.degree, x.depth, x.height, x.typ))

if __name__ == '__main__': main()

Submission status: Accepted

Solution code:
import sys


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 = 0
		self.depth = 0
		self.height = 0

def define_depth(Nodes,node):

	if node.left == -1 and node.right == -1: #leaf
		return

	if node.left != -1:
		Nodes[node.left].depth = node.depth + 1
		define_depth(Nodes,Nodes[node.left])
	if node.right != -1:
		Nodes[node.right].depth = node.depth + 1
		define_depth(Nodes,Nodes[node.right])

def define_height(Nodes,node):

	h1 = 0
	h2 = 0

	if node.left != -1:
		h1 += define_height(Nodes,Nodes[node.left]) + 1
	if node.right != -1:
		h2 += define_height(Nodes,Nodes[node.right]) + 1

	return max(h1,h2)

def find_root(Nodes,node):

	if node.parent == -1:
		return node.id

	return find_root(Nodes,Nodes[node.parent])


def test():

	n = int(sys.stdin.readline())
	Nodes = [Node(0,0,0)] * n
	root = 0

	# Reading inputs
	for i in range(n):

		inputs = list(map(int,sys.stdin.readline().split()))
		id = inputs[0]
		left = inputs[1]
		right = inputs[2]

		tmp_node = Node(id,left,right)
		Nodes[id] = tmp_node

	# Defining parent and sibling and root
	for node in Nodes:

		child_count = 0

		# Parent
		if node.right != -1:
			Nodes[node.right].parent = node.id
			child_count += 1
		if node.left != -1:
			Nodes[node.left].parent = node.id
			child_count += 1

		# Degree
		node.degree = child_count

		#Sibling
		if node.right != -1 and node.left != -1:
			Nodes[node.right].sibling = node.left
			Nodes[node.left].sibling = node.right

	# Finding root
	root = find_root(Nodes,Nodes[0])

	# Defining depth
	define_depth(Nodes,Nodes[root])

	# Defining height
	for node in Nodes:
		node.height = define_height(Nodes,node)

	for i in range(n):

		print(f"node {Nodes[i].id}: ",end='')
		print(f"parent = {Nodes[i].parent}, ",end='')
		print(f"sibling = {Nodes[i].sibling}, ",end='')
		print(f"degree = {Nodes[i].degree}, ",end='')
		print(f"depth = {Nodes[i].depth}, ",end='')
		print(f"height = {Nodes[i].height}, ",end='')

		if Nodes[i].parent == -1:
			print(f"root")
		elif Nodes[i].left == -1 and Nodes[i].right == -1:
			print(f"leaf")
		else:
			print(f"internal node")



if __name__ == "__main__":
	test()

Submission status: Accepted

Solution code:
class binaryTreeNode:
    def __init__(self, x):
        self.val = x
        self.right = None
        self.left = None

n = int(input())
hashMap = {}
rootL = list(range(n))
index = 0
while index < n:
    inputL = list(map(int, input().split()))
    if not inputL[0] in hashMap:
        hashMap[inputL[0]] = binaryTreeNode(inputL[0])
    parent = hashMap[inputL[0]]
    if inputL[1] != -1:
        rootL.remove(inputL[1])
        if inputL[1] in hashMap:
            leftN = hashMap[inputL[1]]
            parent.left = leftN
        else:
            leftN = binaryTreeNode(inputL[1])
            hashMap[inputL[1]] = leftN
            parent.left = leftN
    if inputL[2] != -1:
        rootL.remove(inputL[2])
        if inputL[2] in hashMap:
            rightN = hashMap[inputL[2]]
            parent.right = rightN
        else:
            rightN = binaryTreeNode(inputL[2])
            hashMap[inputL[2]] = rightN
            parent.right = rightN
    index+=1

answerL = ['']*n
root = hashMap[rootL[0]]
def lookNode(parentV, node, sibling, depth):
    if node != None:
        answer = ''
        answer+='node '+str(node.val)+': '
        answer+='parent = '+str(parentV)+', '
        if sibling != None:
            answer+='sibling = '+str(sibling.val)+', '
        else:
            answer+='sibling = '+str(-1)+', '
        if node.right != None and node.left != None:
            answer+='degree = '+str(2)+', '
        elif node.right == None and node.left == None:
            answer+='degree = '+str(0)+', '
        else:
            answer+='degree = '+str(1)+', '
        answer+='depth = '+str(depth)+', '
        height = 0
        if node.right == None and node.left == None:
            height = 0
        else:
            height = max(lookNode(node.val, node.left, node.right, depth+1), lookNode(node.val, node.right, node.left, depth+1))+1
        answer+='height = ' +str(height)+', '
        if parentV == -1:
            answer+='root'
        elif node.right == None and node.left == None:
            answer+='leaf'
        else:
            answer+='internal node'
        answerL[node.val] = answer
        return height
    else:
        return 0
lookNode(-1, root, None, 0)
for ans in answerL:
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
P = [-1]*n
C = [[] for i in range(n)]
D = [[] for i in range(n)]
T = [[] for i in range(n)]
S = [-1]*n
deg = [0]*n
H = [-1]*n

Q1 = deque()
Q2 = deque()

for i in range(n):
  s = [int(i) for i in input().split()]
  id = s[0]
  l = s[1]
  r = s[2]
  C[id] = (l,r)
  if l != -1:
    P[l] = id
    S[l] = r
    deg[id] += 1
  if r != -1:
    P[r] = id
    S[r] = l
    deg[id] += 1
  if deg[id] == 0:
    T[id] = "leaf"
    Q2.append(id)
    H[id] = 0

for i in range(n):
  if P[i] == -1:
    root = i
    T[i] = "root"
  elif T[i] == []:
    T[i] = "internal node"

Q1.append(root)
D[root] = 0

while Q1:
  x = Q1.popleft()
  for nx in C[x]:
    if nx != -1:
      Q1.append(nx)
      D[nx] = D[x] + 1
while Q2:
  x = Q2.popleft()
  nx = P[x]
  if nx != -1:
    Q2.append(nx)
    H[nx] = max(H[x] + 1, H[nx])

for i in range(n):
  print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(i,P[i],S[i],deg[i],D[i],H[i],T[i]))

Submission status: Accepted

Solution code:
n = int(input())

"""親情報を入れる'p'、子情報を入れる'c'、深さを記録する'd'の、3つの辞書を作成"""
p, c, d = {}, {}, {}

for i in range(n):
    num, *children = input().split()
    c[num] = children
    for j in c[num]:
        if j != '-1':
            p[j] = num

def checkdepth(num, depth):
    d[num] = depth
    for i in c[num]:
        if i != '-1':
            checkdepth(i, depth+1)

"""高さを調べる関数。heightの引数には常に0を渡す"""
def checkheight(num, height):
    if c[num][0] != '-1':
        h1 = checkheight(c[num][0], height+1)
    else:
        h1 = height
    if c[num][1] != '-1':
        h2 = checkheight(c[num][1], height+1)
    else:
        h2 = height
    return max(h1, h2)

root = (set(c) - set(p)).pop()
p[root] = '-1'
checkdepth(root, 0)

def checksibling(num):
    if p[num] != '-1':
        for i in c[p[num]]:
            if i != '-1' and i != num:
                return i
                break
    return '-1'

def checkdegree(num, degree=0):
    for i in c[num]:
        if i != '-1':
            degree += 1
    return degree

for i in range(n):
    i = str(i)
    sibling = checksibling(i)
    degree = checkdegree(i, 0)
    if p[i] == '-1':
        nodetype = 'root'
    elif degree == 0:
        nodetype = 'leaf'
    else:
        nodetype = 'internal node'
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i, p[i], sibling, degree, d[i], checkheight(i, 0), nodetype))