Problem:

Binary Tree

A rooted binary tree is a tree with a root node in which every node has at most two children.

Your task is to write a program which reads a rooted binary tree T and prints the following information for each node u of T:

node ID of u

parent of u

sibling of u

the number of children of u

depth of u

height of u

node type (root, internal node or leaf)

If two nodes have the same parent, they are siblings. Here, if u and v have the same parent, we say u is a sibling of v (vice versa).

The height of a node in a tree is the number of edges on the longest simple downward path from the node to a leaf.

Here, the given binary tree consists of n nodes and evey node has a unique ID from 0 to n-1.

Input

The first line of the input includes an integer n, the number of nodes of the tree.

In the next n lines, the information of each node is given in the following format:

id left right

id is the node ID, left is ID of the left child and right is ID of the right child. If the node does not have the left (right) child, the left(right) is indicated by -1.

Output

Print the information of each node in the following format:

node id: parent = p, sibling = s, degree = deg, depth = dep, height = h, type

p is ID of its parent. If the node does not have a parent, print -1.

s is ID of its sibling. If the node does not have a sibling, print -1.

deg, dep and h are the number of children, depth and height of the node respectively.

type is a type of nodes represented by a string (root, internal node or leaf. If the root can be considered as a leaf or an internal node, print root.

Please follow the format presented in a sample output below.

Constraints

1 ≤ n ≤ 25

Sample Input 1

9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1

Sample Output 1

node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node
node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf
node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf
node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node
node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node
node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf
node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf
node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1


Sample output:
node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node
node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf
node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf
node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node
node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node
node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf
node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf
node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf

Submission status: Accepted

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

    def __repr__(self):
        return "{ "+ str(self.parent) + " " + str(self.left) + " " + str(self.right) + " }"



class BinarySearchTree:
    def __init__(self,size):
        self.tree = [Node(-1,-1,-1) for i in range(size+1)]
        self.root = -1

    def add(self,key,right,left):
        self.tree[key].left = left
        self.tree[key].right = right
        self.tree[left].parent = key
        self.tree[right].parent = key 
        #print(self.tree)
        

    def calcHeight(self,next,sum):
        if next == -1:
            return sum -1
        return max(self.calcHeight(self.tree[next].left,sum+1),self.calcHeight(self.tree[next].right,sum+1))

    def calcDepth(self,next):
        #print("height",next)
        if next == -1:
            return -1
        return 1 + self.calcDepth(self.tree[next].parent)
    
    def getType(self,node):
        if node.parent == -1:
            return "root"
        elif node.right == node.left == -1:
            return "leaf"
        return "internal node"
    
    def printAll(self):
        for idx, node in enumerate(self.tree):
            if node.parent == -1:
                self.root = idx
                break
        self.tree.pop()
        for idx, node in enumerate(self.tree):
            parent = node.parent
            sibling = self.tree[node.parent].left
            if sibling == idx:
                sibling = self.tree[node.parent].right
            degree = 0
            if node.left != -1:
                degree += 1
            if node.right != -1:
                degree += 1
            depth = self.calcDepth(idx)
            height = self.calcHeight(idx,0)
            typed = self.getType(node)
            print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(idx,parent,sibling,degree, depth, height,typed))

N = int(input())
BST = BinarySearchTree(N)
for i in range(N):
    Q = list(map(int, input().split()))
    BST.add(Q[0],Q[1],Q[2])
BST.printAll()

Submission status: Accepted

Solution code:
import sys


class Node:
    def __init__(self):
        self.parent = self.left = self.right = None
        self.height = self.depth = None


n = int(sys.stdin.readline())

nodes = [Node() for _ in range(n)]

for _ in range(n):
    id, left, right = map(int, sys.stdin.readline().split())
    if left != -1:
        nodes[id].left = left
        nodes[left].parent = id
    if right != -1:
        nodes[id].right = right
        nodes[right].parent = id


def set_height(id):
    node = nodes[id]
    height = max(
        -1 if child is None else set_height(child)
        for child in (node.left, node.right)
    ) + 1
    node.height = height
    return height


def set_depth(id, depth):
    node = nodes[id]
    node.depth = depth
    for child in (node.left, node.right):
        if child is not None:
            set_depth(child, depth + 1)


root_id = next(i for i, node in enumerate(nodes) if node.parent is None)
set_height(root_id)
set_depth(root_id, 0)

