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 BinaryNode():
    def __init__(self):
        self.parent = -1
        self.left = -1
        self.right = -1
        self.depth = -1
        self.height = -1


class BinaryTree(list):
    def __init__(self, n):
        super().__init__([BinaryNode() for _ in range(n)])
        self.len = n
        self.root = None

    def set_node(self, id, left, right):
        self[id].left = left
        self[id].right = right
        if left > -1:
            self[left].parent = id
        if right > -1:
            self[right].parent = id

    def __set_depth(self, id, depth):
        self[id].depth = depth
        if self[id].left > -1:
            self.__set_depth(self[id].left, depth + 1)
        if self[id].right > -1:
            self.__set_depth(self[id].right, depth + 1)

    def set_depth(self):
        self.__set_depth(self.root, 0)

    def __set_height(self, id):
        if id == -1:
            return -1
        height = 1 + max(self.__set_height(self[id].left), self.__set_height(self[id].right))
        self[id].height = height
        return height

    def set_height(self):
        self.__set_height(self.root)

    def set_root(self):
        for i in range(self.len):
            if self[i].parent == -1:
                self.root = i
                break

    def get_nodetype(self, i):
        if self[i].parent == -1:
            return "root"
        elif self[i].left == -1 and self[i].right == -1:
            return "leaf"
        else:
            return "internal node"

    def get_sibling(self, i):
        parent = self[i].parent
        if parent == -1:
            return -1
        if self[parent].left == i:
            return self[parent].right
        else:
            return self[parent].left

    def get_degree(self, i):
        return (self[i].left > -1) * 1 + (self[i].right > -1) * 1

    def set_all(self):
        self.set_root()
        self.set_depth()
        self.set_height()

    def print(self):
        for i in range(self.len):
            print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
                i, self[i].parent, self.get_sibling(i), self.get_degree(i),
                self[i].depth, self[i].height, self.get_nodetype(i)))


def main():
    n = int(input())
    tree = BinaryTree(n)
    for _ in range(n):
        node_info = input().split(" ")
        node_info = list(map(int, node_info))
        tree.set_node(node_info[0], node_info[1], node_info[2])
    tree.set_all()
    tree.print()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
nil=-1
sn=[[-1,-1,-1]for _ in range(n)]
child=[[]for _ in range(n)]
def getdepth(u):
	d=0
	while sn[u][0] != nil:
		u=sn[u][0]
		d+=1
	return d
def getheight(u):
	h1=h2=0
	if sn[u][2]!=nil:
		h1=getheight(sn[u][2])+1
	if sn[u][1]!=nil:
		h2=getheight(sn[u][1])+1
	return max(h1,h2)
aa=[]
for i in range(n):
	a=list(map(int,input().split()))
	aa.append(a)
aa.sort()
for i in range(n):
	a=aa[i]
	if a[1]!=-1:
		sn[a[0]][1]=a[1]
	if a[2]!=-1:
		sn[a[0]][2]=a[2]
	if a[1]!=-1:
		sn[a[1]][0]=a[0]
	if a[2]!=-1:
		sn[a[2]][0]=a[0]
for i in range(n):
	ans1="node "+str(i)+":"
	ans2="parent = "+str(sn[i][0])+","
	if sn[i][0]==-1:
		x=-1
	elif sn[sn[i][0]][1]==-1 or sn[sn[i][0]][2]==-1:
		x=-1
	else:
		x=sn[sn[i][0]][2] if i==sn[sn[i][0]][1] else sn[sn[i][0]][1]
	ans3="sibling = "+str(x)+","
	y=0
	if sn[i][1]!=-1:
		y+=1
	if sn[i][2]!=-1:
		y+=1
	ans4="degree = "+str(y)+"," 
	ans5="depth = "+str(getdepth(i))+","
	ans6="height = "+str(getheight(i))+","
	if sn[i][0]==-1:
		ans7="root"
	elif getheight(i)==0:
		ans7="leaf"
	else:
		ans7="internal node"
	print(ans1,ans2,ans3,ans4,ans5,ans6,ans7)

