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: Wrong Answer

Solution code:
# tree node
class node:
	def __init__(self,value,left = None,right = None):
		self.value = value # value is a number
		self.left = left
		self.right = right # left and right are both 'node' type

# binary tree
class binary_tree:
	def __init__(self,n):
		self.root = None
		self.node_count = n

	def insert(self,value,left,right):
		if self.root == None:
			self.root = node(value,left,right)
		else:
			node_stack = [self.root]
			while node_stack != []:
				curr_node = node_stack.pop()
				if curr_node == None:
					continue
				if curr_node.value == value:
					curr_node.left = left
					curr_node.right = right
					break
				node_stack.append(curr_node.left)
				node_stack.append(curr_node.right)

	def get_degree(self):
		self.degree_list = [0 for _ in range(self.node_count)]
		node_stack = [self.root]
		while node_stack != []:
			curr_node = node_stack.pop()
			self.degree_list[curr_node.value] = 0
			if curr_node.right != None:
				self.degree_list[curr_node.value] = self.degree_list[curr_node.value] + 1
				node_stack.append(curr_node.right)
			if curr_node.left != None:
				self.degree_list[curr_node.value] = self.degree_list[curr_node.value] + 1
				node_stack.append(curr_node.left)

	def get_parent(self):
		self.parent_list = [0 for _ in range(self.node_count)]
		parent_stack = [[self.root,-1]]
		while parent_stack != []:
			curr_node,curr_parent = parent_stack.pop()
			self.parent_list[curr_node.value] = curr_parent
			if curr_node.right != None:
				parent_stack.append([curr_node.right,curr_node.value])
			if curr_node.left != None:
				parent_stack.append([curr_node.left,curr_node.value])

	def get_node_type(self):
		self.node_type_list = ['' for _ in range(self.node_count)]
		type_stack = [[self.root,'root']]
		while type_stack != []:
			curr_node,node_type = type_stack.pop()
			self.node_type_list[curr_node.value] = node_type
			if curr_node.right != None:
				type_stack.append([curr_node.right,'leaf' if curr_node.right.left == None and curr_node.right.left == None else 'internal node'])
			if curr_node.left != None:
				type_stack.append([curr_node.left,'leaf' if curr_node.left.left == None and curr_node.left.left == None else 'internal node'])

	def get_sibling(self):
		self.sibling_list = [0 for _ in range(self.node_count)]
		sibling_stack = [[self.root,None]]
		while sibling_stack != []:
			curr_node,sibling_node = sibling_stack.pop()
			self.sibling_list[curr_node.value] = sibling_node.value if sibling_node != None else -1
			if curr_node.right != None:
				sibling_stack.append([curr_node.right,curr_node.left])
			if curr_node.left != None:
				sibling_stack.append([curr_node.left,curr_node.right])

	def get_depth(self):
		self.depth_list = [0 for _ in range(self.node_count)]
		depth_stack = [(self.root,0)]
		while depth_stack != []:
			curr_node,curr_depth = depth_stack.pop()
			self.depth_list[curr_node.value] = curr_depth
			if curr_node.right != None:
				depth_stack.append((curr_node.right,curr_depth + 1))
			if curr_node.left != None:
				depth_stack.append((curr_node.left,curr_depth + 1))
		
	def get_height(self):
		self.height_list = [0 for _ in range(self.node_count)]
		height_stack = []
		node_stack = [self.root]
		while node_stack != []:
			curr_node = node_stack.pop()
			height_stack.append(curr_node)
			if curr_node.right != None:
				node_stack.append(curr_node.right)
			if curr_node.left != None:
				node_stack.append(curr_node.left)
		while height_stack != []:
			curr_node = height_stack.pop()
			if curr_node.left == None and curr_node.right == None:
				self.height_list[curr_node.value] = 0
			elif curr_node.left != None and curr_node.right == None:
				self.height_list[curr_node.value] = 1 + self.height_list[curr_node.left.value]
			elif curr_node.left == None and curr_node.right != None:
				self.height_list[curr_node.value] = 1 + self.height_list[curr_node.right.value]
			else:
				self.height_list[curr_node.value] = 1 + max(self.height_list[curr_node.left.value],self.height_list[curr_node.right.value])


