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):
        self.p = -1
        self.l = -1
        self.r = -1

n = int(input())
T = [Node() for _ in range(n)]
for _ in range(n):
    i,left,right = map(int,input().split())
    T[i].l = left
    T[i].r = right
    if left != -1: T[left].p = i
    if right != -1: T[right].p = i

sib = [-1]*n
deg = [0]*n
dep = [0]*n
hei = [0]*n
ntype = ["internal node"]*n

def rec(u,d):
    dep[u] = d
    l = T[u].l
    r = T[u].r
    h1 = h2 = 0
    if l != -1:
        sib[l] = r
        deg[u] += 1
        h1 = rec(T[u].l,d+1)
    if r != -1:
        sib[r] = l
        deg[u] += 1
        h2 = rec(T[u].r,d+1)
    if deg[u] == 0:
        if ntype[u] != "root": ntype[u] = "leaf"
        hei[u] = 0
        return 1
    else:
        h = max(h1,h2)
        hei[u] = h
        return h+1

root = 0
while T[root].p != -1: root += 1
ntype[root] = "root"
rec(root,0)

for i in range(n):
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(i,T[i].p,sib[i],deg[i],dep[i],hei[i],ntype[i]))

Submission status: Accepted

Solution code:
# Binary tree 二分木の表現


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


def settype(u):
    if T[u].parent == -1:
        Type[u] = "root"
    elif Deg[u] == 0:
        Type[u] = "leaf"
    else:
        Type[u] = "internal node"


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


def setheight(u):
    hl, hr = 0, 0
    if T[u].left != -1:
        hl = setheight(T[u].left) + 1
    if T[u].right != -1:
        hr = setheight(T[u].right) + 1
    H[u] = max(hl, hr)
    return H[u]


n = int(input())
T = [Node() for i in range(n)]
S = [-1 for i in range(n)]
Deg = [0 for i in range(n)]

for i in range(n):
    id, left, right = (int(j) for j in input().split())
    if left != -1:
        T[id].left = left
        T[left].parent = id
        S[left] = right
        Deg[id] += 1
    if right != -1:
        T[id].right = right
        T[right].parent = id
        S[right] = left
        Deg[id] += 1

rootid = -1

for id in range(n):
    if T[id].parent == -1:
        rootid = id
        break

Dep = [-1 for i in range(n)]
setdepth(rootid, 0)

Type = ["" for i in range(n)]
for id in range(n):
    settype(id)

H = [-1 for i in range(n)]
setheight(rootid)

for id in range(n):
    print("node ", id, ": parent = ", T[id].parent, ", sibling = ", S[id], ", degree = ", Deg[id], ", depth = ", Dep[id], ", height = ", H[id], ", ", Type[id], sep="")

Submission status: Accepted

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

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

N = int(input()) 
G =[Node() for _ in range(N)]
for _ in range(N):
    idx,*children = [int(x) for x in input().split()] 
    G[idx].left,G[idx].right = children
    if G[idx].left != -1 and G[idx].right != -1:
        G[G[idx].left].sibling,G[G[idx].right].sibling  = G[idx].right,G[idx].left 
    if G[idx].left != -1 or G[idx].right != -1:
        G[idx].type = "internal node"
    else:
        G[idx].type = "leaf"
    for child in children:
        if child != -1:
            G[child].parent =idx
