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):
NIL = -1
MAX = 25


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


T = [Node() for i in range(MAX)]


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


def set_depth(u, d):
    T[u].depth = d
    if T[u].left != NIL:
        set_depth(T[u].left, d + 1)
    if T[u].right != NIL:
        set_depth(T[u].right, d + 1)


if __name__ == '__main__':
    n = int(raw_input())
    for i in range(n):
        u, left, right = map(int, raw_input().split())
        if left != NIL:
            T[left].parent = u
            T[u].left = left
        if right != NIL:
            T[right].parent = u
            T[u].right = right
        if left != NIL and right != NIL:
            T[left].sibling = right
            T[right].sibling = left

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

    set_height(root)
    set_depth(root, 0)
    for i in range(n):
        print "node %d: parent = %d, sibling = %d," % (
            i, T[i].parent, T[i].sibling),

        degree = 0
        if T[i].left != NIL:
            degree += 1
        if T[i].right != NIL:
            degree += 1
        print "degree = %d," % degree,

        print "depth = %d, height = %d," % (T[i].depth, T[i].height),

        if T[i].parent == NIL:
            print "root"
        elif T[i].left == NIL and T[i].right == NIL:
            print "leaf"
        else:
            print "internal node"

Solution (Python):
class Node_information():
    def __init__(self):
        self.id = -1
        self.parent = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = ""
        self.left = -1
        self.right = -1
        self.sibling = -1

def get_tree_id_type(left, right):
    if left == -1 and right == -1:
        return "leaf"
    else:
        return "internal node"

def get_tree_id_degree(left, right):
    if left == -1 and right == -1:
        return 0
    elif left != -1 and right != -1:
        return 2
    else:
        return 1

def get_depth(tree_information, now_id, now_depth):
    tree_information[now_id].depth = now_depth
    if tree_information[now_id].left != -1:
        get_depth(tree_information, tree_information[now_id].left, now_depth + 1)
    if tree_information[now_id].right != -1:
        get_depth(tree_information, tree_information[now_id].right, now_depth + 1)

def get_height(tree_information, now_id):
    h1 = 0
    h2 = 0
    if tree_information[now_id].left != -1:
        h1 = get_height(tree_information, tree_information[now_id].left)
    if tree_information[now_id].right != -1:
        h2 = get_height(tree_information, tree_information[now_id].right)
    tree_information[now_id].height = max(h1,h2)
    return tree_information[now_id].height + 1

def print_tree_information(tree_information, N):
    for i in range(N):
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
        .format(tree_information[i].id,tree_information[i].parent,tree_information[i].sibling,tree_information[i].degree,
        tree_information[i].depth,tree_information[i].height,tree_information[i].type))

def main():
    N = int(input())
    tree_information = list()
    for i in range(N):
        tree_information.append(Node_information())
    for i in range(N):
        information = [int(i) for i in input().split()]
        tree_information[information[0]].id = information[0]
        tree_information[information[0]].left = information[1]
        tree_information[information[0]].right = information[2]
        if information[1] != -1:
            tree_information[information[1]].parent = information[0]
        if information[2] != -1:
            tree_information[information[2]].parent = information[0]
        if information[1] != -1 and information[2] != -1:
            tree_information[information[1]].sibling = information[2]
            tree_information[information[2]].sibling = information[1]
        tree_information[information[0]].type = get_tree_id_type(tree_information[information[0]].left,tree_information[information[0]].right)
        tree_information[information[0]].degree = get_tree_id_degree(tree_information[information[0]].left,tree_information[information[0]].right)
    for i in range(N):
        if tree_information[i].parent == -1:
            tree_information[i].type = "root"
            get_depth(tree_information,i,0)
            break
    for i in range(N):
        if tree_information[i].type == "root":
            get_height(tree_information,i)
            break
    print_tree_information(tree_information,N)

if __name__ == "__main__":
    main()

Solution (Python):
class Node2:
    def __init__(self):
        self.parent = -1
        self.left = -1
        self.right = -1
    