if __name__ == '__main__':
	n = eval(input())
	tree = binary_tree(n)
	for _ in range(n):
		value,left_value,right_value = [eval(x) for x in input().split()]
		left = node(left_value) if left_value != -1 else None
		right = node(right_value) if right_value != -1 else None
		tree.insert(value,left,right)
	tree.get_degree()
	tree.get_parent()
	tree.get_depth()
	tree.get_height()
	tree.get_sibling()
	tree.get_node_type()
	for i in range(n):
		print('node',str(i)+':',end = ' ')
		print('parent','=',str(tree.parent_list[i]) + ',',end = ' ')
		print('sibling','=',str(tree.sibling_list[i]) + ',',end = ' ')
		print('degree','=',str(tree.degree_list[i]) + ',',end = ' ')
		print('depth','=',str(tree.depth_list[i]) + ',',end = ' ')
		print('height','=',str(tree.height_list[i]) + ',',end = ' ')
		print(tree.node_type_list[i])

Submission status: Wrong Answer

Solution code:
class Node():
    def __init__(self, id, left, right, parent=-1, sibling=-1, degree=-1, depth=-1, height=-1, type=None):
        self.id = id
        self.left = left
        self.right = right
        self.parent = parent
        self.sibling = sibling
        self.degree = degree
        self.depth = depth
        self.height = height
        self.type = type
    def show(self):
        print 'node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s' % (self.id, self.parent, self.sibling, self.degree, self.depth, self.height, self.type)

def hasChild(x):
    if x == -1:
        return 0
    else:
        return 1

def calcDepth(node):
    if node.parent == -1:
        return 0
    return 1 + calcDepth(a[node.parent])

def calcHeight(node):
    if node.degree == 0:
        return 0
    return 1 + max(calcHeight(a[node.left]), calcHeight(a[node.right]))

n = int(raw_input())
a = []
dict = {}
for i in range(n):
    tmp = map(int, raw_input().split())
    if tmp[1] == -1 and tmp[2] == -1:
        dict[tmp[0]] = Node(tmp[0], tmp[1], tmp[2], degree=0, type='leaf')
    else:
        dict[tmp[0]] = Node(tmp[0], tmp[1], tmp[2], degree=hasChild(tmp[1])+hasChild(tmp[2]))

for i in range(n):
    a.append(dict[i])

for i in range(n):
    if a[i].right != -1:
        a[a[i].right].parent = a[i].id
    if a[i].left != -1:
        a[a[i].left].parent = a[i].id

for i in range(n):
    a[i].depth = calcDepth(a[i])
    a[i].height = calcHeight(a[i])
        
for i in range(n):
    if a[i].parent != -1 and a[i].degree != 0:
        a[i].type = 'internal node'
    elif a[i].parent == -1 and a[i].degree > 0:
        a[i].type = 'root'
    for j in range(n):
        if i == j:
            continue
        if a[i].depth == a[j].depth and a[i].parent == a[j].parent:
            a[i].sibling = j
        
for el in a:
    el.show()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
tree = [{"parent":-1, "left":-1, "right":-1, "sibling": -1} for _ in range(N)]
parent = set([n for n in range(N)])

for _ in range(N):
    inp = [int(n) for n in input().split()]
    tree[inp[0]]["left"] = inp[1]
    tree[inp[0]]["right"] = inp[2]
    tree[inp[0]]["degree"] = sum([inp[1] != -1, inp[2] != -1])
    
    tree[inp[1]]["parent"] = inp[0]
    tree[inp[2]]["parent"] = inp[0]
    tree[inp[1]]["sibling"] = inp[2]
    tree[inp[2]]["sibling"] = inp[1]
    
    parent = parent.difference(inp[1:])
    
def set_depth(n, depth):
    tree[n]["depth"] = depth
    
    if tree[n]["left"] != -1:
        set_depth(tree[n]["left"], depth+1)
    if tree[n]["right"] != -1:
        set_depth(tree[n]["right"], depth+1)

root = parent.pop()
set_depth(root, 0)

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

set_height(root)