root = [i for i,x in enumerate(G) if x.parent == -1][0]
G[root].type = "root"
dfs(root)
for i,node in enumerate(G):
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(i,node.parent,node.sibling,(node.left != -1) + (node.right != -1),node.depth,node.height,node.type))

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    A_list = [[int(item) for item in input().split()] for _ in range(N)]
    A_list.sort(key=lambda x:x[0])

    # print(A_list)
    T = [[0 for _ in range(7)] for _ in range(N)]

    # bfs
    def bfs(root):
        que = collections.deque([[root, 0, -1]])
        temp_depth = 0
        while que:
            # print(que)
            temp = que.popleft()
            temp_node = temp[0]
            temp_depth = temp[1]
            temp_parent = temp[2]
            T[temp_node][0] = temp_node
            T[temp_node][1] = temp_parent 
            T[temp_node][4] = temp_depth
            children = A_list[temp_node][1:3]
            cnt = 0
            # print(children)
            for child in children:
                if child >= 0:
                    cnt +=1
                    que.append([child, temp_depth+1, temp_node])
                    # print(que)
            T[temp_node][3] = cnt

            siblings = A_list[temp_parent][1:3]
            for sibling in siblings:
                if sibling != temp_node:
                    T[temp_node][2] = sibling


    def height(node):

        max_depth = 0
        height_que = collections.deque([[node, 0]])

        while height_que:
            temp = height_que.popleft()
            temp_node = temp[0]
            temp_depth = temp[1]
            children = A_list[temp_node][1:3]
            # print(children)
            for child in children:
                if child >= 0:
                    height_que.append([child, temp_depth+1])
            max_depth = max(max_depth, temp_depth)
        
        return max_depth 

    def is_root(node):
        root_check_que = collections.deque([node])
        foot_print = [False for _ in range(N)]

        while root_check_que:
            temp_node = root_check_que.popleft()
            foot_print[temp_node] = True
            children = A_list[temp_node][1:3]

            for child in children:
                if child >= 0 and foot_print[child] == False:
                    root_check_que.append(child)

        return all(foot_print)

    
    for i in range(N):
        if is_root(i):
            root = i
            break

    bfs(root)

    for node, left, right in A_list:

        if T[node][1] == -1:
            T[node][6] = 'root' #type
        elif left == -1 and right == -1:
            T[node][6] = 'leaf'
        else:
            T[node][6] = 'internal node'

        T[node][5] = height(node)


    for node, parent, sibling, degree, depth, height, node_type in T:
        print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(node, parent, sibling, degree, depth, height, node_type))
    
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# Binary Tree


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


class BinaryTree():
    def __init__(self, n):
        self.T = [Node(i) for i in range(n)]

    def set_children(self, idx, l, r):
        node = self.T[idx]
        node.left = l
        node.right = r

        deg = 0
        if l != -1:
            deg += 1
            self.T[l].parent = idx
            self.T[l].sibling = r

        if r != -1:
            deg += 1
            self.T[r].parent = idx
            self.T[r].sibling = l

        node.degree = deg

    def get_root(self):
        for idx, node in enumerate(self.T):
            if node.parent == -1:
                return idx

    def set_type(self):
        for i, node in enumerate(self.T):
            if node.parent == -1:
                node.type = 'root'
            elif node.left == -1 and node.right == -1:
                node.type = 'leaf'
            else:
                node.type = 'internal node'

    def set_depth(self):
        root = self.get_root()
        self.set_depth_rec(root, 0)

    def set_depth_rec(self, idx, depth):
        node = self.T[idx]
        node.depth = depth
        if node.left != -1:
            self.set_depth_rec(node.left, depth+1)
        if node.right != -1:
            self.set_depth_rec(node.right, depth+1)

    def set_height(self):
        root = self.get_root()
        self.set_height_rec(root)

    def set_height_rec(self, idx):
        node = self.T[idx]
        if node.left == -1 and node.right == -1:
            node.height = 0
            return 0

        height = max(
            self.set_height_rec(node.left),
            self.set_height_rec(node.right)
        ) + 1

        node.height = height
        return height


N = int(input())
tree = BinaryTree(N)

for _ in range(N):
    idx, l, r = map(int, input().split())

    tree.set_children(idx, l, r)

tree.set_type()
tree.set_depth()
tree.set_height()

for node in tree.T:
    i = node.idx
    p = node.parent
    s = node.sibling
    deg = node.degree
    dep = node.depth
    h = node.height
    typ = node.type

    print(
        f'node {i}: parent = {p}, sibling = {s}, degree = {deg}, depth = {dep}, height = {h}, {typ}')

