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.

Solution (Python):
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}")

Solution (Python):
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))

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

Solution (Python):

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))

Solution (Python):
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 = '')

Solution (Python):
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))

Solution (Python):
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())


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'


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)


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}")

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

Solution (Python):

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()

Solution (Python):
NIL = -1

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


def setDepth(tree, depthList, u, depth):
    if u == NIL:
        return
    depthList[u] = depth
    setDepth(tree, depthList, tree[u].left, depth + 1)
    setDepth(tree, depthList, tree[u].right, depth + 1)


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


def getSibling(tree, u):
    if tree[u].parent == NIL:
        return NIL
    if tree[tree[u].parent].left not in (u, NIL):
        return tree[tree[u].parent].left
    if tree[tree[u].parent].right not in (u, NIL):
        return tree[tree[u].parent].right
    return NIL


def printNode(tree, depthList, heightList, u):
    result = 'node %d: ' % u
    result += 'parent = %d, ' % tree[u].parent
    result += 'sibling = %d, ' % getSibling(tree, u)
    deg = 0
    if tree[u].left != NIL:
        deg += 1
    if tree[u].right != NIL:
        deg += 1
    result += 'degree = %d, ' % deg
    result += 'depth = %d, ' % depthList[u]
    result += 'height = %d, ' % heightList[u]

    if tree[u].parent == NIL:
        result += 'root'
    elif tree[u].left == NIL and tree[u].right == NIL:
        result += 'leaf'
    else:
        result += 'internal node'
    print(result)


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

for i in range(n):
    value, left, right = [int(v) for v in input().split()]
    tree[value].left = left
    tree[value].right = right
    if left != NIL:
        tree[left].parent = value
    if right != NIL:
        tree[right].parent = value

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

depthList = [-1] * n
heightList = [-1] * n
setDepth(tree, depthList, root, 0)
setHeight(tree, heightList, root)
for i in range(n):
    printNode(tree, depthList, heightList, i)

Solution (Python):

class Node:
    def is_leaf(self):
        return self.depth > 0 and len(self.degree) == 0
    
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.sibling = None
        self.degree = []
        self.depth = 0
        self.height = 0
    def __str__(self):
        p = self.parent.id if self.parent else -1
        s = self.sibling.id if self.sibling else -1
        d = len(self.degree)
        typ = 'root'
        if self.depth > 0: typ = 'internal node'
        if d == 0 and self.depth > 0: typ = 'leaf'
        h = self.height
        return 'node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}'.format(self.id, p, s, d, self.depth, h, typ)

def calc_cld_depth(nd):
    cs = nd.degree
    for c in cs:
        c.depth = nd.depth + 1
        calc_cld_depth(c)

n = int(input())
rbt = [Node(i) for i in range(n)]
for i in range(n):
    id,left,right = map(int, input().split())
    tgt = rbt[id]
    l,r = None,None
    if not left == -1:
        l = rbt[left]
        l.depth += tgt.depth + 1
        l.parent = tgt
        calc_cld_depth(l)
        tgt.degree.append(l)
    if not right == -1:
        r = rbt[right]
        r.depth += tgt.depth + 1
        r.parent = tgt
        calc_cld_depth(r)
        tgt.degree.append(r)
    if (not left == -1) and (not right == -1):
        l.sibling, r.sibling = r,l
    if left == -1 and right == -1:
        if tgt.parent: tgt.depth = tgt.parent.depth + 1

for c in rbt:
    h = 0
    if c.is_leaf():
        c.height = h
        p = c.parent
        while p:
            h += 1
            if p.height < h: p.height = h
            p = p.parent
for t in rbt: print(t)