for n in range(N):
    if tree[n]["parent"] == -1:
        tree[n]["type"] = "root"
    elif tree[n]["degree"] == 0:
        tree[n]["type"] = "leaf"
    else:
        tree[n]["type"] = "internal node"
    
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"\
          .format(n, tree[n]["parent"], tree[n]["sibling"],
                  tree[n]["degree"], tree[n]["depth"], tree[n]["height"], tree[n]["type"]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def dfs(here, p, d, conn, parent, depth, height):
    parent[here] = p
    depth[here] = d
    l_d, r_d = 0, 0
    for c in conn[here]:
        l_d = dfs(c[0], here, d + 1, conn, parent, depth, height)
        r_d = dfs(c[1], here, d + 1, conn, parent, depth, height)
    if len(conn[here]):
        height[here] = max(l_d, r_d) - d
    return max(l_d, r_d, d)

v_num = int(input())
conn = defaultdict(list)
in_v = [0 for n in range(v_num)]
for _ in range(v_num):
    v, left, right = (int(n) for n in input().split(" "))
    if left != -1:
        conn[v].append([left, right])
        in_v[left] += 1
        in_v[right] += 1
for i, n in enumerate(in_v):
    if not n:
        root = i
        break
parent = [-1 for n in range(v_num)]
depth = [0 for n in range(v_num)]
height = [0 for n in range(v_num)]
dfs(root, -1, 0, conn, parent, depth, height)
sibling = [-1 for n in range(v_num)]
for i in range(v_num):
    for j in range(v_num):
        if i == j:
            continue
        elif parent[i] == parent[j]:
            sibling[i] = j
            break
v_type = ["" for n in range(v_num)]
for i in range(v_num):
    if i == root:
        v_type[i] = "root"
    elif len(conn[i]) != 0:
        v_type[i] = "internal node"
    else:
        v_type[i] = "leaf"