Submission status: Accepted

Solution code:
import sys
n = int(input())
class Node:
  def __init__(self):
    self.p = -1 # parent
    self.l = -1 # left most child
    self.r = -1 # right sibling

T = [Node() for _ in range(n)]
D = [0]*n
sys.setrecursionlimit(1500)
def rec(u,p):
  D[u] = p
  if T[u].r != -1: rec(T[u].r,p+1)
  if T[u].l != -1: rec(T[u].l,p+1)

H = [0]*n
def rec1(u):
  r = l = 0
  if T[u].r != -1: r = rec1(T[u].r)+1
  if T[u].l != -1: l = rec1(T[u].l)+1
  H[u] = max(r,l)
  return H[u]
def sib(n):
  if T[n].p == -1:
    return -1
  if T[T[n].p].l == n:
    return T[T[n].p].r
  if T[T[n].p].r == n:
    return T[T[n].p].l
for i in range(n):
    v,l,r = map(int,input().split())
    T[v].r = r
    if r != -1:
      T[r].p = v
    T[v].l = l
    if l != -1:
      T[l].p = v
    #print(v,T[v].p,T[v].l,T[v].r)
#print("a1")
for i in range(n):
  #print(i,T[i].p,T[i].l,T[i].r)
  if T[i].p == -1 : r = i
#print("a2")
rec(r,0)
rec1(r)
#print("a3")
for i in range(n):
  #print(i,T[i].p,T[i].l,T[i].r)
  d = 0
  if T[i].l != -1:
    d += 1
  if T[i].r != -1:
    d += 1  
  if T[i].p == -1:
    kind = "root"
  elif d == 0: kind = "leaf"
  else: kind = "internal node"
  print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
        .format(i,T[i].p,sib(i),d,D[i],H[i],kind))

Submission status: Accepted

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

def GetDepth(T, u):
    d = 0
    n = T[u]

    while n.parent != -1:
        n = T[n.parent]
        d += 1

    return d

def GetHight(T, u, d):

    if T[u].left != -1:
        h1 = GetHight(T, T[u].left, d + 1)
    else:
        h1 = d

    if T[u].right != -1:
        h2 = GetHight(T, T[u].right, d + 1)
    else:
        h2 = d

    return max(h1, h2)

def Main():

    n = int(input())

    T = [Node(-1, -1, -1, -1, -1) for i in range(n)]
    D = [0 for i in range(n)]
    H = [0 for i in range(n)]

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

        if left != -1 and right != -1:
            degree = 2
        elif left == -1 and right == -1:
            degree = 0
        else:
            degree = 1

        T[node_id].left = left
        T[node_id].right = right
        T[node_id].degree = degree

        if left != -1 and right != -1:
            T[left].sibling = right
            T[right].sibling = left

        if left != -1:
            T[left].parent = node_id
        if right != -1:
            T[right].parent = node_id

    for i in range(len(T)):

        if T[i].parent == -1:
            node_type = "root"
        elif T[i].left == -1 and T[i].right == -1:
            node_type = "leaf"
        else:
            node_type = "internal node"

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

Main()

Submission status: Accepted

Solution code:
from collections import defaultdict

class TreeNode():

  def __init__(self, val):
    self.val = val
    self.parent = -1
    self.sibling = -1
    self.left = None
    self.right = None
    self.depth = -1
    self.height = -1

  def node_type(self):
    if self.depth == 0:
      return "root"
    elif self.left or self.right:
      return "internal node"
    else:
      return "leaf"

  def get_degree(self):
    deg = 0
    if self.left: deg += 1
    if self.right: deg += 1

    return deg

  def __str__(self):
    # degree = num of children
    return "node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}".format(
      str(self.val), str(self.parent), str(self.sibling), str(self.get_degree()), str(self.depth), str(self.height), str(self.node_type()))