def getSibling(u):
    if Nodes[u].parent == -1:
        return -1
    p = Nodes[u].parent
    if Nodes[p].left == u:
        return Nodes[p].right
    else:
        return Nodes[p].left

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

def getDegree(u):
    if Nodes[i].left != -1 and Nodes[i].right != -1:
        return 2
    elif Nodes[i].left == -1 and Nodes[i].right == -1:
        return 0
    else:
        return 1

def getHeight(u):
    a = 0
    b = 0
    if Nodes[u].left != -1:
        a = getHeight(Nodes[u].left) + 1
    if Nodes[u].right != -1:
        b = getHeight(Nodes[u].right) + 1
    return max(a, b)

def getType(u):
    if Nodes[u].parent == -1:
        return "root"
    elif Nodes[u].right != -1 or Nodes[u].left != -1:
        return "internal node"
    else:
        return "leaf"
    
def printNode(u):
    print_str = "node " + str(u) + ": parent = " + str(Nodes[u].parent) + ", "
    print_str = print_str + "sibling = " + str(getSibling(u)) + ", "
    print_str = print_str + "degree = " + str(getDegree(u)) + ", "
    print_str = print_str + "depth = " + str(getDepth(u)) + ", "
    print_str = print_str + "height = " + str(getHeight(u)) + ", " + getType(u)
    print(print_str)
    
        

    

n = int(input())

Nodes = []
for i in range(n):
    tmp_obj = Node2()
    Nodes.append(tmp_obj)


for i in range(n):
    num, left, right = map(int, input().split())
    Nodes[num].left = left
    Nodes[num].right = right
    if left != -1:
        Nodes[left].parent = num
    if right != -1:
        Nodes[right].parent = num
    

for i in range(n):
    printNode(i)

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


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


def main():
    n = int(input())
    global Nodes
    Nodes = [Node() for i in range(n)]

    for i in range(n):
        id, *children = map(int, input().split())
        left = children[0]
        right = children[1]
        if left != -1 and right != -1:
            Nodes[id].type = "internal node"
            Nodes[id].degree = 2
            Nodes[id].left = left
            Nodes[id].right = right
            Nodes[left].sibling = right
            Nodes[right].sibling = left
        elif left != -1 or right != -1:
            Nodes[id].type = "internal node"
            Nodes[id].degree = 1
            if left != -1:
                Nodes[id].left = left
            else:
                Nodes[id].left = right
        else:
            Nodes[id].type = "leaf"
            Nodes[id].degree = 0
        for child in children:
            if child != -1:
                Nodes[child].parent = id

    rootid = ""
    for i, node in enumerate(Nodes):
        if node.parent == -1:
            rootid = i
    Nodes[rootid].type = "root"
    dfs(rootid)

    for i, node in enumerate(Nodes):
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
            i, node.parent, node.sibling, node.degree, node.depth, node.height, node.type))


if __name__ == '__main__':
    main()

Solution (Python):
def calc_height(list_child, id_now):
    height_left = 0
    height_right = 0

    id_child_left = list_child[id_now][0]
    if id_child_left != -1:
        height_left = calc_height(list_child, id_child_left) + 1
    
    id_child_right = list_child[id_now][1]
    if id_child_right != -1:
        height_right = calc_height(list_child, id_child_right) + 1

    return max(height_left, height_right)



n = int(input())


list_child = [[] for _ in range(n)]
list_parent = [-1 for _ in range(n)]

for _ in range(n):

    id, *C = map(int, input().split())

    list_child[int(id)].extend(C)

    for c in C:
        if c == -1:
            continue

        list_parent[int(c)] = int(id)