Submission status: Accepted

Solution code:
N = int(input())
childs = [[] for _ in range(N)]
parent = [-1 for _ in range(N)]
sibling = [-1 for _ in range(N)]
isleaf = [True for _ in range(N)]
for _ in range(N):
    i, l, r = map(int, input().split())
    if l != -1 or r != -1:
        isleaf[i] = False
    for child in [l, r]:
        if child != -1:
            childs[i].append(child)
            parent[child] = i
    if l != -1:
        sibling[l] = r
    if r != -1:
        sibling[r] = l

depth = [0 for _ in range(N)]
height = [0 for _ in range(N)]


def dfs(cur):
    for child in childs[cur]:
        depth[child] = depth[cur] + 1
        dfs(child)
        height[cur] = max(height[child] + 1, height[cur])


root = 0
while root < N:
    if parent[root] == -1:
        break
    else:
        root += 1
dfs(root)

for i in range(N):
    print(
        'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'
        .format(
            i, parent[i], sibling[i], len(childs[i]), depth[i], height[i],
            'root' if i == root else 'leaf' if isleaf[i] else 'internal node'))

Submission status: Accepted

Solution code:

null = -1

class Node:
    def __init__(self):
        self.parent = null
        self.left = null
        self.right = null
        self.id = null
        self.depth = null
        self.height = null
        self.sibling = null
        self.type = null
        self.degree = 0
        
    
def setDepth(u, d):
    if u == null:
        return  
    Tree[u].depth = d
    setDepth(Tree[u].left, d + 1)
    setDepth(Tree[u].right, d + 1)
    
def setHeight(u):
    h1 = 0
    h2 = 0
    if Tree[u].left != null:
        h1 = setHeight(Tree[u].left) + 1
    if Tree[u].right != null:
        h2 = setHeight(Tree[u].right) + 1
    Tree[u].height = max(h1, h2)
    return Tree[u].height

def setType():
    global root
    for i in range(n):
        if Tree[i].parent == null:
            Tree[i].type = "root"
            root = i
        elif Tree[i].left == null and Tree[i].right == null:
            Tree[i].type = "leaf"
        else:
            Tree[i].type = "internal node"
            
def getSibling(i):
    if Tree[i].parent == null:
        return null
    elif Tree[Tree[i].parent].left != i and Tree[Tree[i].parent].left != null:
        return Tree[Tree[i].parent].left
    elif Tree[Tree[i].parent].right != i and Tree[Tree[i].parent].right != null:
        return Tree[Tree[i].parent].right
    return null
        
Tree = []
root = 0

n = int(input())
for i in range(n):
    Tree.append(Node())
    
for i in range(n):
    tmp = list(map(int, input().split()))
    
    Tree[tmp[0]].id = tmp[0]
    
    if tmp[1] != -1:
        Tree[tmp[0]].left = tmp[1]
        Tree[tmp[1]].parent = tmp[0]
        Tree[tmp[0]].degree += 1
    if tmp[2] != -1:
        Tree[tmp[0]].right = tmp[2]
        Tree[tmp[2]].parent = tmp[0]
        Tree[tmp[0]].degree += 1

setType()
setDepth(root, 0)
setHeight(root)

for i in range(n):
    #print(Tree[i].depth, Tree[i].height)
    print("node", Tree[i].id, end = "")
    print(": parent =", Tree[i].parent, end = "")
    print(", sibling =",getSibling(i), end = "")
    print(", degree =",Tree[i].degree, end = "")
    print(", depth =",Tree[i].depth, end = "")
    print(", height =",Tree[i].height, end = "")
    print(",", Tree[i].type)

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, value):
        self.value = value
        self.deep = -1
        self.parent = None
        self.left = -1
        self.right = -1
        self.height = -1
        self.sib = -1

