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 Tree:
    nodes = []
    def __init__(self):
        self.root = None
    def insert(self, nodenum, leftnum, rightnum):
        if leftnum != -1:
            self.nodes[nodenum].left = self.nodes[leftnum]
            self.nodes[leftnum].type_ = "internal node"
            self.nodes[leftnum].parent = self.nodes[nodenum]
            self.nodes[nodenum].degree += 1
        else:
            self.nodes[nodenum].left = -1
        if rightnum != -1:
            self.nodes[nodenum].right = self.nodes[rightnum]
            self.nodes[rightnum].type_ = "internal node"
            self.nodes[rightnum].parent = self.nodes[nodenum]
            self.nodes[nodenum].degree += 1
        else:
            self.nodes[nodenum].right = -1
        if leftnum != -1 and rightnum != -1:
            self.nodes[leftnum].sibling = rightnum
            self.nodes[rightnum].sibling = leftnum
    def depth(self, node):
        if node.left != -1:
            node.left.depth += node.depth + 1
            self.depth(node.left)
        if node.right != -1:
            node.right.depth += node.depth + 1
            self.depth(node.right)
    def height(self, node):
        if node.left == -1 and node.right == -1:
            node.type_ = "leaf"
            return 0
        elif node.left == -1:
            x = self.height(node.right)
            node.height = x + 1
            return x + 1
        elif node.right == -1:
            x = self.height(node.left)
            node.height = x + 1
            return x + 1
        else:
            x = max(self.height(node.left), self.height(node.right)) + 1
            node.height = x
            return x
class Node:
    def __init__(self, label, left = -1, right = -1):
        self.label = label
        self.type_ = "root"
        self.parent = -1
        self.sibling = -1
        self.depth = 0
        self.height = 0
        self.degree = 0
        self.left = left
        self.right = right

tree = Tree()
n = int(input())
for i in range(n):
    tree.nodes.append(Node(i))
for i in range(n):
    num, left, right = map(int, input().split())
    tree.insert(num, left, right)
for i in tree.nodes:
    if i.parent == -1:
        tree.depth(i)
        tree.height(i)
if n == 1:
    tree.nodes[0].type_ = "root"
for i in tree.nodes:
    print("node {0:}: parent = ".format(i.label), end = "")
    if i.parent == -1:
        print(i.parent, end = "")
    else:
        print(i.parent.label, end = "")
    print(", sibling = {0:}, degree = {1:}, depth = {2:}, height = {3:}, {4:}".format(i.sibling, i.degree, i.depth, i.height, i.type_))

Solution (Python):
from enum import IntEnum


class Attrs(IntEnum):
    LEFT = 0
    RIGHT = 1
    PARENT = 2
    SIBLING = 3
    DEPTH = 4
    HEIGHT = 5


def parents(nodes):
    for i, node in enumerate(nodes):
        if node[Attrs.LEFT] != -1:
            nodes[node[Attrs.LEFT]][Attrs.PARENT] = i
            nodes[node[Attrs.LEFT]][Attrs.SIBLING] = node[Attrs.RIGHT]
        if node[Attrs.RIGHT] != -1:
            nodes[node[Attrs.RIGHT]][Attrs.PARENT] = i
            nodes[node[Attrs.RIGHT]][Attrs.SIBLING] = node[Attrs.LEFT]


def depth_and_heights(nodes):
    def depth(n):
        if nodetype(n) != "root" and n[Attrs.DEPTH] == 0:
            n[Attrs.DEPTH] = depth(nodes[n[Attrs.PARENT]]) + 1
        return n[Attrs.DEPTH]

    def height(n):
        if nodetype(n) != "leaf" and n[Attrs.HEIGHT] == 0:
            if n[Attrs.LEFT] != -1:
                lh = height(nodes[n[Attrs.LEFT]])
            else:
                lh = -1

            if n[Attrs.RIGHT] != -1:
                rh = height(nodes[n[Attrs.RIGHT]])
            else:
                rh = -1
            n[Attrs.HEIGHT] = max(lh, rh) + 1
        return n[Attrs.HEIGHT]

    for node in nodes:
        node[Attrs.DEPTH] = depth(node)
        node[Attrs.HEIGHT] = height(node)