for id in range(n):

    parent = list_parent[id]

    if parent == -1:
        sibling = -1
    else:
        if list_child[parent][0] == id:
            sibling = list_child[parent][1]
        else:
            sibling = list_child[parent][0]

    degree = 2 - list_child[id].count(-1)

    depth = 0
    parent_now = parent

    while parent_now != -1:
        depth += 1
        parent_now = list_parent[parent_now]


    if depth == 0:
        type_node = "root"
        height = calc_height(list_child, id)
    elif list_child[id][0] == list_child[id][1] == -1:
        type_node = "leaf"
        height = 0
    else:
        type_node = "internal node"
        height = calc_height(list_child, id)

    print(f"node {id}: parent = {parent}, sibling = {sibling}, degree = {degree}, depth = {depth}, height = {height}, {type_node}")

Solution (Python):
n = int(input())

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

    def setChildNodes(self, r, l):
        self.right = r
        self.left = l
        if r == -1 and l == -1:
            self.degree = 0
        elif r != -1 and l != -1:
            self.degree = 2
        else:
            self.degree = 1

    def setParent(self, parent):
        self.parent = parent

    def getParent(self):
        return self.parent

    def setSibling(self, sibling):
        self.sibling = sibling

    def recDepth(self, depth, nodes):
        self.depth = depth
        rheight = -1
        lheight = -1
        if self.right != -1:
            rheight = nodes[self.right].recDepth(self.depth + 1, nodes)
        if self.left != -1:
            lheight = nodes[self.left].recDepth(self.depth + 1, nodes)
        if self.right == -1 and self.left == -1:
            self.height = 0
        elif rheight > lheight:
            self.height = rheight + 1
        else:
            self.height = lheight + 1

        return self.height

    def printInfo(self):
        info = ''
        if self.parent == -1:
            info = 'root'
        elif self.degree == 0:
            info = 'leaf'
        else:
            info = 'internal node'

        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
              self.id, self.parent, self.sibling, self.degree,
              self.depth, self.height, info))

nodes = []

for i in range(n):
    nodes.append(Node(i, -1, -1))

for i in range(n):
    arr = list(map(int, input().split()))
    nodes[arr[0]].setChildNodes(arr[1], arr[2])
    if arr[1] != -1:
        nodes[arr[1]].setParent(arr[0])
    if arr[2] != -1:
        nodes[arr[2]].setParent(arr[0])
    if arr[1] != -1 and arr[2] != -1:
        nodes[arr[1]].setSibling(arr[2])
        nodes[arr[2]].setSibling(arr[1])

for i in range(n):
    if nodes[i].getParent() == -1:
        root = nodes[i]

root.recDepth(0, nodes)

for node in nodes:
    node.printInfo()

Solution (Python):
NIL = -1


class Node():
    def __init__(self, p, l, r):
        self.p = p
        self.l = l
        self.r = r
        self.s = NIL
        self.deg = NIL
        self.dep = NIL
        self.h = NIL


def set_attr(u):
    def set_height(u_):
        h1 = 0
        h2 = 0
        if T[u_].l != NIL:
            h1 = set_height(T[u_].l) + 1
        if T[u_].r != NIL:
            h2 = set_height(T[u_].r) + 1
        res = h1 if h1 > h2 else h2
        T[u_].h = res
        return res

    def set_depth(u_, d):
        if u_ == NIL:
            return
        T[u_].dep = d
        set_depth(T[u_].l, d + 1)
        set_depth(T[u_].r, d + 1)

    set_height(u)
    set_depth(u, 0)


N = int(input())
T = [Node(NIL, NIL, NIL) for _ in range(N)]
for _ in range(N):
    n, l, r = map(int, input().split())
    T[n].l = l
    T[n].r = r
    deg = 0
    if l != NIL:
        T[l].p = n
        deg += 1
    if r != NIL:
        T[r].p = n
        deg += 1
    if l != NIL and r != NIL:
        T[r].s = l
        T[l].s = r
    T[n].deg = deg
root = 0
for n, t in enumerate(T):
    if t.p == NIL:
        root = n
set_attr(root)
for n, t in enumerate(T):
    if t.p == NIL:
        type_ = 'root'
    elif t.l == NIL and t.r == NIL:
        type_ = 'leaf'
    else:
        type_ = 'internal node'
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, '
          'height = {}, {}'.format(n, t.p, t.s, t.deg, t.dep, t.h, type_))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