def setdeep(tree, i, deep):
    tree[i].deep = deep
    if tree[i].left != -1:
        setdeep(tree, tree[i].left, deep + 1)
    if tree[i].right != -1:
        setdeep(tree, tree[i].right, deep + 1)

def setheight(tree, i):
    if tree[i].height != -1:
        pass
    elif tree[i].left == -1 and tree[i].right == -1:
        tree[i].height = 0
    elif tree[i].left == -1:
        tree[i].height = setheight(tree, tree[i].right)
    elif tree[i].right == -1:
        tree[i].height = setheight(tree, tree[i].left)
    else:
        tree[i].height = max(setheight(tree, tree[i].right), setheight(tree, tree[i].left))
    return tree[i].height + 1

if __name__ == '__main__':
    n = int(input())
    tree = {}

    for _ in range(n):
        datas = [int(num) for num in input().split(' ')]
        nodeid = datas[0]
        if nodeid not in tree.keys():
            tree[nodeid] = Node(nodeid)
        tree[nodeid].left = left = int(datas[1])
        tree[nodeid].right = right = int(datas[2])
        if left != -1:
            if left not in tree.keys():
                tree[left] = Node(left)
            tree[left].parent = nodeid
            tree[left].sib = right
        if right != -1:
            if right not in tree.keys():
                tree[right] = Node(right)
            tree[right].parent = nodeid
            tree[right].sib = left

    for i in range(n):
        curnode = tree[i]
        if curnode.parent is None:
            # this is root
            setdeep(tree, i, 0)
            setheight(tree, i)
            break
            
    for i in range(n):
        curnode = tree[i]
        deg = 0
        if curnode.left == -1 and curnode.right == -1:
            nodetype = 'leaf'
            deg = 0
        else:
            if curnode.left != -1:
                deg += 1
            if curnode.right != -1:
                deg += 1
            nodetype = 'internal node'
        if curnode.parent == None:
            nodetype = 'root'
            parent = -1
        else:
            parent = curnode.parent
        print('node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s' \
            % (i, parent,curnode.sib, deg,  curnode.deep, curnode.height, nodetype) )

Submission status: Accepted

Solution code:
#ALDS1_7_B
N = int(input())
answer1= []

def get_parent(node):
    parent = -1
    if "parent" in node:
        return node["parent"]
    return parent

def get_depth(node):
    depth = 0
    while "parent" in node:
        depth += 1
        parent = node["parent"]
        node = rooted_tree[parent]
    return depth

def get_node_type(node):
    if "parent" not in node:
        return "root"
    if node["left"] == -1 and node["right"] == -1:
        return "leaf"
    return "internal node"

def get_sibling(id, node):
    sibling = -1
    if "parent" not in node:
        return sibling
    parent_rchild= rooted_tree[node["parent"]]["right"]
    parent_lchild= rooted_tree[node["parent"]]["left"]
    if id == parent_rchild:
        sibling = parent_lchild
    else:
        sibling = parent_rchild
    return sibling

def get_degree(node):
    degree = 0
    if node["left"] > -1:
        degree += 1
    if node["right"] > -1:
        degree += 1        
    return degree

def get_height(node):
    h1 = h2 = 0
    if node["right"] > -1:
        h1 = get_height(rooted_tree[node["right"]]) + 1
    if node["left"] > -1:
        h2 = get_height(rooted_tree[node["left"]]) + 1
    h =  max(h1, h2)
    return h

rooted_tree = [{} for i in range(N)]
for _ in range(N):
    row = input()
    id, left, right = list(map(int, row.split()))
    rooted_tree[id]["right"] = right
    rooted_tree[id]["left"] = left
    #子供のparentを左右で設定する。
    if left > -1:
        left_child_id = left
        rooted_tree[left_child_id]["parent"] = id
    if right > -1:
        right_child_id = right
        rooted_tree[right_child_id]["parent"] = id