def degree(node):
    if node[Attrs.LEFT] != -1 and node[Attrs.RIGHT] != -1:
        return 2
    elif node[Attrs.LEFT] != -1:
        return 1
    elif node[Attrs.RIGHT] != -1:
        return 1
    else:
        return 0


def nodetype(node):
    if node[Attrs.PARENT] == -1:
        return "root"
    elif node[Attrs.LEFT] == -1 and node[Attrs.RIGHT] == -1:
        return "leaf"
    else:
        return "internal node"


def print_tree(ns):
    parents(ns)
    depth_and_heights(ns)

    for nid, n in enumerate(ns):
        print(("node {}: parent = {}, sibling = {}, degree = {}, " +
               "depth = {}, height = {}, {}").format(nid,
                                                     n[Attrs.PARENT],
                                                     n[Attrs.SIBLING],
                                                     degree(n),
                                                     n[Attrs.DEPTH],
                                                     n[Attrs.HEIGHT],
                                                     nodetype(n)))


def run():
    n = int(input())
    nodes = [None] * n

    for i in range(n):
        nodeid, *attrs = [int(i) for i in input().split()]
        attrs.extend([-1, -1, 0, 0])
        nodes[nodeid] = attrs

    print_tree(nodes)


if __name__ == '__main__':
    run()

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

def input_depth(node, i, n):
    node[i].depth = n
    if node[i].left != -1:
        input_depth(node, node[i].left, n + 1)
    if node[i].right != -1:
        input_depth(node, node[i].right, n + 1)

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

def print_node(node, i):
    print("node " + str(i) + ": ", end = "")
    print("parent = " + str(node[i].parent) + ", ", end = "")
    if node[i].parent == -1:
        print("sibling = -1, ", end = "")
    elif i == node[node[i].parent].left:
        print("sibling = " + str(node[node[i].parent].right) + ", ", end = "")
    else:
        print("sibling = " + str(node[node[i].parent].left) + ", ", end = "")
    print("degree = " + str(node[i].degree) + ", ", end = "")
    print("depth = " + str(node[i].depth) + ", ", end = "")
    print("height = " + str(node[i].height) + ", ", end = "")
    if node[i].parent == -1:
        print("root")
    elif node[i].degree == 0:
        print("leaf")
    else:
        print("internal node")
        
n = int(input())
ns = [Node() for i in range(n)]
for i in range(n):
    p, l, r = map(int, input().split())
    if l != -1:
        ns[p].left = l
        ns[p].degree += 1
        ns[l].parent = p
    if r != -1:
        ns[p].right = r
        ns[p].degree += 1
        ns[r].parent = p

for i in range(n):
    if ns[i].parent == -1:
        input_depth(ns, i, 0)
        input_height(ns, i)
        break

for i in range(n):
    print_node(ns, i)

Solution (Python):
from enum import Enum, auto
import sys

class NodeType(Enum):
    LEAF = auto()
    INTERNAL_NODE = auto()
    ROOT = auto()