for id, node in enumerate(nodes):
    sibling = -1
    if node.parent is not None:
        parent = nodes[node.parent]
        sibling = parent.right if parent.left == id else parent.left
        if sibling is None:
            sibling = -1

    node_type = 'internal node'
    if node.parent is None:
        node_type = 'root'
    elif node.left is None and node.right is None:
        node_type = 'leaf'

    print(
        (
            'node %d: parent = %d, sibling = %d, ' +
            'degree = %d, depth = %d, height = %d, %s'
        ) % (
            id,
            -1 if node.parent is None else node.parent,
            sibling,
            sum(child is not None for child in (node.left, node.right)),
            node.depth,
            node.height,
            node_type
        ))

Submission status: Accepted

Solution code:


class node:
    def __init__(self,nodeid):

        self.parent = None
        self.parentid = -1
        self.c_leftid = -1
        self.c_left = None
        self.c_rightid = -1
        self.c_right = None
        self.nodeid = nodeid
        self.type = "root"
    def setLeftChild(self,cn):
        self.c_left = cn
        self.c_leftid = cn.nodeid
        cn.parent = self
        cn.parentid = self.nodeid
        cn.setNodeType()
        self.setNodeType()
        return
    def setRightChild(self,cn):
        self.c_right = cn
        self.c_rightid = cn.nodeid
        cn.parent = self
        cn.parentid = self.nodeid
        cn.setNodeType()
        self.setNodeType()
        return
    def getDepth(self):
        cnt = 0
        t = self
        while True:
            if (t.parentid == -1 ):
                break
            t = t.parent
            cnt = cnt + 1
        return cnt
    def setNodeType(self):
        if (self.getDepth() == 0):
            self.type = "root"
        else:
            if ( self.c_rightid == -1 and self.c_leftid == -1 ):
                self.type = "leaf"
            else:
                self.type = "internal node" 
    def getNodeType(self):
        return self.type
    def getSibling(self):
        if ( self.parentid == -1):
            return -1
        i = self.parent
        if ( i.c_rightid == self.nodeid ):
            return i.c_leftid
        elif ( i.c_leftid == self.nodeid):
            return i.c_rightid
    def getHeight(self):
        lcnt = 0
        rcnt = 0
        if (self.c_leftid == -1  and self.c_rightid == -1 ):
            return 0
        elif (self.c_rightid  == -1):
            lcnt = lcnt + self.c_left.getHeight() + 1
        elif (self.c_leftid  == -1):
            rcnt = rcnt + self.c_right.getHeight() + 1
        else:
            lcnt = lcnt + self.c_left.getHeight() + 1
            rcnt = rcnt + self.c_right.getHeight() + 1
        if (lcnt >= rcnt):
            return lcnt
        else:
            return rcnt
    def getDegree(self):
        cnt = 0
        if (self.c_leftid != -1):
            cnt += 1
        if (self.c_rightid != -1):
            cnt += 1
        return cnt
    def showNode(self):
        i1 = self.nodeid
        i2 = self.parentid
        i3 = self.getSibling()
        i4 = self.getDegree()
        i5 = self.getDepth()
        i6 = self.getHeight()
        i7 = self.getNodeType()
        print ('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i1,i2,i3,i4,i5,i6,i7))
        return

nl = []
n = int(input())
for i in range(0,n):
    nl.append(node(i))

for i in range(0,n):
    (a,b,c) = map(int,input().split())
    if (b != -1):
        nl[a].setLeftChild(nl[b])
    if (c != -1):
        nl[a].setRightChild(nl[c])

for i in range(0,n):
    nl[i].showNode()

Submission status: Accepted

Solution code:
class Node:
    parent = ""
    sibling = ""
    depth = ""
    height = ""

    def __init__(self, left, right):
        self.left = left
        self.right = right

        if self.right == -1 and self.left == -1:
            self.degree = 0
            self.type = 'leaf'
        elif self.right == -1 or self.left == -1:
            self.degree = 1
            self.type = 'internal node'
        else:
            self.degree = 2
            self.type = 'internal node'


def add_parent_node_and_depth(nodes, parent_node_no, node_no, depth):
    nodes[node_no].parent = parent_node_no
    nodes[node_no].depth = depth

    left_node_no = nodes[node_no].left
    right_node_no = nodes[node_no].right

    left_height, right_height = 0, 0
    if left_node_no != -1:
        left_height = add_parent_node_and_depth(nodes, node_no, left_node_no, depth+1)
        nodes[left_node_no].sibling = right_node_no
    if right_node_no != -1:
        right_height = add_parent_node_and_depth(nodes, node_no, right_node_no, depth+1)
        nodes[right_node_no].sibling = left_node_no

    if left_node_no == -1 and right_node_no == -1:
        nodes[node_no].height = 0
    else:
        nodes[node_no].height = max(left_height, right_height) + 1
    return nodes[node_no].height


def main():
    n = int(input())
    nodes = {}
    for i in range(n):
        node_no, left, right = [int(x) for x in input().split()]
        nodes[node_no] = Node(left, right)

    lefts = [nodes[x].left for x in nodes]
    rights = [nodes[x].right for x in nodes]
    root_no = list(set(nodes.keys()) - set(lefts + rights))[0]

    nodes[root_no].type = 'root'
    nodes[root_no].sibling = -1
    add_parent_node_and_depth(nodes, -1, root_no, 0)

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

    return

main()

Submission status: Accepted

Solution code:
class Trees():
    def __init__(self):
        self.nodes = {}
    def add_nodes(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)
    def add_child(self, id, child_id1, child_id2):
        for child_id in [child_id1, child_id2]:
            if child_id != -1:
                self.add_nodes(child_id)
                self.nodes[id].add_child_id(self.nodes[child_id])
        if child_id1 != -1:
            self.nodes[child_id1].sibling = child_id2
        if child_id2 != -1:            
            self.nodes[child_id2].sibling = child_id1
        self.nodes[id].left = child_id1
        self.nodes[id].right = child_id2
    def setheight(self, id):
        h1, h2 = 0, 0
        if self.nodes[id].right != -1:
            h1 = self.setheight(self.nodes[id].right) + 1
        if self.nodes[id].left != -1:
            h2 = self.setheight(self.nodes[id].left) + 1
        self.nodes[id].height = max(h1, h2)
        return max(h1, h2)
        

         
class Node():
    def __init__(self, id):
        self.node = id
        self.parent = None
        self.depth = 0
        self.nodetype = 'root'
        self.children = []
        self.sibling = -1
        self.degree = 0
        self.height = 0
        self.left = -1
        self.right = -1
     
    def add_child_id(self, child):
        child.parent = self
        self.children.append(child)
        child.update_depth()
        self.update_nodetype()
        child.update_nodetype()
        self.degree += 1
        
     
    def update_depth(self):
        depth = self.depth
        if self.parent:
            self.depth = self.parent.depth + 1
        if depth != self.depth:
            for child in self.children:
                child.update_depth()
 
     
    def update_nodetype(self):
        if self.depth == 0:
            self.nodetype = 'root'
        elif len(self.children) > 0:
            self.nodetype = 'internal node'
        else:
            self.nodetype = 'leaf'
            

     
    def __str__(self):
        parent = self.parent.node if self.parent else -1
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
            self.node, parent, self.sibling, self.degree, self.depth, self.height, self.nodetype)
     
 