nodedict = {}

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

    def __repr__(self):
        return str(self.__dict__)

    def get_height(self):
        if self.height != -1:
            pass
        else:
            if self.degree == 0:
                self.height = 0
            else:
                lh, rh = 0, 0
                if self.left != -1:
                    lh = nodedict[self.left].get_height()
                if self.right != -1:
                    rh = nodedict[self.right].get_height()
                self.height = max(lh, rh) + 1

        return self.height

def assign_info(node, current_depth):
    node.depth = current_depth
    if node.left != -1:
        left = nodedict[node.left]
        left.parent = node.id
        left.sibling = node.right
        assign_info(left, current_depth + 1)

    if node.right != -1:
        right = nodedict[node.right]
        right.parent = node.id
        right.sibling = node.left
        assign_info(right, current_depth + 1)

def solve():
    n = int(input())

    
    childlist = []
    for i in range(n):
        id, left, right = map(int, input().split())
        nodedict[id] = Node(id, left, right)
        childlist.append(left)
        childlist.append(right)


    
    rootid = -1
    for i in range(n):
        if i not in childlist:
            rootid = i

    
    assign_info(nodedict[rootid], 0)

    
    for i in range(n):
        nodedict[i].get_height()

    
    for i in range(n):
        node = nodedict[i]
        if node.depth == 0:
            type = "root"
        elif node.height == 0:
            type = "leaf"
        else:
            type = "internal node"

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

solve()

Solution (Python):
class Node:
    def __init__(self, idnum):
        self.id = idnum
        self.parent = -1
        self.left = -1
        self.right = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = "root"

n = int(input())
T = [Node(i) for i in range(n)]
for ni in range(n):
    idnum, left, right = [int(i) for i in input().split()]
    T[idnum].left = left
    T[idnum].right = right
    T[idnum].degree = 2 - [left, right].count(-1)
    if left != -1:
        T[left].parent = idnum
        T[left].sibling = right
    if right != -1:
        T[right].parent = idnum
        T[right].sibling = left



leaf_id = []
for ni in range(n):
    if T[ni].parent == -1:
        T[ni].type = "root"
        root_id = ni
    elif T[ni].degree == 0:
        T[ni].type = "leaf"
        leaf_id.append(ni)
    else:
        T[ni].type = "internal node"

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

def setHeight(p, h):
    if T[p].height < h:
        T[p].height = h
    if T[p].parent != -1:
        setHeight(T[p].parent, h+1)

for l in leaf_id:
    setHeight(l, 0)


for ni in range(n):
    print("node "+str(T[ni].id)+\
        ": parent = "+str(T[ni].parent)+\
            ", sibling = "+str(T[ni].sibling)+\
                ", degree = "+str(T[ni].degree)+\
                    ", depth = "+str(T[ni].depth)+\
                        ", height = "+str(T[ni].height)+\
                            ", "+T[ni].type)

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

def get_depth(u, p):
  D[u] = p
  if result[u].right is not None:
    get_depth(result[u].right, p)
  if result[u].left is not None:
    get_depth(result[u].left, p+1)

def get_depth_1(u, p):
  i = u
  d = 0
  while result[u].parent != -1:
    u = result[u].parent
    d += 1
  D[i] = d

def get_hight(H, u):
  lh, rh = 0, 0
  if result[u].left != -1:
    lh = get_hight(H, result[u].left)+1
  if result[u].right != -1:
    rh = get_hight(H, result[u].right)+1

  H[u] = max(lh, rh)
  return H[u]

n = int(input())
node  = [list(map(int, input().split())) for _ in range(n)] 
result = [Node() for _ in range(n)]
D = [0 for _ in range(n)]
H = [0 for _ in range(n)]