class BinaryTreeNode():
    def __init__(self, parent=None, left=None, right=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.sibling = None
        self.degree = None
        self.depth = None
        self.height = None
        self.type = None

n = int(input())
nodes = [BinaryTreeNode() for i in range(n)]
for i in range(n):
    id, left, right = list(map(int, input().split(' ')))
    degree = 0
    if left != -1:
        degree += 1
        nodes[id].left = left
        nodes[left].parent = id
        nodes[left].sibling = right
    if right != -1:
        degree += 1
        nodes[id].right = right
        nodes[right].parent = id
        nodes[right].sibling = left
    nodes[id].degree = degree
    if degree == 0:
        nodes[id].type = NodeType.LEAF
    else:
        nodes[id].type = NodeType.INTERNAL_NODE

root = 0
for i in range(n):
    if nodes[i].parent == None:
        root = i
        nodes[i].type = NodeType.ROOT

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

def set_height(u):
    h1, h2 = 0, 0
    if nodes[u].left != None:
        h1 = set_height(nodes[u].left) + 1
    if nodes[u].right != None:
        h2 = set_height(nodes[u].right) + 1
    nodes[u].height = h1 if h1 > h2 else h2
    return nodes[u].height

set_depth(root, 0)
set_height(root)

for i in range(n):
    parent = -1 if nodes[i].parent == None else nodes[i].parent
    sibling = -1 if nodes[i].sibling == None else nodes[i].sibling
    type = ''
    if nodes[i].type == NodeType.INTERNAL_NODE:
        type = 'internal node'
    elif nodes[i].type == NodeType.LEAF:
        type = 'leaf'
    elif nodes[i].type == NodeType.ROOT:
        type = 'root'
    print('node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d,'%(i, parent, sibling, nodes[i].degree, nodes[i].depth, nodes[i].height), type)

Solution (Python):

"""
Created on Sat May 19 19:34:44 2018
ALDS1_7_B
@author: maezawa
"""

n = int(input())

parent = [-1 for _ in range(n)]
left = [-1 for _ in range(n)]
right = [-1 for _ in range(n)]
height = [None for _ in range(n)]
depth = [None for _ in range(n)]

def set_parent():
    global parent
    for i in range(n):
        if left[i] != -1:
            parent[left[i]] = i
        if right[i] != -1:
            parent[right[i]] = i

    
def set_depth(i, p):
    global depth
    if depth[i] != None:
        return
    depth[i] = p
    if right[i] != None:
        set_depth(right[i], p)
    if left[i] != None:
        set_depth(left[i], p+1)
       
def get_depth(i):
    global depth
    if depth[i] != None:
        return depth[i]
    d = 0
    u = i
    while parent[u] != -1:
        u = parent[u]
        d += 1
    depth[i] = d
    return d

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

def get_sib(i):
    if right[parent[i]] == i:
        return left[parent[i]]
    else:
        return right[parent[i]]
    
def get_deg(i):
    deg = 0
    if right[i] != -1:
        deg += 1
    if left[i] != -1:
        deg += 1
    return deg    

def get_height(i):
    return height[i]
    
for i in range(n):
    line = list(map(int, input().split()))
    left[line[0]] = line[1]
    right[line[0]] = line[2]

set_parent()

for i in range(n):
    set_height(i)
    
for i in range(n):
    out_str = 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, '.format(i,parent[i],get_sib(i), get_deg(i), get_depth(i), get_height(i))
    if parent[i] == -1:
        out_str += 'root'
    elif right[i] == -1 and left[i] == -1:
        out_str += 'leaf'
    else:
        out_str += 'internal node'
    print(out_str)

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


n = int(input())
binary_tree = [Node() for i in range(n)]
h, d = [0 for j in range(n)], [0 for k in range(n)]


def set_height(u):
    h1 = h2 = 0
    if binary_tree[u].right != -1:
        h1 = set_height(binary_tree[u].right) + 1
    if binary_tree[u].left != -1:
        h2 = set_height(binary_tree[u].left) + 1

    h[u] = max(h1, h2)
    return h[u]


def set_depth(u, dep):
    d[u] = dep
    if binary_tree[u].right != -1:
        set_depth(binary_tree[u].right, dep+1)
    if binary_tree[u].left != -1:
        set_depth(binary_tree[u].left, dep+1)

    return d[u]


def set_sibling(u):
    if binary_tree[binary_tree[u].parent].left != u:
        return binary_tree[binary_tree[u].parent].left
    else:
        return binary_tree[binary_tree[u].parent].right


def set_degree(u):
    cnt = 0
    if binary_tree[u].left != -1:
        cnt += 1
    if binary_tree[u].right != -1:
        cnt += 1
    return cnt


def set_type(u):
    if binary_tree[u].parent == -1:
        return "root"
    elif binary_tree[u].left == -1 and binary_tree[u].right == -1:
        return "leaf"
    else:
        return "internal node"


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

    
    root_idx = 0
    for i in range(n):
        if binary_tree[i].parent == -1:
            root_idx = i
            break

    
    set_height(root_idx)

    
    set_depth(root_idx, 0)

    for i in range(n):
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, "
              "height = {}, {}".format(i, binary_tree[i].parent,
                set_sibling(i), set_degree(i), d[i], h[i], set_type(i)))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