tree = Trees()
 
n = int(input())
 
for i in range(n):
    a = list(map(int,input().split()))
    tree.add_nodes(a[0])
    tree.add_child(id=a[0], child_id1=a[1], child_id2=a[2])

for id in range(n):
    tree.setheight(id)
        

for id in range(n):
    print(f"{tree.nodes[id]}")

Submission status: Accepted

Solution code:
class Node:
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.children=[]
        self.degree=0
        self.depth=-1
        self.state="leaf"
        self.sibling=-1
        self.height=-1




def get_depth(Tree,node,depth):
    for child in node.children:
        Tree[child].depth=depth+1
        get_depth(Tree,Tree[child],depth+1)


def get_height(Tree):
    for node in Tree:
        if(len(node.children)==0):
                node.height=0
                tmp_node=node
                while(tmp_node.parent!=-1):
                        Tree[tmp_node.parent].height=max([tmp_node.height+1, Tree[tmp_node.parent].height])
                        tmp_node=Tree[tmp_node.parent]
                     




Tree=[]
n=int(input())
for i in range(n):
    Tree.append(Node())
for loop in range(n):
    info=list(map(int,input().split()))
    i=info[0]
    Tree[i].name=i
    for j in range(1,len(info)):
        if(info[j]!=-1):
                (Tree[i].children).append(info[j])
                if(info[1]!=-1 and info[2]!=-1):
                        Tree[info[2]].sibling=info[1]
                        Tree[info[1]].sibling=info[2]
                Tree[i].state="internal node"
                Tree[info[j]].parent=i