for id in range(N):
    node = rooted_tree[id]
    parent = get_parent(node)
    sibling = get_sibling(id, node)
    degree = get_degree(node)
    depth = get_depth(node)
    height = get_height(node)
    node_type = get_node_type(node)
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(id, parent, sibling, degree, depth, height, node_type))

Submission status: Accepted

Solution code:
def binary(node,parent,sibling,depth,root):
    if node!=-1:
        id,left,right=A[node]
        degree = len([i for i in (right, left) if i != -1])
        if parent==-1:root="root"
        elif degree!=0:root="internal node"
        else:root="leaf"
        B.append([node,parent,sibling,degree,depth,root])
        binary(left,node,right,depth+1,root)
        binary(right,node,left,depth+1,root)


def setHight(H,u):
    h1,h2=0,0
    if A[u][2]!=-1:
        h1=setHight(H,A[u][2])+1
    if A[u][1]!=-1:
        h2=setHight(H,A[u][1])+1
    H[u]=max(h1,h2)
    return H[u]


n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
B,H=[],[0]*n
top=[i for i in range(n)]
for i in range(n):
    for j in (A[i][1],A[i][2]):
        if j!=-1:top.remove(j)
top=top[0]
A=sorted(A)
binary(top,-1,-1,0,"root")
setHight(H,top)
for j,i in enumerate(sorted(B)):
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
          .format(i[0],i[1],i[2],i[3],i[4],H[j],i[5]))

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u, d=0):
        dep[u] = d
        h = 0
        for cu in chi[u]:
            h = max(h, dfs(cu, d + 1) + 1)
        hig[u] = h
        return h

    n = int(input())
    par = [-1] * n
    sib = [-1] * n
    deg = [0] * n
    dep = [-1] * n
    hig = [-1] * n
    typ = ["internal node"] * n
    chi = [[] for _ in range(n)]
    for _ in range(n):
        u, l, r = map(int, input().split())
        if l != -1:
            par[l] = u
            sib[l] = r
            deg[u] = 1
            chi[u] = [l]
        if r != -1:
            par[r] = u
            sib[r] = l
            deg[u] += 1
            chi[u] += [r]
        if deg[u] == 0:
            typ[u] = "leaf"
    root = par.index(-1)
    typ[root] = "root"
    dfs(root)
    for u in range(n):
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format
              (u, par[u], sib[u], deg[u], dep[u], hig[u], typ[u]))

main()

Submission status: Accepted

Solution code:

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

  def get_parent(self):
    if self.parent == None:
      return -1
    return self.parent.id

  def get_children(self):
    return list(filter(None, [self.left, self.right]))

  def get_sibling(self):
    parent = self.parent
    if parent == None:
      return -1
    children = parent.get_children()
    if len(children) == 1:
      return -1
    return list(filter(lambda x: x != self, children))[0].id

  def get_depth(self):
    count = 0
    tmp = self
    while tmp.parent:
      count += 1
      tmp = tmp.parent
    return count
    
  def get_height(self):
    l, r = 0, 0
    if self.left != None:
      l = self.left.get_height() + 1
    if self.right != None:
      r = self.right.get_height() + 1
    return max(l, r)
  
  def get_type(self):
    if self.parent == None:
      return "root"
    if len(self.get_children()) == 0:
      return "leaf"
    return "internal node"


num = int(input())
nodes = [None] * num
children = []

for i in range(num):
  id, left, right = map(int, input().split())
  n = nodes[id] if nodes[id] else Node(id)
  nodes[id] = n

  if left != -1:
    if nodes[left] == None:
      l = Node(left)
      l.parent = n
      nodes[left] = l
      n.left = l
    else:
      nodes[left].parent = n
      n.left = nodes[left]

  if right != -1:
    if nodes[right] == None:
      r = Node(right)
      r.parent = n
      nodes[right] = r
      n.right = r
    else:
      nodes[right].parent = n
      n.right = nodes[right]
    