root = set(range(n))
binary_tree = [0 for i in range(n)]

for i in range(n):
    l = list(map(int, input().split()))
    binary_tree[l[0]] = l
    s = set(l[1:3])
    root -= s

def binary(id, parent, depth, sibling, height):
    output = {}
    hline = []
    hline.append(height)
    output['node'] = id
    output['parent'] = parent
    output['sibling'] = sibling
    output['depth'] = depth
    left = binary_tree[id][1]
    right = binary_tree[id][2]
    degree = 0
    if(parent == -1):
        output['type'] = 'root'
    elif(left == -1 and right == -1):
        output['type'] = 'leaf'
    else:
        output['type'] = 'internal node'
    if(left != -1):
        degree += 1
        hline.append(binary(left, id, depth+1, right, height))
    if(right != -1):
        degree += 1
        hline.append(binary(right, id, depth+1, left, height))
    max_height = max(hline)
    output['degree'] = degree
    output['height'] = max_height
    binary_tree[id] = output
    return max_height + 1

binary(list(root)[0], -1, 0, -1, 0)
for line in binary_tree:
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(line['node'], line['parent'], line['sibling'], line['degree'], line['depth'], line['height'], line['type']))

Solution (Python):
class Tree:
    def __init__(self, ary):
        self.nodes = [
            Node(node, self) for node in sorted(ary, key=lambda x: x[0])
        ]
        [node.set() for node in self.nodes]
        for node in self.nodes:
            if node.parent == -1:
                node.set_depth(0)
                node.set_height()
                break

    def output(self):
        [node.output() for node in self.nodes]


class Node:
    def __init__(self, node, tree):
        self.tree = tree
        self.no = node[0]
        self.left = node[1]
        self.right = node[2]
        self.parent = -1
        self.sibling = -1
        self.degree = 0

    def set(self):
        if self.left > -1:
            self.tree.nodes[self.left].parent = self.no
            if self.right > -1:
                self.tree.nodes[self.right].sibling = self.left
            self.degree += 1

        if self.right > -1:
            self.tree.nodes[self.right].parent = self.no
            if self.left > -1:
                self.tree.nodes[self.left].sibling = self.right
            self.degree += 1

    def set_depth(self, d):
        self.depth = d
        if self.left > -1:
            self.tree.nodes[self.left].set_depth(d + 1)
        if self.right > -1:
            self.tree.nodes[self.right].set_depth(d + 1)

    def set_height(self):
        if self.degree == 0:
            self.height = 0
        else:
            self.tree.nodes[self.right].set_height()
            self.tree.nodes[self.left].set_height()
            self.height = 1 + max(self.tree.nodes[self.right].height,
                                  self.tree.nodes[self.left].height)

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

        print(
            'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.
            format(self.no, self.parent, self.sibling, self.degree, self.depth,
                   self.height, kind))


if __name__ == '__main__':
    
    n = int(input())
    ary = [[int(_) for _ in input().split()] for i in range(n)]
    tree = Tree(ary)
    tree.output()

Solution (Python):
class NullNode():
    def __init__(self):
        self.id = -1

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

    def __str__(self):
        return '{} {} {} {} {}'.format(self.id, self.parent.id, self.left.id, self.right.id, self.sibling.id)

    def getHeight(self, right_height=0, left_height=0):
        if self.left.id != -1:
            left_height += 1
            left_height = self.left.getHeight(left_height, left_height)
        if self.right.id != -1:
            right_height += 1
            right_height = self.right.getHeight(right_height, right_height)
        return max(left_height, right_height)

    def getDepth(self, depth=0):
        if self.parent.id != -1:
            depth += 1
            depth = self.parent.getDepth(depth)
        return depth

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

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