def calc_depth(root, level):
  if root is None: return
  root.depth = level

  calc_depth(root.left, level+1)
  calc_depth(root.right, level+1)

def calc_height(root):
  if root is None: return 0

  leftHeight = calc_height(root.left)
  rightHeight = calc_height(root.right)

  return 1 + max(leftHeight, rightHeight)

num = int(input())
nodes = defaultdict(int)

for i in range(num):
  ins = list(map(int, input().split()))
  val = ins[0]

  if nodes[val] == 0:
    nodes[val] = TreeNode(val)
  n = nodes[val]

  left_val, right_val = ins[1], ins[2]
  
  if left_val != -1:
    # initalize treenode
    if nodes[left_val] == 0:
      nodes[left_val] = TreeNode(left_val)

    # appending to n.left
    n.left = nodes[left_val]
    n.left.parent = n.val
    # get sibling
    if right_val != -1:
      n.left.sibling = right_val

  if right_val != -1:
    if nodes[right_val] == 0:
      nodes[right_val] = TreeNode(right_val)

    n.right = nodes[right_val]
    n.right.parent = n.val
    if left_val != -1:
      n.right.sibling = left_val

root = [node for node in nodes.values() if node.parent == -1][0]
calc_depth(root, 0)
for i in range(num):
  n  = nodes[i]
  n.height = calc_height(n) - 1

sort_nodes = sorted(nodes.items(), key=lambda x:x[0] )
for _, node in sort_nodes:
  print(node)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
writelines = sys.stdout.writelines
N = int(readline())
L = [None]*N; R = [None]*N
S = [-1]*N
P = [-1]*N
D = [-1]*N
DG = [0]*N
H = [-1]*N
for i in range(N):
    i, l, r = map(int, readline().split())
    L[i] = l; R[i] = r
    if l != -1:
        P[l] = i
        DG[i] += 1
    if r != -1:
        P[r] = i
        DG[i] += 1
    if l != -1 != r:
        S[l] = r; S[r] = l
def dfs(v, d):
    D[v] = d
    H[v] = h = max((dfs(L[v], d+1) if L[v] != -1 else 0), (dfs(R[v], d+1) if R[v] != -1 else 0))
    return h+1
dfs(P.index(-1), 0)
writelines(["node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n" % (i, P[i], S[i], DG[i], D[i], H[i], 'root' if P[i] == -1 else 'leaf' if DG[i] == 0 else 'internal node') for i in range(N)])

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, num=None, parent=None, left=None, right=None, depth=None, height=None, sibling=None
                 , degree=None, type=None):
        self.num = num
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.height = height
        self.sibling = sibling
        self.degree = degree
        self.type = type

    def __str__(self):
        if self.parent is None:
            resParent = '-1'
        else:
            resParent = str(self.parent.num)

        if self.sibling is None:
            resSibling = '-1'
        else:
            resSibling = str(self.sibling.num)

        return 'node ' + str(self.num) + ': parent = ' + resParent + ', sibling = ' + resSibling \
               + ', degree = ' + str(self.degree) + ', depth = ' + str(self.depth) + ', height = ' + str(self.height) \
               + ', ' + self.type

def setDepth(node, depth):
    """
    :param node: Root node (in order to set height value to all nodes underneath
    :param depth: Depth of root node (=0)
    :return: nothing
    """
    if node == None:
        return
    node.depth = depth
    setDepth(node.left, depth+1)
    setDepth(node.right, depth+1)

def setHeight(node):
    """
    :param node: Root node (in order to set height value to all nodes underneath
    :return: height + set height value to all nodes underneatha
    """
    h1, h2 = 0, 0
    if node.left is not None:
        h1 = setHeight(node.left) + 1
    if node.right is not None:
        h2 = setHeight(node.right) + 1
    height = max(h1, h2)
    node.height = height
    return height

def getSibling(node):
    parent = node.parent
    if parent is None:
        return None
    elif parent.left != node and parent.left is not None:
        return parent.left
    elif parent.right != node and parent.right is not None:
        return parent.right
    return None