for node in Tree:
    if(node.parent==-1):
        node.state="root"
        node.depth=0
        get_depth(Tree,node,0)


get_height(Tree)
        


for node in Tree:
    print(f"node {node.name}: parent = {node.parent}, sibling = {node.sibling}, degree = {len(node.children)}, depth = {node.depth}, height = {node.height}, {node.state}")

Submission status: Accepted

Solution code:
import sys

def height(id):
    if children[id]==[]:
        return 0
    if children[id][0]==-1 and children[id][1]==-1:
        return 0
    return max(height(children[id][0]),height(children[id][1]))+1

n = int(sys.stdin.readline())
parent = [-1 for _ in range(n)]
children = [[] for _ in range(n)]
nodes = []
for _ in range(n):
    id, left, right = list(map(int, sys.stdin.readline().split()))
    nodes.append(id)
    children[id] = [left, right]
    if left>=0:  parent[left] = id
    if right>=0: parent[right] = id

for n in sorted(nodes):
    h = height(n)
    p = parent[n]
    if p==-1:    type='root'
    else:
        if h==0: type='leaf'
        else:    type='internal node'
        
    depth = 0
    k=n
    while parent[k]>=0:
        k = parent[k]
        depth+=1

    ss=children[parent[n]]
    if ss[0]==-1 or ss[1]==-1:
        s=-1
    elif n==ss[0]:
        s=ss[1]
    else:
        s=ss[0]

    deg = 0
    if children[n][0]>=0: deg +=1
    if children[n][1]>=0: deg +=1
            
    print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}'.format(n, p, s, deg, depth, h, type))

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():
    "node of the tree structure"
    def __init__(self, parent = -1, left = -1, right = -1):
        self.parent = parent
        self.left = left
        self.right = right

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

def getSibling(u):
    if node_list[u].parent == -1:
        return -1
    if node_list[node_list[u].parent].left != -1 and node_list[node_list[u].parent].left != u:
        return node_list[node_list[u].parent].left
    if node_list[node_list[u].parent].right != -1 and node_list[node_list[u].parent].right != u:
        return node_list[node_list[u].parent].right
    return -1

def getDegree(u):
    count = 0
    if node_list[u].left != -1:
        count += 1
    if node_list[u].right != -1:
        count += 1
    return count

def getDepth(u):
    count = 0
    while node_list[u].parent != -1:
        count += 1
        u = node_list[u].parent
    return count

def getType(u):
    if node_list[u].parent == -1:
        return "root"
    if node_list[u].left == -1 and node_list[u].right == -1:
        return "leaf"
    return "internal node"

n = int(input())
node_list = []
for i in range(n):
    node = Node()
    node_list.append(node)

for i in range(n):
    a,b,c = map(int, input().split())
    node_list[a].left = b
    node_list[a].right = c
    if b != -1:
        node_list[b].parent = a
    if c != -1:
        node_list[c].parent = a
height_list = [-1]*n

for i in range(n):
    print("node", str(i)+":", "parent =", str(node_list[i].parent) + ",", "sibling =", str(getSibling(i)) + ",", "degree =", str(getDegree(i)) + ",", "depth =", str(getDepth(i)) + ",", "height =", str(setHeight(i)) + ",", getType(i))

Submission status: Accepted

Solution code:
NIL = -1
class Node:
  def __init__(self):
    self.parent = NIL
    self.left = NIL
    self.right = NIL
    self.type = NIL
    self.depth = NIL
    self.sibling = NIL
    self.degree = NIL
    self.height = NIL

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

def getDepth(u):
  d = 0
  while T[u].parent != NIL:
    u = T[u].parent
    d += 1
  return d

def getSibling(u):
  if T[u].parent == NIL:
    return NIL
  if T[T[u].parent].left != u and T[T[u].parent].left != NIL:
    return T[T[u].parent].left
  if T[T[u].parent].right != u and T[T[u].parent].right != NIL:
    return T[T[u].parent].right
  return NIL