for i in range(v_num):
    print("node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}".format(i, parent[i], sibling[i], 2 if len(conn[i]) else 0, depth[i], height[i], v_type[i]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def dfs(here, p, d, conn, parent, depth, height):
    parent[here] = p
    depth[here] = d
    l_d, r_d = 0, 0
    for c in conn[here]:
        if c[0] >= 0:
            l_d = dfs(c[0], here, d + 1, conn, parent, depth, height)
        if c[1] >= 0:
            r_d = dfs(c[1], here, d + 1, conn, parent, depth, height)
    if len(conn[here]):
        height[here] = max(max(l_d, r_d) - d, 0)
    return max(l_d, r_d, d)

v_num = int(input())
conn = defaultdict(list)
in_v = [0 for n in range(v_num + 1)]
degree = [0 for n in range(v_num)]
for _ in range(v_num):
    v, left, right = (int(n) for n in input().split(" "))
    conn[v].append([left, right])
    in_v[left] += 1
    in_v[right] += 1
    degree[v] += int(left >= 0) + int(right >= 0)
for i, n in enumerate(in_v):
    if not n:
        root = i
        break
parent = [-1 for n in range(v_num)]
depth = [0 for n in range(v_num)]
height = [0 for n in range(v_num)]
dfs(root, -1, 0, conn, parent, depth, height)
sibling = [-1 for n in range(v_num)]
for i in range(v_num):
    for j in range(v_num):
        if i == j:
            continue
        elif parent[i] == parent[j]:
            sibling[i] = j
            break
v_type = ["" for n in range(v_num)]
for i in range(v_num):
    if i == root:
        v_type[i] = "root"
    elif len(conn[i]) != 0:
        v_type[i] = "internal node"
    else:
        v_type[i] = "leaf"
for i in range(v_num):
    print("node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}".format(i, parent[i], sibling[i], degree[i], depth[i], height[i], v_type[i]))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

if __name__ == '__main__':

    n = int(input())
    T = [Node() for i in range(n)]

    for _ in range(n):
        i, left, right = [int(s) for s in input().split(" ")]
        has_left = (left != -1)
        has_right = (right != -1)
        if has_left:
            T[i].left = left
            T[left].parent = i
            T[i].degree += 1
        if has_right:
            T[i].right = right
            T[right].parent = i
            T[i].degree += 1
        if has_left and has_right:
            T[left].sibling = right
            T[right].sibling = left

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

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

    for i, n in enumerate(T):
        if n.parent == -1:
            root = i
        
    setDepth(root, 0)
    setHeight(0)

    for i, node in enumerate(T):
        if node.parent == -1:
            n_type = "root"
        elif node.left != -1:
            n_type = "internal node"
        else:
            n_type = "leaf"

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

if __name__ == '__main__':

    n = int(input())
    T = [Node() for i in range(n)]

    for _ in range(n):
        i, left, right = [int(s) for s in input().split(" ")]
        has_left = (left != -1)
        has_right = (right != -1)
        if has_left:
            T[i].left = left
            T[left].parent = i
            T[i].degree += 1
        if has_right:
            T[i].right = right
            T[right].parent = i
            T[i].degree += 1
        if has_left and has_right:
            T[left].sibling = right
            T[right].sibling = left

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

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

    for i, n in enumerate(T):
        if n.parent == -1:
            root = i
        
    setDepth(root, 0)
    setHeight(root)

    for i, node in enumerate(T):
        if node.parent == -1:
            n_type = "root"
        elif node.left != -1:
            n_type = "internal node"
        else:
            n_type = "leaf"

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

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'sibling', 'degree', 'depth', 'height', 'type', 'c']
    def __init__(self, id):
        self.id = id
        self.p = -1
        self.sibling = -1
        self.degree = 0
        self.depth = -1
        self.height = 0
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, sibling = {self.sibling}, degree = {self.degree}, depth = {self.depth}, height = {self.height}, {self.type}"
n = int(input())
tree = tuple(Tree(i) for i in range(n))
leaf_li = []
for _ in range(n):
    id, *c = map(int, readline().replace("-1", "").split())
    if c != []:
        tree[id].type = "internal node"
        tree[id].c = c
        for j in c:
            tree[j].p = id
        len_c = len(c)
        tree[id].degree = len_c
        if len_c == 2:
            tree[c[0]].sibling = c[1]
            tree[c[1]].sibling = c[0]
    else:
        leaf_li.append(id)
for i in leaf_li:
    a = i
    cnt = 0
    while tree[a].p != -1 and tree[a].height == 0:
        tree[a].height = cnt
        cnt += 1
        a = tree[a].p
    if tree[a].height == 0 and tree[a].p == -1:
        root = a
        tree[root].type = "root"
        tree[root].depth = 0
        tree[root].height = cnt + 1
def depth_check(id, d):
    d += 1
    for i in tree[id].c:
        tree[i].depth = d
        if tree[i].type != "leaf":
            depth_check(i, d)
depth_check(root, 0)
print("\n".join(map(str, tree)))

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'sibling', 'degree', 'depth', 'height', 'type', 'c']
    def __init__(self, id):
        self.id = id
        self.p = -1
        self.sibling = -1
        self.degree = 0
        self.depth = -1
        self.height = 0
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, sibling = {self.sibling}, degree = {self.degree}, depth = {self.depth}, height = {self.height}, {self.type}"
n = int(input())
tree = tuple(Tree(i) for i in range(n))
leaf_li = []
for _ in range(n):
    id, *c = map(int, readline().replace("-1", "").split())
    if c != []:
        tree[id].type = "internal node"
        tree[id].c = c
        for j in c:
            tree[j].p = id
        len_c = len(c)
        tree[id].degree = len_c
        if len_c == 2:
            tree[c[0]].sibling = c[1]
            tree[c[1]].sibling = c[0]
    else:
        leaf_li.append(id)
for i in leaf_li:
    a = i
    cnt = 1
    while tree[a].p != -1 and tree[tree[a].p].height == 0:
        tree[tree[a].p].height = cnt
        cnt += 1
        a = tree[a].p
    if tree[a].p == -1:
        root = a
        tree[root].type = "root"
        tree[root].depth = 0
        tree[root].height = cnt
def depth_check(id, d):
    d += 1
    for i in tree[id].c:
        tree[i].depth = d
        if tree[i].type != "leaf":
            depth_check(i, d)