def getDegree(node):
    if node.left is None and node.right is None:
        return 0
    elif node.left is None or node.right is None:
        return 1
    else:
        return 2

def getType(node):
    if node.parent is None:
        return 'root'
    elif node.left is None and node.right is None:
        return 'leaf'
    else:
        return 'internal node'

# import sys
# sys.stdin = open('input.txt', 'r')

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

# Initiate all nodes
for i in range(n):
    node = Node(i)
    nodes.append(node)

# Set parent, left and right from input
for i in range(n):
    num, leftNum, rightNum = map(int, input().split())
    node = nodes[num]
    if leftNum != -1:
        node.left = nodes[leftNum]
        node.left.parent = node
    if rightNum != -1:
        node.right = nodes[rightNum]
        node.right.parent = node

for node in nodes:
    node.sibling = getSibling(node)
    node.degree = getDegree(node)
    node.type = getType(node)
    if node.type == 'root':
        root = node

setDepth(root, 0)
setHeight(root)

for node in nodes:
    print(node)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

class Node:
    def __init__(self, id):
        self.id = id
        self.parent = -1
        self.sibling = -1
        self.children = []
        self.depth = 0
        self.height = 0
        self.ntype = None
    
    def __str__(self):
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.\
            format(self.id, self.parent, self.sibling, len(self.children), self.depth, self.height, self.ntype)
        
N = int(input())

nodes = [Node(i) for i in range(N)]

# 親子関係解決
for i in range(N):
    id, l, r = [int(i) for i in input().split()]
    deg = 0
    if l >= 0 and r >= 0:
        nodes[id].children += [l, r]
        nodes[l].parent = id
        nodes[l].sibling = r
        nodes[r].parent = id
        nodes[r].sibling = l
        nodes[id].ntype = 'internal node'
    elif l >= 0:
        nodes[l].parent = id
        nodes[id].children.append(l)
        nodes[id].ntype = 'internal node'
    elif r >= 0:
        nodes[r].parent = id
        nodes[id].children.append(r)
        nodes[id].ntype = 'internal node'
    else:  
        nodes[id].ntype = 'leaf'

# rootノード検索
root = -1
for i in range(N):
    if nodes[i].parent == -1:
        root = i
        nodes[i].ntype = 'root'
        break

def nfs(node, dep):
    node.depth = dep
    
    if not node.children:
        node.height = 0
        return 0
    
    for child in node.children:
        h = nfs(nodes[child], dep+1)
        node.height = max(node.height, h+1)
    
    return node.height

nfs(nodes[root], 0)

for node in nodes:
    print(node)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
dicLeft = dd(lambda: -1)
dicRight = dd(lambda: -1)
dicParent = dd(lambda: -1)

n = int(input())
for i in range(n):
  id, left, right = map(int, input().split())
  dicLeft[id] = left
  dicRight[id] = right
  dicParent[left] = id
  dicParent[right] = id

def depth(dicPar, id):
  if dicPar[id] == -1:
    return 0
  else:
    return depth(dicPar, dicPar[id]) + 1

def height(dicLeft, dicRight, id):
  left = dicLeft[id]
  right = dicRight[id]
  if left == -1 and right == -1:
    return 0
  elif left == -1:
    return height(dicLeft, dicRight, right) + 1
  elif right == -1:
    return height(dicLeft, dicRight, left) + 1
  else:
    return max(height(dicLeft, dicRight, left), height(dicLeft, dicRight, right)) + 1

def degree(dicLeft, dicRight, id):
  counter = 0
  if dicLeft[id] != -1:
    counter += 1
  if dicRight[id] != -1:
    counter += 1
  return counter

def sibling(dicParent, dicLeft, dicRight, id):
  parent = dicParent[id]
  if parent == -1:
    return -1
  else:
    if dicLeft[parent] == id:
      return dicRight[parent]
    elif dicRight[parent] == id:
      return dicLeft[parent]