n = int(input())
node_list = [Node(id) for id in range(n)]
for i in range(n):
    [id, left, right] = [int(j) for j in input().split()]
    i_node = node_list[id]
    if left != -1:
        i_node.left = node_list[left]
        node_list[left].parent = node_list[id]
        if right != -1:
            node_list[left].sibling = node_list[right]
    if right != -1:
        i_node.right = node_list[right]
        node_list[right].parent = node_list[id]
        if left != -1:
            node_list[right].sibling = node_list[left]

for id in range(n):
    i_node = node_list[id]
    parent = i_node.parent.id
    sibling = i_node.sibling.id
    degree = i_node.getDegree()
    depth = i_node.getDepth()
    height = i_node.getHeight()
    type = i_node.getType()
    print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}'.format(id, parent, sibling, degree, depth, height, type))

Solution (Python):


n = int(input())
T = [list(map(int, input().split())) for i in range(n)]
A = [False for i in range(n)]

class binaryTree:
    def __init__(self, node, x=-1):
        self.node = node
        self.p = x
    
    def partialTree(self,tree,left, right):
        node = tree.node
        if left != -1:
            if A[left]:
                A[left].p = tree
                tree.l = A[left]
            else:
                tree.l = binaryTree(left, node)
                A[left] = tree.l
                tree.l.p = tree
        else:
            tree.l = binaryTree(left, node)
            tree.l.node = -1
            
        if right != -1:
            if A[right]:
                A[right].p = tree
                tree.r = A[right]
            else:
                tree.r = binaryTree(right, node)
                A[right] = tree.r
                tree.r.p = tree
        else:
            tree.r = binaryTree(right, node)
            tree.r.node = -1
            
def searchParent():
    p_tree = A[0]
    while p_tree.p != -1:
        p_tree = p_tree.p
    return p_tree

     
def setHeight(tree):
    h1 = h2 = 0
    if tree.l.node != -1:
        h1 = setHeight(tree.l) + 1
    if tree.r.node != -1:
        h2 = setHeight(tree.r) + 1
    if tree.l.node == -1 and tree.r.node == -1:
        tree.hei = 0
        return 0
    tree.hei = max(h1,h2)
    return max(h1, h2)

def setDepth(tree,depth):
    tree.dep = depth
    depth += 1
    if tree.l.node != -1:
        setDepth(tree.l,depth)

    if tree.r.node != -1:
        setDepth(tree.r,depth)

def getSibling(tree):
    if tree.p == -1:
        return -1
    if tree.p.l.node != -1 and tree.p.l.node != tree.node:
        return tree.p.l.node
    if tree.p.r.node != -1 and tree.p.r.node != tree.node:
        return tree.p.r.node
    return -1

        
def makeTree():
    for i in range(n):
        t = T[i]
        node = t[0]
        left = t[1]
        right = t[2]
        if A[node]:
            tree = A[node]
        else:
            tree = binaryTree(node)
            A[node] = tree
        binaryTree.partialTree(binaryTree, tree,left,right)

makeTree()
p_tree = searchParent()
setHeight(p_tree)
depth = 0
setDepth(p_tree,depth)


for i in range(n):
    tree = A[i]
    tree.sib = getSibling(tree)
    deg = 0
    if tree.r.node != -1:
        deg += 1

    if tree.l.node != -1:
        deg += 1

    if tree.p == -1:
        kind = "root"
    else:
        if deg == 0:
            kind = "leaf"
        else:
            kind = "internal node"

    ID = i
    if tree.p == -1:
        parent = -1
    else:
        parent = tree.p.node
    sibling = tree.sib
    degree = deg
    depth = tree.dep
    height = tree.hei

    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"\
          .format(ID, parent, sibling, degree, depth, height, kind))