def initiate(li):
  for l in li:
    n = l[0]
    left = l[1]
    right = l[2]
    if left != -1:
      result[left].parent = n
      result[n].left = left
    if right != -1:
      result[right].parent = n
      result[n].right = right


initiate(node)

for u in range(n):
  get_depth_1(u, 0)
  
for u in range(n):
    get_hight(H, u)

final = []

for i in range(n):
  node = i 
  parent = result[node].parent 
  depth = D[i]
  height = H[i]
  degree = 0
  if result[node].left == -1 and result[node].right == -1:
    typ = "leaf"
    degree = 0
  elif result[node].left >= 0 and result[node].right >= 0:
    typ = "internal node"
    degree = 2
  else:
    degree = 1
    typ = "internal node"

  if parent == -1:
    typ = "root"
  if result[parent].left == node:
    sibling = result[parent].right
  else:
    sibling = result[parent].left
  print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(node, parent, sibling, degree, depth, height, typ))

Solution (Python):
class Node:
    def __init__(self, data):
        self.data = data 
        self.depth = None
        self.children = None

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

Solution (Python):
class Node:
    def __init__(self, id):
        self.id = id
        self.parent = -1
        self.left = -1
        self.right = -1
    
    def get_depth(self):
        if self.parent == -1:
            return 0
        else:
            return nodes[self.parent].get_depth() + 1

    def get_degree(self):
        degree = 0
        if self.left != -1:
            degree += 1
        if self.right != -1:
            degree += 1
        return degree

    def get_height(self):
        
        
        max_height = 0
        if self.left != -1:
            max_height = nodes[self.left].get_height() + 1
            
        if self.right != -1:
            max_height = max(max_height, nodes[self.right].get_height() + 1)
            
        return max_height
    
    def get_sibling(self):
        if self.parent == -1:
            return -1
        
        if nodes[self.parent].left == self.id:
            return nodes[self.parent].right
        else:
            return nodes[self.parent].left

    def get_type(self):
        if self.parent == -1:
            return 'root'
        elif self.left == -1 and self.right == -1:
            return 'leaf'
        else:
            return 'internal node'

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


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

    
    if left != -1:
        nodes[left].parent = i
    if right != -1:
        nodes[right].parent = i

    
    
    
    
    
    
    
    
    



for i in range(n):
    print('node {id}: parent = {p}, sibling = {s}, degree = {degree}, depth = {depth}, height = {height}, {type}'.format(
        id=i,
        p=nodes[i].parent,
        s=nodes[i].get_sibling(),
        degree=nodes[i].get_degree(),
        depth=nodes[i].get_depth(),
        height=nodes[i].get_height(),
        type=nodes[i].get_type(),
    ))

Solution (Python):
class Tree(object):
    def __init__(self):
        self.nodes = {}
        self.root = None

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

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

    def set_depth(self):
        for node in self.nodes.values():
            if node.type == 'root':
                self.root = node
                break
        self.root._set_depth(0)

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


class Node(object):
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.children = []
        self.depth = None
        self.height = None
        self.type = 'root'
        self.bro = None

    def add_child(self, child):
        child.bro = len(self.children)
        self.children.append(child)
        child.parent = self
        child.update_nodetype()
        if self.parent:
            self.update_nodetype()

    def update_nodetype(self):
        if self.parent:
            if self.children:
                self.type = 'internal node'
            else:
                self.type = 'leaf'
        else:
            self.type = 'root'

    def _set_depth(self, depth):
        self.depth = depth
        for child in self.children:
            child._set_depth(depth+1)

    def _set_height(self):
        
        if not self.children:
            self.height = 0
        else:
            if self.height:
                pass
            else:
                height = 0
                for child in self.children:
                    child._set_height()
                    height = max(child.height, height)
                self.height = height + 1

    def get_sib(self):
        if not self.parent:
            return -1
        else:
            bros = self.parent.children
            if len(bros) == 1:
                return -1
            else:
                if self.bro == 0:
                    return bros[1].id
                else:
                    return bros[0].id

    def __str__(self):
        parent = self.parent.id if self.parent else -1
        sib = self.get_sib()
        deg = len(self.children)
        dep = self.depth
        h = self.height
        str = 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(id, parent, sib, deg, dep, h, self.type)
        return str