def nodeType(dicPar, dicLeft, dicRight, id):
  if dicPar[id] == -1:
    return "root"
  elif dicLeft[id] == -1 and dicRight[id] == -1:
    return "leaf"
  else:
    return "internal node"

#print(depth(dicPar, 1))
for id in range(n):
  print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(id, dicParent[id], sibling(dicParent, dicLeft, dicRight, id), degree(dicLeft, dicRight, id), depth(dicParent, id), height(dicLeft, dicRight, id), nodeType(dicParent, dicLeft, dicRight, id)))

Submission status: Accepted

Solution code:
n = int(input())
p = [-1] * n
c = [None] * n
dp = [-1] * n
h = [None] * n
sb = [-1] * n
k = [None] * n
deg = [-1] * n

for i in range(n):
    id, l, r = map(int, input().split())
    c[id] = [l, r]

for i in range(n):
    l, r = c[i]
    if l>=0:
        p[l] = i
    if r>=0:
        p[r] = i

for i in range(n):
    d = 0
    pr = p[i]
    while pr>=0:
        d += 1
        pr = p[pr]
    dp[i] = d
    
def get_height(idx):
    if sum(c[idx]) == -2:
        return 0
    else:
        return max(get_height(c[idx][0]), get_height(c[idx][1])) + 1

h = [get_height(i) for i in range(n)]

for l, r in c:
    if l>=0 and r>=0:
        sb[l] = r
        sb[r] = l
for i in range(n):
    if p[i]==-1:
        k[i]='root'
    elif sum(c[i]) == -2:
        k[i]='leaf'
    else:
        k[i]='internal node'
        
for i in range(n):
    l, r = c[i]
    if l==-1 and r==-1:
        deg[i]=0
    elif l>=0 and r>=0:
        deg[i]=2
    else:
        deg[i]=1
    print('node %i: parent = %i, sibling = %i, degree = %i, depth = %i, height = %i, %s'%(i, p[i], sb[i], deg[i], dp[i], h[i], k[i]))

Submission status: Accepted

Solution code:
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])

    if inp[1] != -1:
        tree[inp[1]]['parent'] = inp[0]
        tree[inp[1]]['sibling'] = inp[2]
    if inp[2] != -1:
        tree[inp[2]]['parent'] = inp[0]
        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']))






# sibling がおかしい

Submission status: Accepted

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

T.sort(key = lambda x: x[0])

def calc_parent(T,data):
    for i in range(n):
        if T[i][1] == data or T[i][2] == data:
            return T[i][0]
    return -1

def calc_sibling(T,data):
    if T[calc_parent(T,data)][1] == data:
        return T[calc_parent(T,data)][2]
    elif T[calc_parent(T,data)][2] == data:
        return T[calc_parent(T,data)][1]
    else:
        return -1

def calc_degree(T,data):
    count = 0
    if T[data][1] != -1:
        count += 1
    if T[data][2] != -1:
        count += 1
    return count

def calc_depth(T,data):
    depth = 0
    while calc_parent(T,data) != -1:
        data = calc_parent(T,data)
        depth += 1
    return depth

def calc_height(T,data):
    if data == -1:
        return -1
    else:
        return max(1+calc_height(T,T[data][1]),
                    1+calc_height(T,T[data][2]))

def calc_type(T,data):
    if calc_parent(T,data) == -1:
        return "root"
    elif calc_degree(T,data) == 0:
        return "leaf"
    else:
        return "internal node"

for i in range(n):
    print("node "+str(i), end="")
    print(": parent = "+str(calc_parent(T,i)),end="")
    print(", sibling = "+str(calc_sibling(T,i)), end="")
    print(", degree = "+str(calc_degree(T,i)), end="")
    print(", depth = "+str(calc_depth(T,i)), end="")
    print(", height = "+str(calc_height(T,i)), end="")
    print(", "+str(calc_type(T,i)))