Solution (Python):
def search(ps, id):
    if ps[id] == -1:
        return 0
    else:
        return 1 + search(ps, ps[id])


def search_h(tree, id):
    if tree[id][0] == -1:
        left = -1
    else:
        left = search_h(tree, tree[id][0])

    if tree[id][1] == -1:
        right = -1
    else:
        right = search_h(tree, tree[id][1])

    return 1 + max(left, right)


n = int(input())
tree = [[] for _ in range(n)]
ps = [-1 for _ in range(n)]
ss = [-1 for _ in range(n)]
for _ in range(n):
    s = input().split()
    id = int(s[0])
    left = int(s[1])
    right = int(s[2])
    tree[id] = [left, right]
    if left >= 0:
        ps[left] = id
        ss[left] = right
    if right >= 0:
        ps[right] = id
        ss[right] = left

for id in range(n):
    p = ps[id]
    s = ss[id]
    deg = int(tree[id][0] >= 0) + int(tree[id][1] >= 0)
    d = search(ps, id)
    h = search_h(tree, id)
    if p == -1:
        type = "root"
    elif tree[id][0] == -1 and tree[id][1] == -1:
        type = "leaf"
    else:
        type = "internal node"

    print("node " + str(id) + ": parent = " + str(p) + ", sibling = " + str(s) + ", degree = " + str(
        deg) + ", depth = " + str(d) + ", height = " + str(h) + ", " + type)

Solution (Python):
Parent = 0
Lchild = 1
Rchild = 2

def depth(n):
    if n == -1: return -1
    return depth(parent(n)) + 1

def height(n):
    c1, c2 = childs(n)
    if (c1, c2) == (-1, -1): return 0
    return max(height(c1), height(c2)) + 1

def parent(n):
    return node[n][Parent]

def childs(n):
    return node[n][Lchild:Rchild+1]

def sibling(n):
    c1, c2 = childs(parent(n))
    if c1 == n: return c2
    elif c2 == n: return c1
    return -1

def degree(n):
    return 2 - childs(n).count(-1)

def nt(n):
    if parent(n) == -1:
        return 'root'
    elif degree(n) == 0:
        return 'leaf'
    else:
        return 'internal node'
    return

n = int(input())
node = [[-1, -1, -1] for i in range(n)]
for i in range(n):
    tmp = map(int, raw_input().split())
    j = tmp[0]
    e1, e2 = tmp[1:]
    if e1 != -1:
        node[j][Lchild] = e1
        node[e1][Parent] = j
    if e2 != -1:
        node[j][Rchild] = e2
        node[e2][Parent] = j

for i in range(n):
    msg = 'node {0}: parent = {1}, sibling = {2}, degree = {3}, '+\
          'depth = {4}, height = {5}, {6}'''
    c1 = parent(i)
    c2 = sibling(i)
    c3 = degree(i)
    c4 = depth(i)
    c5 = height(i)
    c6 = nt(i)
    print msg.format(i, c1, c2, c3, c4, c5, c6)

Solution (Python):

from __future__ import division, print_function
from sys import stdin

FORMAT = ('node {0.id}: parent = {0.parent}, sibling = {0.sibling}, '
          'degree = {0.degree}, depth = {0.depth}, height = {0.height}, '
          '{0.type}').format


class Node(object):
    def __init__(self, data):
        self.id = data[0]
        self.parent = -1
        self.sibling = -1
        self.degree = int(data[1] >= 0) + int(data[2] >= 0)
        
        self.childs = data[1:]
        self.depth = 0
        self.height = -1
        self.type = 'internal node' if self.degree else 'leaf'

    def __str__(self):
        return FORMAT(self)


def calc_depth(tree, i):
    h = 0
    for k, j in enumerate(tree[i].childs):
        if j >= 0:
            tree[j].depth += 1
            tree[j].sibling = tree[i].childs[1-k]
            h = max(h, calc_depth(tree, j))
    if tree[i].type == 'leaf':
        tree[i].height = 0
    else:
        tree[i].height = h
    return tree[i].height + 1