for i in range(num):
  node = nodes[i]
  print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(node.id, node.get_parent(), node.get_sibling(), len(node.get_children()), node.get_depth(), node.get_height(), node.get_type()))

Submission status: Accepted

Solution code:

class Node:
    id = None
    parent = None
    left = None
    right = None
    sibling = -1
    depth = None
    height = None

    def __str__(self):
        degree = None
        _type = None

        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(self.id, self.parent, self.sibling, self.get_degree(), self.depth, self.height, self.get_type())

    def get_degree(self):
        degree = 0
        if self.left is not None:
            degree += 1
        if self.right is not None:
            degree += 1
        return degree

    def get_type(self):
        if self.parent == -1:
            return 'root'
        if self.get_degree() == 0:
            return 'leaf'
        else:
            return 'internal node'


def set_depth(node_id, depth):
    if node_id is None:
        return

    global T
    T[node_id].depth = depth
    set_depth(T[node_id].left, depth + 1)
    set_depth(T[node_id].right, depth + 1)


def set_height(node_id):
    global T

    h1, h2 = 0, 0
    if T[node_id].left is not None:
        h1 = set_height(T[node_id].left) + 1
    if T[node_id].right is not None:
        h2 = set_height(T[node_id].right) + 1

    T[node_id].height = max(h1, h2)

    return max(h1, h2)


n = int(input())
T = []
root = 0

for i in range(n):
    T.append(Node())

for i in range(n):
    _ = list(map(int, input().split()))
    _id = _[0]
    left = _[1]
    right = _[2]
    if left == -1:
        left = None
    if right == -1:
        right = None

    T[_id].id = _id
    T[_id].left = left
    T[_id].right = right

    if left is not None:
        T[left].parent = _id
    if right is not None:
        T[right].parent = _id

    if left is not None and right is not None:
        T[left].sibling = right
        T[right].sibling = left

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

set_depth(root, 0)
set_height(root)


for i in range(n):
    print(T[i])

Submission status: Accepted

Solution code:
class Node():
    def __init__(self,parent=-1,left=-1,right=-1,depth=0,height=-1,degree=0,sibling=-1,typ='internal node'):
        self.parent=parent
        self.left=left
        self.right=right
        self.depth=depth
        self.height=height
        self.degree=degree
        self.sibling=sibling
        self.typ=typ
        
def depth(node,i,n):
    node[i].depth=n
    if node[i].left!=-1:
        depth(node,node[i].left,n+1)
    if node[i].right!=-1:
        depth(node,node[i].right,n+1)

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

n=int(input())
N=[Node() for i in range(n)]
for i in range(n):
    p,l,r=[int(i) for i in input().split()]
    if l!=-1:
        N[p].left=l
        N[l].parent=p
        N[p].degree+=1
        if r != -1:
            N[l].sibling=r
            N[r].sibling=l
    if r!=-1:
        N[p].right=r
        N[r].parent=p
        N[p].degree+=1
    elif l==-1 and r==-1:
        N[p].typ='leaf'
        N[p].height=0


for i in range(n):
    height(N,i)
    if N[i].parent==-1:
        N[i].typ='root'
        depth(N,i,0)

for i in range(n):
    print('node '+str(i)+': parent = '+str(N[i].parent)+', sibling = '+str(N[i].sibling)+', degree = '+str(N[i].degree)+', depth = '+str(N[i].depth)+', height = '+str(N[i].height)+', '+N[i].typ)

Submission status: Accepted

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


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

def get_depth(node, D, u, d):
    D[u] = d
    if node[u].left != -1:
        get_depth(node, D, node[u].left, d+1)
    if node[u].right != -1:
        get_depth(node, D, node[u].right, d+1)


def get_height(node, H, u):
    h_l = 0   
    h_r = 0
    if node[u].left != -1:
        h_l = get_height(node, H, node[u].left) + 1
    if node[u].right != -1:
        h_r = get_height(node, H, node[u].right) + 1
    ans = max(h_l, h_r)
    H[u] = ans
    return ans

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