def getDegree(u):
  deg = 0
  if T[u].left != NIL:
    deg += 1
  if T[u].right != NIL:
    deg += 1
  return deg

n = int(input())
T = [0]*n
for i in range(n):
  T[i] = Node()
for i in range(n):
  id, l, r = map(int,input().split())
  T[id].left = l
  T[id].right = r

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

for i in range(n):
  if T[i].parent == NIL:
    T[i].type = 'root'
  elif T[i].parent != NIL and (T[i].left != NIL or T[i].right != NIL):
    T[i].type = 'internal node'
  else:
    T[i].type = 'leaf'

for i in range(n):
  T[i].depth = getDepth(i)
  T[i].sibling = getSibling(i)
  T[i].degree = getDegree(i)
  T[i].height = setHeight(i)

for i in range(n):
  print('node ',i,': parent = ',T[i].parent,', sibling = ',T[i].sibling,', degree = ',T[i].degree,', depth = ',T[i].depth,', height = ',T[i].height,', ',T[i].type,sep = '')

Submission status: Accepted

Solution code:
n = int(input())
par_kid = {}
not0 = []
for i in range(n):
    a = list(map(int, input().split()))
    if (a[1] != -1 or a[2] != -1):
        par_kid[a[0]] = a[1:]
        not0 += a[1:]
for i in range(n):
    if (i not in not0):
        first_node = i
        break
par_dep = {first_node:(-1,0)}
def pd(f):
    if (len(par_kid) == 0):
        return 0
    A = par_kid[f]
    c = 0
    for a in A:
        if (a == -1):
            c += 1
            continue
        par_dep[a] = (f, par_dep[f][1]+1)
        if (a not in par_kid.keys()):
            c += 1
            continue
        pd(a)
    if (c == len(A)):
        return 0
s = pd(first_node)
height = {}
for i in range(n):
    if (i not in par_kid.keys()):
        k = i
        height[k] = 0
        while True:
            par = par_dep[k][0]
            if (par in height.keys()):
                height[par] = max(height[par], height[k] + 1)
            else:
                height[par] = height[k] + 1
            if (par == -1):
                break
            k = par
for i in range(n):
    if (n == 1):
        print('node 0: parent = -1, sibling = -1, degree = 0, depth = 0, height = 0, root')
    elif (i == first_node):
        if (-1 in par_kid[i]):
            print('node {}: parent = -1, sibling = -1, degree = 1, depth = 0, height = {}, root'.format(i,height[i]))
        else:
            print('node {}: parent = -1, sibling = -1, degree = 2, depth = 0, height = {}, root'.format(i,height[i]))
    elif(i in par_kid.keys()):
        par = par_dep[i][0]
        dep = par_dep[i][1]
        h = height[i]
        A = par_kid[par]
        for a in A:
            if (a != i):
                sib = a
        if (-1 in par_kid[i]):
            print('node {}: parent = {}, sibling = {}, degree = 1, depth = {}, height = {}, internal node'.format(i,par,sib,dep,h))
        else:    
            print('node {}: parent = {}, sibling = {}, degree = 2, depth = {}, height = {}, internal node'.format(i,par,sib,dep,h))
    else:
        par = par_dep[i][0]
        dep = par_dep[i][1]
        h = height[i]
        A = par_kid[par]
        for a in A:
            if (a != i):
                sib = a
        print('node {}: parent = {}, sibling = {}, degree = 0, depth = {}, height = {}, leaf'.format(i,par,sib,dep,h))

Submission status: Accepted

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

n = int(input())

# preparing the tree
tree = []
for _ in range(n):
    tree.append(Node())
for _ in range(n):
    id, left, right = map(int, input().split())
    if left > -1:
        tree[id].left = left
        tree[left].parent = id
    if right > -1:
        tree[id].right = right
        tree[right].parent = id
        
        
def get_type(id):
    if tree[id].parent is None:
        return 'root'
    elif (tree[id].left is None) and (tree[id].right is None):
        return 'leaf'
    else:
        return 'internal node'

# recursively set the depth of each node    
def set_depth(id, d):
    tree[id].depth = d
    if tree[id].left is not None:
        set_depth(tree[id].left, d+1)
    if tree[id].right is not None:
        set_depth(tree[id].right, d+1)