n = int(stdin.readline())
tree = [-1] * n

for _ in range(n):
    node = Node([int(s) for s in stdin.readline().split()])
    parent = tree[node.id]
    tree[node.id] = node
    if isinstance(parent, int):
        tree[node.id].parent = parent
    else:
        tree[node.id].parent = parent.id
    for i in node.childs:
        if i >= 0:
            if isinstance(tree[i], int):
                tree[i] = node.id
            else:
                tree[i].parent = node.id

for i in range(n):
    calc_depth(tree, i)

for node in tree:
    if node.parent == -1:
        node.type = 'root'
    print(node)

Solution (Python):
def getDepth(x):
    global nodes
    p = nodes[x][0]
    c = 0
    while p != -1:
        c += 1
        p = nodes[p][0]

    return c


def getHeight(x):
    global nodes
    h1, h2 = 0, 0
    if nodes[x][1] != -1:
        h1 = getHeight(nodes[x][1])+1
    if nodes[x][2] != -1:
        h2 = getHeight(nodes[x][2])+1

    return max(h1, h2)


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

for i in range(n):
    nodes.append([-1])


for i in range(n):
    a = list(map(int, input().split()))
    if a[1] != -1:
        nodes[a[1]][0] = a[0]
    if a[2] != -1:
        nodes[a[2]][0] = a[0]
    
    nodes[a[0]] += a[1:]

for i in range(n):
    par = nodes[i][0]
    sib = nodes[par][1]

    if nodes[par][1] == i:
        sib = nodes[par][2]

    if par == -1:
        sib = -1

    deg = 0
    if nodes[i][1] != -1:
        deg +=1
    if nodes[i][2] != -1:
        deg +=1

    dep = getDepth(i)
    hei = getHeight(i)

    typ = ' internal node'
    if hei == 0:
        typ = ' leaf'
    if par == -1:
        typ = ' root'

    print('node ' + str(i) + ': parent = ', end= '')
    print(str(par) + ', sibling = ', end= '')
    print(str(sib) + ', degree = ', end= '')
    print(str(deg) + ', depth = ', end= '')
    print(str(dep) + ', height = ', end = '')
    print(str(hei) + ',' + typ)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2**20)

class Node:
    def __init__(self):
        self.id = None
        self.p = None
        self.left = None
        self.right = None
        self.deg = None
        self.att = None
        self.depth = None
        self.height = None
        self.sibling = None

def SetDepth(u, p):
    T[u].depth = p
    pr, pl = 0, 0
    if T[u].right != -1:
        pr = SetDepth(T[u].right, p+1)
    if T[u].left != -1:
        pl = SetDepth(T[u].left, p+1)
    p = max(p, pr, pl)
    T[u].height = p - T[u].depth
    return p

n = int(input())
T = [None] * n
for i in range(n):
    temp = Node()
    T[i] = temp

for i in range(n):
    d = 0
    L = [int(x) for x in input().split()]
    v, l, r = L[0], L[1], L[2]
    T[v].id = v
    T[v].left = l
    T[v].right = r
    if l != -1:
        T[l].p = v
        d += 1
    if r != -1:
        T[r].p = v
        d += 1
    T[v].deg = d 

for i, t in enumerate(T):
    if t.p == None:
        t.att = 'root'
        t.p = -1
        maxd = SetDepth(i, 0)
    elif t.deg == 0:
        t.att = 'leaf'
    else:
        t.att = 'internal node'
    if t.p == -1:
        t.sibling = -1
    else:
        if T[t.p].left == t.id:
            if T[t.p].right == None:
                t.sibling = -1
            else:
                t.sibling = T[t.p].right
        else:
            if T[t.p].left == None:
                t.sibling = -1
            else:
                t.sibling = T[t.p].left

for i in range(n):
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(T[i].id, T[i].p, T[i].sibling, T[i].deg, T[i].depth, T[i].height, T[i].att))