def get_degree(node, u):
    deg = 0
    if node[u].left != -1:
        deg +=1
    if node[u].right != -1:
        deg +=1
    return deg

for k, v in node.items():
    if v.parent is -1:
        root = k

D = {}
get_depth(node, D, root, 0)
H = {}
get_height(node, H, root)

def print_for_a_node(u):
    parent = node[u].parent
    sib = get_sibling(node, u)
    deg = get_degree(node, 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 i in range(n):
    print_for_a_node(i)

Submission status: Accepted

Solution code:
n = int(input())

tree_dict = {}
node_info_dict = {}

for _ in range(n):
    row = list(map(int, input().split(" ")))
    
    tree_dict[row[0]] = {
        "left": row[1],
        "right": row[2], 
    }
    
    node_info_dict[row[1]] = {
        "parent": row[0], 
        "sibling": row[2], 
    }
        
    node_info_dict[row[2]] = {
        "parent": row[0], 
        "sibling": row[1], 
    }
        
def get_depth(node_id):
    count = 1
    parent_node_id = node_info_dict[node_id]["parent"]
    while parent_node_id in node_info_dict:
        count += 1
        parent_node_id = node_info_dict[parent_node_id]["parent"]
    
    return count

def get_height(node_id, height):
    right_height, left_height = 0, 0
    if tree_dict[node_id]["right"] != -1:
        right_height = get_height(tree_dict[node_id]["right"], height) + 1
    
    if tree_dict[node_id]["left"] != -1:
        left_height = get_height(tree_dict[node_id]["left"], height) + 1

    height = right_height if right_height > left_height else left_height
    return height
    
for i in range(n):
    if i in node_info_dict:
        parent = node_info_dict[i]['parent']
        sibling = node_info_dict[i]['sibling']
        depth = get_depth(i)
    else:
        parent = -1
        sibling = -1
        depth = 0
        
    degree = 0
    if tree_dict[i]["right"] != -1:
        degree += 1
    if tree_dict[i]["left"] != -1:
        degree += 1
        
    height = get_height(i, 0)
    
    if parent == -1:
        node_type = "root"
    elif tree_dict[i]["right"] == -1 and tree_dict[i]["left"] == -1:
        node_type = "leaf"
    else:
        node_type = "internal node"
        
    print(f"node {i}: parent = {parent}, sibling = {sibling}, degree = {degree}, depth = {depth}, height = {height}, {node_type}")

Submission status: Accepted

Solution code:
n=int(input())
p_list=[-1]*n
s_list=[-1]*n
c_list=[0]*n
degree=[0]*n
depth=[0]*n
height=[0]*n
type=[0]*n
for _ in range(n):
    id,l,r=map(int,input().split())
    c_list[id]=[l,r]
    if l!=-1 and r!=-1:
        degree[id]=2
        type[id]="internal node"
        p_list[l]=id
        p_list[r]=id
        s_list[l]=r
        s_list[r]=l
    elif r!=-1:
        degree[id]=1
        type[id]="internal node"
        p_list[r]=id
        s_list[r]=l
    elif l!=-1:
        degree[id]=1
        type[id]="internal node"
        p_list[l]=id
        s_list[l]=r
    else:
        degree[id]=0
        type[id]="leaf"
root=p_list.index(-1)
type[root]="root"
def dsf1(v,d):
    if v!=-1:
        depth[v]=d
        dsf1(c_list[v][0],d+1)
        dsf1(c_list[v][1],d+1)
dsf1(root,0)
def dsf2(v):
    if c_list[v]==[-1,-1]:
        height[v]=0
    else:
        dsf2(c_list[v][0])
        dsf2(c_list[v][1])
        height[v]=max(height[c_list[v][0]],height[c_list[v][1]])+1
dsf2(root)
for i in range(n):
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(i,p_list[i],s_list[i],degree[i],depth[i],height[i],type[i]))