# recursively set the height of each node
def set_height(id):
    if id is None:
        pass
    elif tree[id].type == 'leaf':
        tree[id].height = 0
    else:
        left_id = tree[id].left
        right_id = tree[id].right
        set_height(left_id)
        set_height(right_id)
        
        
        tree[id].height = max(
                0 if left_id is None else tree[left_id].height + 1,  
                0 if right_id is None else tree[right_id].height + 1 
            )
         

def get_num_child(id):
    return (tree[id].left is not None)  + (tree[id].right is not None)

def get_sibling(id):
    if tree[id].type == 'root':
        out = None
    else:
        parent_node = tree[tree[id].parent]
        out = (parent_node.right if (parent_node.left == id) else parent_node.left)
    return (-1 if out is None else out)

# ==========

for id in range(n):
    tree[id].type = get_type(id)
    if tree[id].type == 'root':
        root_id = id
set_depth(root_id, 0)
set_height(root_id)

for id in range(n):
    print(f"node {id}: parent = {-1 if tree[id].parent is None else tree[id].parent}, sibling = {get_sibling(id)}, degree = {get_num_child(id)}, depth = {tree[id].depth}, height = {tree[id].height}, {tree[id].type}")

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self):
        self.nodes = {}
        self.nodes[-1] = None

    def add_node(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)

    def add_child(self, parent_id, left_id, right_id):
        self.add_node(parent_id)
        self.add_node(left_id)
        self.add_node(right_id)
        self.nodes[parent_id].add_child(self.nodes[left_id],
                                        self.nodes[right_id])


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

    def add_child(self, left, right):
        self.left = left
        self.right = right

        self.update_height()

        for child in self.children():
            child.parent = self
            child.update_depth()

    def update_height(self):
        if self.degree():
            self.height = max([child.height + 1 for child in self.children()])
            if self.parent:
                self.parent.update_height()

    def update_depth(self):
        self.depth = self.parent.depth + 1
        for child in self.children():
            child.update_depth()

    def nodetype(self):
        if self.parent:
            if self.degree():
                return 'internal node'
            else:
                return 'leaf'
        else:
            return 'root'

    def degree(self):
        return len(self.children())

    def children(self):
        return [child for child in [self.left, self.right] if child]

    def sibling(self):
        if self.parent and self.parent.degree() == 2:
            if self.parent.left == self:
                return self.parent.right.id
            else:
                return self.parent.left.id
        else:
            return -1

    def __str__(self):
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
            self.id,
            self.parent.id if self.parent else - 1,
            self.sibling(),
            self.degree(),
            self.depth,
            self.height,
            self.nodetype())


tree = Tree()

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

for id in sorted(tree.nodes):
    if id != -1:
        print(tree.nodes[id])

Submission status: Accepted

Solution code:
#ALDS1_7-B Binary Trees
class Node:
    def __init__(self, nid):
        self.nid = nid
        self.parent = None
        self.sibling = None
        self.degree = self.funcDeg
        self.depth = self.funcDep
        self.height = self.funcH
        self.type = self.funcT
        self.left = None
        self.right = None
        
    def funcDeg(self):
        deg = 0
        if self.left:
            deg+=1
        if self.right:
            deg+=1
        return deg
        
    def funcDep(self):
        if self.parent:
            parentD = self.parent.depth()
        else:
            parentD = -1
        return parentD + 1
    
    def funcH(self):
        if self.left:
            leftH = self.left.height()
        else:
            leftH = -1
        if self.right:
            rightH = self.right.height()
        else:
            rightH = -1
        return max(leftH,rightH) + 1
        
    def funcT(self):
        if not self.parent:
            return "root"
        elif self.left or self.right:
            return "internal node"
        else:
            return "leaf"
        
    def dump(self):
        txt = "node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
        print (txt.format(self.nid, -1 if not self.parent else self.parent.nid, -1 if not self.sibling else self.sibling.nid, self.degree(), self.depth(), self.height(), self.type()))
        
n = int(input())
D = {}
for i in range(n):
    D[i] = Node(i)
for i in range(n):
    nid, left, right = [int(i) for i in input().split()]
    if not left == -1 and not right == -1:
        D[right].sibling = D[left]
        D[left].sibling = D[right]
        
    if not left == -1:
        D[nid].left = D[left]
        D[left].parent = D[nid]
            
    if not right == -1:
        D[nid].right = D[right]
        D[right].parent = D[nid]
        
for i in range(n):
    D[i].dump()