tree = Tree()
n = int(input())
for i in range(n):
    tmp = list(map(int, input().split()))
    id = tmp[0]
    children = tmp[1:]
    tree.add_node(id)
    for c in children:
        if c != -1:
            tree.add_child(id, c)
tree.set_depth()
tree.set_height()
for id in range(n):
    print(tree.nodes[id])

Solution (Python):
n = int(input())
parent = [-1] * n
left   = [-1] * n
right  = [-1] * n
sibling = [-1] * n
degree  =  [0] * n
depth   =  [0] * n
for i in range(n):
    x = list(map(int, input().split()))
    left[x[0]]  = x[1]
    right[x[0]] = x[2]
    children = 0
    if x[1] != -1:
        parent[x[1]] = x[0]
        sibling[x[1]] = x[2]
        children += 1
    if x[2] != -1:
        parent[x[2]] = x[0]
        sibling[x[2]] = x[1]
        children += 1
    degree[x[0]] = children
def setDepth(u, p, d):
    d[u] = p
    if right[u] != -1:
        setDepth(right[u], p + 1, d)
    if left[u] != -1:
        setDepth(left[u], p + 1, d)
    return d
def getHeight(u, p, height):
    height += [p]
    if right[u] != -1:
        getHeight(right[u], p + 1, height)
    if left[u] != -1:
        getHeight(left[u], p + 1, height)
    return max(height)
def howNode(u):
    if parent[u] == -1:
        return 'root'
    elif left[u] == right[u] == -1:
        return 'leaf'
    else:
        return 'internal node'
root = parent.index(-1)
setDepth(root, 0, depth)
for i in range(n):
    print('node '+str(i)+': parent = '+str(parent[i])
    +', sibling = '+str(sibling[i])+', degree = '+
    str(degree[i])+', depth = '+str(depth[i])+', height = '
    +str(getHeight(i, 0, []))+', '+howNode(i))

Solution (Python):
n = int(input())

class Node():
    def __init__(self,id):
        self.id = id
        self.child = []
        self.parent = -1

    def addChild(self,child):
        self.child = child

    def setParent(self,parent):
        self.parent = parent

nodes = {}
for i in range(n):
    line = list(input().split(" "))
    id = int(line[0])
    if not id in nodes:
        nodes[id] = Node(id)
    child = []
    for j in range(1,3):
        if not int(line[j]) == -1:
            child.append(int(line[j]))
    nodes[id].addChild(child)

    for ele in child:
        if not ele in nodes:
            nodes[ele] = Node(ele)
        nodes[ele].setParent(id)

def culcHeight(nodes,id,counter):
    objNode = nodes[id]
    children = objNode.child
    if children == []:
        return counter
    else:
        counter += 1
        results = []
        for chili in children:
            a = culcHeight(nodes,chili,counter)
            results.append(a)
        return max(results)

for i in sorted(nodes):
    node = nodes[i]
    ans = ''
    ans += 'node ' + str(i) + ': parent = '
    ans += str(node.parent) + ', sibling = '


    if node.parent == -1:
        ans += str(-1)
        children = []
    else:
        children = nodes[node.parent].child
        if children == [node.id]:
            ans += str(-1)
        else:
            for k in children:
                if not k == i:
                    ans += str(k)



    ans += ', degree = ' + str(len(node.child))


    ans += ', depth = '


    startnode = node
    count = 0
    while not startnode.parent == -1:
        startnode = nodes[startnode.parent]
        count += 1
    ans += str(count)


    ans += ', height = '
    ans += str(culcHeight(nodes,i,0))
    ans += ', '
    if node.parent == -1:
        type = 'root'
    else:
        if node.child == []:
            type = 'leaf'
        else:
            type = 'internal node'
    ans += type
    print(ans)