Submission status: Accepted

Solution code:
n = int(input())
lst = [list(map(int,input().split())) for i in range(n)]
B = [lst[i][0] for i in range(n)]
node = [[] for i in range(n)]

def Insertion_Sort(lst,B,n):
    for i in range(1,n):
        v = B[i]
        w = lst[i]
        j = i-1
        while j>=0 and B[j]>v:
            B[j+1]=B[j]
            lst[j+1]=lst[j]
            j-=1
        B[j+1]=v
        lst[j+1]=w
        
def find_root():
    A = []
    for i in range(n):
        A.extend(lst[i][1:])
    for i in range(n):
        if not i in A:
            return i

def make_node(arg_parent, arg_sibling, arg_num, arg_depth):
    if arg_num == root:
        type = "root"
    elif lst[arg_num][1] == lst[arg_num][2] == -1:
        type = "leaf"
    else:
        type = "internal node"
    children_lst = lst[arg_num][1:]
    degree = 0
    for i in children_lst:
        if i != -1:
            degree+=1
    height = -1
    node[arg_num] = [arg_parent, arg_sibling, degree, arg_depth, height, type]
    if children_lst[0]!=-1:
        make_node(arg_num, children_lst[1], children_lst[0], arg_depth+1)
    if children_lst[1]!=-1:
        make_node(arg_num, children_lst[0], children_lst[1], arg_depth+1)

def make_height(arg_num, arg_height):
    if arg_height > node[arg_num][4]:
        node[arg_num][4] = arg_height
        if node[arg_num][0] != -1:
            make_height(node[arg_num][0], arg_height+1)

def make_height_0_list():
    A = []
    for i in range(n):
        if node[i][2] == 0:
            A.append(i)
    return A

Insertion_Sort(lst, B, n)
root = find_root()
make_node(-1, -1, root, 0)
height_0_list = make_height_0_list()
for i in height_0_list:
    make_height(i, 0)

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

Submission status: Accepted

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


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


N = int(input())
btree = [Node(-1, -1, -1) for i in range(N)]
root_cand_list = [i for i in range(N)]
depth = [-1 for i in range(N)]
height = [-1 for i in range(N)]
degree = [0 for i in range(N)]
sibling = [-1 for i in range(N)]


def main():

    for i in range(N):
        num, left, right = map(int, input().split())

        if left != -1:
            btree[num].left = left
            btree[left].parent = num
            root_cand_list.remove(left)
        if right != -1:
            btree[num].right = right
            btree[right].parent = num
            root_cand_list.remove(right)

    setDepth(root_cand_list[0], 0)
    setHeight(root_cand_list[0])
    showBTree()


def setDepth(num, d):
    depth[num] = d
    node = btree[num]
    dgr = 0
    if node.left != -1:
        setDepth(node.left, d + 1)
        dgr += 1
    if node.right != -1:
        setDepth(node.right, d + 1)
        dgr += 1

    if node.parent != -1:
        parent = btree[node.parent]
        if parent.left != -1 and parent.left != num:
            sibling[num] = parent.left
        elif parent.right != -1 and parent.right != num:
            sibling[num] = parent.right

    degree[num] = dgr


def setHeight(num):
    lh = 0
    rh = 0
    if btree[num].left != -1:
        lh = setHeight(btree[num].left)
    if btree[num].right != -1:
        rh = setHeight(btree[num].right)

    if btree[num].left == -1 and btree[num].right == -1:
        # 葉についた時
        height[num] = 0
        h = 1
    else:
        height[num] = max(lh, rh)
        h = max(lh, rh) + 1
    return h


def showBTree():
    for i in range(N):
        if depth[i] == 0:
            TYPE = "root"
        elif height[i] == 0:
            TYPE = "leaf"
        else:
            TYPE = "internal node"

        print("node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}".format(i, btree[i].parent, sibling[i], degree[i], depth[i], height[i], TYPE))


if __name__ == '__main__':
    main()