depth_check(root, 0)
print("\n".join(map(str, tree)))

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'sibling', 'degree', 'depth', 'height', 'type', 'c']
    def __init__(self, id):
        self.id = id
        self.p = -1
        self.sibling = -1
        self.degree = 0
        self.depth = -1
        self.height = 0
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, sibling = {self.sibling}, degree = {self.degree}, depth = {self.depth}, height = {self.height}, {self.type}"
def solve():
    n = int(input())
    if n == 1:
        input()
        print("node 0: parent = -1, sibling = -1, degree = 0, depth = 0, height = 0, root")
        return
    tree = tuple(Tree(i) for i in range(n))
    leaf_li = []
    for _ in range(n):
        id, *c = map(int, readline().replace("-1", "").split())
        if c != []:
            tree[id].type = "internal node"
            tree[id].c = c
            for j in c:
                tree[j].p = id
            len_c = len(c)
            tree[id].degree = len_c
            if len_c == 2:
                tree[c[0]].sibling = c[1]
                tree[c[1]].sibling = c[0]
        else:
            leaf_li.append(id)
    for i in leaf_li:
        a = i
        cnt = 1
        while tree[a].p != -1 and tree[tree[a].p].height == 0:
            tree[tree[a].p].height = cnt
            cnt += 1
            a = tree[a].p
        if tree[a].p == -1:
            root = a
            tree[root].type = "root"
            tree[root].depth = 0
            tree[root].height = cnt
    def depth_check(id, d):
        d += 1
        for i in tree[id].c:
            tree[i].depth = d
            if tree[i].type != "leaf":
                depth_check(i, d)
    depth_check(root, 0)
    print("\n".join(map(str, tree)))
solve()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'sibling', 'degree', 'depth', 'height', 'type', 'c']
    def __init__(self, id):
        self.id = id
        self.p = -1
        self.sibling = -1
        self.degree = 0
        self.depth = -1
        self.height = 0
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, sibling = {self.sibling}, degree = {self.degree}, depth = {self.depth}, height = {self.height}, {self.type}"
def solve():
    n = int(input())
    if n == 1:
        input()
        print("node 0: parent = -1, sibling = -1, degree = 0, depth = 0, height = 0, root")
        return
    tree = tuple(Tree(i) for i in range(n))
    leaf_li = []
    for _ in range(n):
        id, *c = map(int, readline().replace("-1", "").split())
        if c != []:
            tree[id].type = "internal node"
            tree[id].c = c
            for j in c:
                tree[j].p = id
            len_c = len(c)
            tree[id].degree = len_c
            if len_c == 2:
                tree[c[0]].sibling = c[1]
                tree[c[1]].sibling = c[0]
        else:
            leaf_li.append(id)
    root = 0
    for i in leaf_li:
        a = i
        cnt = 1
        while tree[a].p != -1 and tree[tree[a].p].height == 0:
            tree[tree[a].p].height = cnt
            cnt += 1
            a = tree[a].p
        if tree[a].p == -1 and tree[a].depth == -1:
            root = a
            tree[root].type = "root"
            tree[root].depth = 0
            tree[root].height = cnt
    tree[root].height = max(tree[i].height for i in tree[root].c) + 1
    def depth_check(id, d):
        d += 1
        for i in tree[id].c:
            tree[i].depth = d
            if tree[i].type != "leaf":
                depth_check(i, d)
    depth_check(root, 0)
    print("\n".join(map(str, tree)))
solve()

Submission status: Wrong Answer

Solution code:
import sys
def q(a,k):
 d[a]=k
 for b in t[a]:
  if'-1'!=b:q(b,k+1)
def n(a,k):
 if a in h:h[a]=max(h[a],k)
 else:h[a]=k
 if'-1'!=p[a]:n(p[a],k+1)
input()
t,p,s,d,h={},{},{},{},{}
for e in sys.stdin:
 x,y,z=e.split()
 t[x]=set([y,z])-set(['-1'])
 p[y]=p[z]=x
 s[y],s[z]=z,y
r=(set(t)-set(p)).pop()
p[r],s[r]=['-1']*2
q(r,0)
for i in t:
 if not t[i]:n(i,0)
print('\n'.join(f"node {i}: parent = {p[i]}, sibling = {s[i]}, degree = {len(t[i])}, depth = {d[i]}, height = {h[i]}, {('internal node'if d[i]else'root')if t[i]else'leaf'}"for i in map(str,sorted(map(int,t)))))

Submission status: Wrong Answer

Solution code:
class Tree:
    nodes = []
    def __init__(self):
        self.root = None
    def insert(self, nodenum, leftnum, rightnum):
        if leftnum != -1:
            self.nodes[nodenum].left = self.nodes[leftnum]
            self.nodes[leftnum].type_ = "internal node"
            self.nodes[leftnum].parent = self.nodes[nodenum]
            self.nodes[nodenum].degree += 1
        else:
            self.nodes[nodenum].left = -1
        if rightnum != -1:
            self.nodes[nodenum].right = self.nodes[rightnum]
            self.nodes[rightnum].type_ = "internal node"
            self.nodes[rightnum].parent = self.nodes[nodenum]
            self.nodes[nodenum].degree += 1
        else:
            self.nodes[nodenum].right = -1
        if leftnum != -1 and rightnum != -1:
            self.nodes[leftnum].sibling = rightnum
            self.nodes[rightnum].sibling = leftnum
    def depth(self, node):
        if node.left != -1:
            node.left.depth += node.depth + 1
            self.depth(node.left)
        if node.right != -1:
            node.right.depth += node.depth + 1
            self.depth(node.right)
    def height(self, node):
        if node.left == -1 and node.right == -1:
            node.type_ = "leaf"
            return 0
        elif node.left == -1:
            x = self.height(node.right)
            node.height = x
            return x + 1
        elif node.right == -1:
            x = self.height(node.left)
            node.height = x
            return x + 1
        else:
            x = max(self.height(node.left), self.height(node.right)) + 1
            node.height = x
            return x

class Node:
    def __init__(self, label, left = -1, right = -1):
        self.label = label
        self.type_ = "root"
        self.parent = -1
        self.sibling = -1
        self.depth = 0
        self.height = 0
        self.degree = 0
        self.left = left
        self.right = right

tree = Tree()
n = int(input())
for i in range(n):
    tree.nodes.append(Node(i))
for i in range(n):
    num, left, right = map(int, input().split())
    tree.insert(num, left, right)
for i in tree.nodes:
    if i.parent == -1:
        tree.depth(i)
        tree.height(i)
for i in tree.nodes:
    print("node {0:}: parent = ".format(i.label), end = "")
    if i.parent == -1:
        print(i.parent, end = "")
    else:
        print(i.parent.label, end = "")
    print(", sibling = {0:}, degree = {1:}, depth = {2:}, height = {3:}, {4:}".format(i.sibling, i.degree, i.depth, i.height, i.type_))

Submission status: Wrong Answer

Solution code:
class Tree:
    nodes = []
    def __init__(self):
        self.root = None
    def insert(self, nodenum, leftnum, rightnum):
        if leftnum != -1:
            self.nodes[nodenum].left = self.nodes[leftnum]
            self.nodes[leftnum].type_ = "internal node"
            self.nodes[leftnum].parent = self.nodes[nodenum]
            self.nodes[nodenum].degree += 1
        else:
            self.nodes[nodenum].left = -1
        if rightnum != -1:
            self.nodes[nodenum].right = self.nodes[rightnum]
            self.nodes[rightnum].type_ = "internal node"
            self.nodes[rightnum].parent = self.nodes[nodenum]
            self.nodes[nodenum].degree += 1
        else:
            self.nodes[nodenum].right = -1
        if leftnum != -1 and rightnum != -1:
            self.nodes[leftnum].sibling = rightnum
            self.nodes[rightnum].sibling = leftnum
    def depth(self, node):
        if node.left != -1:
            node.left.depth += node.depth + 1
            self.depth(node.left)
        if node.right != -1:
            node.right.depth += node.depth + 1
            self.depth(node.right)
    def height(self, node):
        if node.left == -1 and node.right == -1:
            node.type_ = "leaf"
            return 0
        elif node.left == -1:
            x = self.height(node.right)
            node.height = x
            return x + 1
        elif node.right == -1:
            x = self.height(node.left)
            node.height = x
            return x + 1
        else:
            x = max(self.height(node.left), self.height(node.right)) + 1
            node.height = x
            return x
class Node:
    def __init__(self, label, left = -1, right = -1):
        self.label = label
        self.type_ = "root"
        self.parent = -1
        self.sibling = -1
        self.depth = 0
        self.height = 0
        self.degree = 0
        self.left = left
        self.right = right

tree = Tree()
n = int(input())
for i in range(n):
    tree.nodes.append(Node(i))
for i in range(n):
    num, left, right = map(int, input().split())
    tree.insert(num, left, right)
for i in tree.nodes:
    if i.parent == -1:
        tree.depth(i)
        tree.height(i)
for i in tree.nodes:
    print("node {0:}: parent = ".format(i.label), end = "")
    if i.parent == -1:
        print(i.parent, end = "")
    else:
        print(i.parent.label, end = "")
    print(", sibling = {0:}, degree = {1:}, depth = {2:}, height = {3:}, {4:}".format(i.sibling, i.degree, i.depth, i.height, i.type_))