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: Wrong Answer

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

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

def set_sibling(u,S):
    if tree[u].parent != -1:
        v = tree[tree[u].parent].left
        if v == u:
            v = tree[tree[u].parent].right
        S[u] = v
    else:
        S[u] = -1
    if tree[u].left != -1:
        set_sibling(tree[u].left, S)
    if tree[u].right != -1:
        set_sibling(tree[u].right, S)

def set_degree(u,D):
    d = 0
    if tree[u].left != -1:
        d += 1
    if tree[u].right != -1:
        d += 1
    D[u] = d
    if tree[u].left != -1:
        set_degree(tree[u].left, D)
    if tree[u].right != -1:
        set_degree(tree[u].right, D)

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



n = int(raw_input().strip())
tree = {}
for i in range(n):
    nid, left, right = map(int, raw_input().strip().split(' '))
    if not nid in tree: tree[nid] = Node(-1,left,right)
    else:
        tree[nid].left = left
        tree[nid].right = right
    if not left == -1:
        if not left in tree: tree[left] = Node(nid,-1,-1)
        else: tree[left].parent = nid
    if not right == -1:
        if not right in tree: tree[right] = Node(nid,-1,-1)
        else: tree[right].parent = nid

r = -1
for i in range(len(tree)):
    if tree[i].parent == -1:
        r = i
        break

H = {}
set_height(r,H)
S = {}
set_sibling(r,S)
D = {}
set_degree(r,D)
P = {}
set_depth(r,P,0)

for i in range(len(tree)):
    t = "root"
    if tree[i].left == -1:
        t = "leaf"
    elif tree[i].parent != -1:
        t = "internal node"
    print "node %s: parent = %s, sibling = %s, degree = %s, depth = %s, height = %s, %s" % (i, tree[i].parent, S[i], D[i], P[i], H[i], t)

Submission status: Wrong Answer

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

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

def set_sibling(u,S):
    if tree[u].parent != -1:
        v = tree[tree[u].parent].left
        if v == u:
            v = tree[tree[u].parent].right
        S[u] = v
    else:
        S[u] = -1
    if tree[u].left != -1:
        set_sibling(tree[u].left, S)
    if tree[u].right != -1:
        set_sibling(tree[u].right, S)

def set_degree(u,D):
    d = 0
    if tree[u].left != -1:
        d += 1
    if tree[u].right != -1:
        d += 1
    D[u] = d
    if tree[u].left != -1:
        set_degree(tree[u].left, D)
    if tree[u].right != -1:
        set_degree(tree[u].right, D)

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



n = int(raw_input().strip())
tree = {}
for i in range(n):
    nid, left, right = map(int, raw_input().strip().split(' '))
    if not nid in tree: tree[nid] = Node(-1,left,right)
    else:
        tree[nid].left = left
        tree[nid].right = right
    if not left == -1:
        if not left in tree: tree[left] = Node(nid,-1,-1)
        else: tree[left].parent = nid
    if not right == -1:
        if not right in tree: tree[right] = Node(nid,-1,-1)
        else: tree[right].parent = nid

r = -1
for i in range(len(tree)):
    if tree[i].parent == -1:
        r = i
        break

H = {}
set_height(r,H)
S = {}
set_sibling(r,S)
D = {}
set_degree(r,D)
P = {}
set_depth(r,P,0)

for i in range(len(tree)):
    if tree[i].parent == -1:
        t = "root"
    elif tree[i].left == -1:
        t = "leaf"
    else:
        t = "internal node"
    print "node %s: parent = %s, sibling = %s, degree = %s, depth = %s, height = %s, %s" % (i, tree[i].parent, S[i], D[i], P[i], H[i], t)

Submission status: Wrong Answer

Solution code:
n = int(raw_input())



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

class Node:
    def __init__(self):
        self.id = -1
        self.parent = -1
        self.left = -1
        self.right = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = 'leaf' if self.height == 0 else 'internal node'
        
    def setType(self):
        if self.height == 0:
            self.type = 'leaf'
        elif self.parent == -1:
            self.type = 'root'
        else:
            self.type = 'internal node'

    def __str__(self):
        return FORMAT(self)

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

def setDepth(u, d):#(0,0)
    T[u].depth = d
    if T[u].left == -1 and T[u].right == -1:
        return 
    setDepth(T[u].left, d+1)
    setDepth(T[u].right, d+1)



T = [Node() for _ in xrange(n)]

for i in xrange(n):
    a = map(int, raw_input().split())
    u = a[0]
    l = a[1]
    r = a[2]
    T[u].id = u
    T[u].left = l  #set child
    T[u].right = r  #set child
    if l != -1 and r != -1:
        T[l].parent = u  #set parent
        T[r].parent = u  #set parent
    if l != -1 and r != -1:
        T[u].degree = 2
        T[l].sibling = r
        T[r].sibling = l

setHeight(T, 0)
setDepth(0, 0)


for i in xrange(n):
    T[i].setType()
    print T[i]

Submission status: Wrong Answer

Solution code:
n = int(raw_input())



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

class Node:
    def __init__(self):
        self.id = -1
        self.parent = -1
        self.left = -1
        self.right = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = 'leaf' if self.height == 0 else 'internal node'
        
    def setType(self):
        if self.height == 0:
            self.type = 'leaf'
        elif self.parent == -1:
            self.type = 'root'
        else:
            self.type = 'internal node'

    def __str__(self):
        return FORMAT(self)

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

def setDepth(u, d):#(0,0)
    T[u].depth = d
    if T[u].left == -1 and T[u].right == -1:
        return 
    setDepth(T[u].left, d+1)
    setDepth(T[u].right, d+1)



T = [Node() for _ in xrange(n)]
N = 0
for i in xrange(n):
    a = map(int, raw_input().split())
    u = a[0]
    l = a[1]
    r = a[2]
    if i == 0:
        N = u
    T[u].id = u
    T[u].left = l  #set child
    T[u].right = r  #set child
    if l != -1 and r != -1:
        T[l].parent = u  #set parent
        T[r].parent = u  #set parent
    if l != -1 and r != -1:
        T[u].degree = 2
        T[l].sibling = r
        T[r].sibling = l

setHeight(T, N)
setDepth(N, 0)


for i in xrange(n):
    T[i].setType()
    print T[i]

Submission status: Wrong Answer

Solution code:
n = int(raw_input())



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

class Node:
    def __init__(self):
        self.id = -1
        self.parent = -1
        self.left = -1
        self.right = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = 'leaf' if self.height == 0 else 'internal node'
        
    def setType(self):
        if self.height == 0 and self.parent != -1:
            self.type = 'leaf'
        elif self.parent == -1:
            self.type = 'root'
        else:
            self.type = 'internal node'

    def __str__(self):
        return FORMAT(self)

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

def setDepth(u, d):#(0,0)
    T[u].depth = d
    if T[u].left == -1 and T[u].right == -1:
        return 
    setDepth(T[u].left, d+1)
    setDepth(T[u].right, d+1)



T = [Node() for _ in xrange(n)]
N = 0
for i in xrange(n):
    a = map(int, raw_input().split())
    u = a[0]
    l = a[1]
    r = a[2]
    if i == 0:
        N = u
    T[u].id = u
    T[u].left = l  #set child
    T[u].right = r  #set child
    if l != -1 and r != -1:
        T[l].parent = u  #set parent
        T[r].parent = u  #set parent
    if l != -1 and r != -1:
        T[u].degree = 2
        T[l].sibling = r
        T[r].sibling = l

setHeight(T, N)
setDepth(N, 0)


for i in xrange(n):
    T[i].setType()
    print T[i]

Submission status: Wrong Answer

Solution code:
n = int(raw_input())



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

class Node:
    def __init__(self):
        self.id = -1
        self.parent = -1
        self.left = -1
        self.right = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = 'leaf' if self.height == 0 else 'internal node'
        
    def setType(self):
        if self.height == 0 and self.parent != -1:
            self.type = 'leaf'
        elif self.parent == -1:
            self.type = 'root'
        else:
            self.type = 'internal node'

    def __str__(self):
        return FORMAT(self)

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

def setDepth(u, d):#(0,0)
    T[u].depth = d
    if T[u].left == -1 and T[u].right == -1:
        return
    if T[u].left != -1 and T[u].right == -1:
        setDepth(T[u].left, d+1)
    elif T[u].left == -1 and T[u].right != -1:
        setDepth(T[u].right, d+1)
    else:
        setDepth(T[u].left, d+1)
        setDepth(T[u].right, d+1)

T = [Node() for _ in xrange(n)]
N = 0
for i in xrange(n):
    a = map(int, raw_input().split())
    u = a[0]
    l = a[1]
    r = a[2]
    if i == 0:
        N = u
    T[u].id = u
    T[u].left = l  #set child
    T[u].right = r  #set child
    if l != -1 and r != -1:
        T[l].parent = u  #set parent
        T[r].parent = u  #set parent
    elif l != -1 and r == -1:
        T[l].parent = u  #set parent
    elif l == -1 and r != -1:
        T[r].parent = u  #set parent

    if l != -1 and r != -1:
        T[u].degree = 2
        T[l].sibling = r
        T[r].sibling = l
    elif l != -1 and r == -1:
        T[u].degree = 1
    elif  l == -1 and r != -1:
        T[u].degree = 1


setHeight(T, N)
setDepth(N, 0)


for i in xrange(n):
    T[i].setType()
    print T[i]

Submission status: Wrong Answer

Solution code:
"""Binary Trees."""

class Node:
    def __init__(self, num, leftChild, rightChild):
        self.id = num
        self.parent = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = 'leaf'
        self.leftChild = leftChild
        self.rightChild = rightChild
        
    def show_info(self):
        print('node {}:'.format(self.id), 'parent = {}'.format(self.parent),
              'sibling = {}'.format(self.sibling),
              'degree = {}'.format(self.degree),
              'depth = {}'.format(self.depth),
              'height = {}'.format(self.height),
              '{}'.format(self.type))


def set_node(i_s):
    i_l = list(map(int, i_s.split()))
    num = i_l[0]
    children = i_l[1:]
    node = Node(num, children[0], children[1])
    T[num] = node
    T[-1] -= num


def set_attributes(n_i, parent, sibling, depth):
    node = T[n_i]
    node.parent = parent
    node.sibling = sibling
    node.depth = depth
    if node.leftChild != -1:
        node.degree += 1
        node.type = 'internal node'
        set_attributes(node.leftChild, node.id, node.rightChild, depth + 1)
    if node.rightChild != -1:
        node.degree += 1
        node.type = 'internal node'
        set_attributes(node.rightChild, node.id, node.leftChild, depth + 1)
    if node.leftChild != -1 and node.rightChild != -1:
        node.height = max(T[node.leftChild].height,
                          T[node.rightChild].height) + 1
    elif node.leftChild != -1:
        node.height = T[node.leftChild].height + 1
    elif node.rightChild != -1:
        node.height = T[node.rightChild].height + 1



import sys

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

T = [None] * n

T.append(int(n * (n - 1) / 2))

for x in sys.stdin.readlines():
    set_node(x)

set_attributes(T[-1], -1, -1, 0)

T[T[-1]].type = 'root'

for n in T[:-1]:
    n.show_info()

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self, num, leftChild, rightChild):
        self.id = num
        self.parent = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = 'leaf'
        self.leftChild = leftChild
        self.rightChild = rightChild
        
    def show_info(self):
        print('node {}:'.format(self.id), 'parent = {}'.format(self.parent),
              'sibling = {}'.format(self.sibling),
              'degree = {}'.format(self.degree),
              'depth = {}'.format(self.depth),
              'height = {}'.format(self.height),
              '{}'.format(self.type))


def set_node(i_s):
    num, leftChild, rightChild = list(map(int, i_s.split()))
    node = Node(num, leftChild, rightChild)
    T[num] = node
    T[-1] -= (max(0, leftChild) + max(0, rightChild))


def set_attributes(n_i, parent, sibling, depth):
    node = T[n_i]
    node.parent = parent
    node.sibling = sibling
    node.depth = depth
    if node.leftChild != -1:
        node.degree += 1
        node.type = 'internal node'
        set_attributes(node.leftChild, node.id, node.rightChild, depth + 1)
    if node.rightChild != -1:
        node.degree += 1
        node.type = 'internal node'
        set_attributes(node.rightChild, node.id, node.leftChild, depth + 1)
    if node.leftChild != -1 and node.rightChild != -1:
        node.height = max(T[node.leftChild].height,
                          T[node.rightChild].height) + 1
    elif node.leftChild != -1:
        node.height = T[node.leftChild].height + 1
    elif node.rightChild != -1:
        node.height = T[node.rightChild].height + 1



import sys

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

T = [None] * n

T.append(int(n * (n - 1) / 2))

for x in sys.stdin.readlines():
    set_node(x)

set_attributes(T[-1], -1, -1, 0)

T[T[-1]].type = 'root'

for n in T[:-1]:
    n.show_info()

Submission status: Wrong Answer

Solution code:
class BinTree():
    def __init__(self):
        self.parent = -1
        self.left, self.right = -1, -1
        self.sib = -1
        self.dep, self.deg, self.h = 0, 0, 0
        self.state = "internal node"

    def set_node(self, nid, l, r):
        global root
        root -= {l, r}
        self.left, self.right = l, r
        self.deg = (l != -1) + (r != -1)
        if l != -1:
            left = trees[l]
            left.parent = nid
            left.sib = r
        if r != -1:
            right = trees[r]
            right.parent = nid
            right.sib = l

    def set_param(self):
        if self.parent != -1:
            self.dep = trees[self.parent].dep + 1
        else:
            self.state = "root"
        if self.deg == 0:
            self.state = "leaf"
        if self.left != -1:
            left = trees[self.left]
            left.set_param()
            self.h = left.h + 1
        if self.right != -1:
            right = trees[self.right]
            right.set_param()
            if self.h <= right.h:
                self.h = right.h + 1

    def echo(self, nid):
        print('node {}: parent = {}'.format(nid, self.parent),
              'sibling = {}'.format(self.sib),
              'degree = {}'.format(self.deg),
              'depth = {}'.format(self.dep),
              'height = {}'.format(self.h),
              self.state, sep=', ')

n = int(input())
trees = [BinTree() for _ in range(n)]
root = set(range(n))
for _ in range(n):
    inp = list(map(int, input().split()))
    trees[inp[0]].set_node(*inp)
root = root.pop()
trees[root].set_param()
for i, tree in enumerate(trees):
    tree.echo(i)

Submission status: Wrong Answer

Solution code:
import sys

class Node:
    def __init__(self, id, children):
        self.id = id
        self.parent = -1
        self.depth = 0
        self.type = "root"
        self.children = children

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    N = lines[0]

    tree = []
    for i in range(int(N)):
        tree.append(Node(i, map(int, lines[i + 1][4:].split())))

    for node in tree:
        if not node.children:
            node.type = "leaf"

        for child in node.children:
            tree[child].parent = node.id
            tree[child].depth = node.depth + 1
            if tree[child].type != "leaf":
                tree[child].type = "internal node"

    for node in tree:
        print "node {0.id}: parent = {0.parent}, depth = {0.depth}, {0.type}, {0.children}".format(node)

Submission status: Wrong Answer

Solution code:
import sys

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

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

def buildTree(id, nodeList, depth):
    leftId, rightId = nodeList[id][0], nodeList[id][1]
    if leftId == -1:
        return Node(id, None, None, 0, depth, "leaf")
    node = Node(id, buildTree(leftId, nodeList, depth + 1), buildTree(rightId, nodeList, depth + 1), 2, depth, "internal node")
    node.left.parent = node
    node.left.sibling = node.right.id
    node.right.parent = node
    node.right.sibling = node.left.id
    node.height = max(node.left.height, node.right.height) + 1
    return node

def tree2linear(node, list):
    list[node.id] = node
    if not node.left is None:
        tree2linear(node.left, list)
        tree2linear(node.right, list)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    N = int(lines[0])
    del lines[0]

    nodeList = [[]] * N
    sum = N * (N - 1) / 2
    for line in lines:
        line = map(int, line.split())
        id, children = line[0], line[1:]
        nodeList[id] = children
        for child in children:
            if child == -1:
                break
            sum -= child
    root = buildTree(sum, nodeList, 0)
    root.type = "root"
    root.parent = Node(-1, None, None, 0, 0, "")

    nodeList = [0] * N
    tree2linear(root, nodeList)
    for node in nodeList:
        node.printInfo()

Submission status: Wrong Answer

Solution code:
import sys

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

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

def buildTree(id, nodeList, depth):
    leftId, rightId = nodeList[id][0], nodeList[id][1]
    if leftId == -1 and rightId == -1:
        dummy = Node(-1, None, None, 0, 0, "")
        return Node(id, dummy, dummy, 0, depth, "leaf")
    degree = 0
    if leftId == -1:
        left = Node(-1, None, None, 0, 0, "")
    else:
        left = buildTree(leftId, nodeList, depth + 1)
        degree += 1
    if rightId == -1:
        right = Node(-1, None, None, 0, 0, "")
    else:
        right = buildTree(rightId, nodeList, depth + 1)
        degree += 1
    node = Node(id, left, right, degree, depth, "internal node")

    node.left.parent = node
    node.left.sibling = node.right.id
    node.right.parent = node
    node.right.sibling = node.left.id
    node.height = max(node.left.height, node.right.height) + 1
    return node

def tree2linear(node, list):
    print node.id
    list[node.id] = node
    if node.left.id != -1:
        tree2linear(node.left, list)
    if node.right.id != -1:
        tree2linear(node.right, list)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    N = int(lines[0])
    del lines[0]

    nodeList = [[]] * N
    sum = N * (N - 1) / 2
    for line in lines:
        line = map(int, line.split())
        id, children = line[0], line[1:]
        nodeList[id] = children
        for child in children:
            if child == -1:
                continue
            sum -= child

    root = buildTree(sum, nodeList, 0)
    root.type = "root"
    root.parent = Node(-1, None, None, 0, 0, "")

    nodeList = [0] * N
    tree2linear(root, nodeList)
    for node in nodeList:
        node.printInfo()

Submission status: Wrong Answer

Solution code:
import sys

class Node:
    def __init__(self):
        self.id = id
        self.parent = -1
        self.sibling = -1
        self.type = "leaf"

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

def setTree(id, tree, depth):
    if id == -1:
        return -1

    tree[id].depth = depth
    height = degree = 0
    for i in range(2):
        child = tree[id].children[i]
        if child != -1:
            degree += 1
        tree[child].parent = id
        tree[child].sibling = tree[id].children[~i]
        height = max(setTree(child, tree, depth + 1) + 1, height)
    tree[id].height = height
    tree[id].degree = degree
    if height != 0:
        tree[id].type = "internal node"

    return height

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    N = int(lines[0])
    del lines[0]

    tree = []
    for i in range(N):
        tree.append(Node())

    root = N * (N - 1) / 2
    for line in lines:
        info = map(int, line.split())
        tree[info[0]].children = info[1:]
        tree[info[0]].id = info[0]
        for i in tree[info[0]].children:
            if i != -1:
                root -= i

    root = setTree(root, tree, 0)
    tree[root].type = "root"

    for node in tree:
        node.printInfo()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

class Node(object):
    def __init__(self, N):
        self.parent = [-1 for i in range(N)]
        self.left = [-1 for i in range(N)]
        self.right = [-1 for i in range(N)]
        self.depth = [-1 for i in range(N)]
        self.sibling = [-1 for i in range(N)]
        self.hight = [0 for i in range(N)]
        self.degree = [0 for i in range(N)]
        self.max_depth = None

    def set_depth(self, u):
        d, U = 0, u
        while T.parent[u] is not -1:
            u = T.parent[u]
            d += 1
        self.depth[U] = d

    def set_hight(self, u):
        self.hight[u] = self.max_depth - self.depth[u]
        

N = int(input())

# create node
T = Node(N)

# set data
for j in range(N):
    A = [int(i) for i in input().split()]

    # left????±????
    T.left[A[0]] = A[1]

    # parent???degree????±????
    for u in A[1:]:
        if u is not -1:
            T.parent[u] = A[0]
            T.degree[A[0]] += 1
            
    # right???sibling????±????
    if (A[1] is not -1) and (A[2] is not -1):
        T.right[A[1]] = A[2]
        T.sibling[A[1]], T.sibling[A[2]] = A[2], A[1]

# set depth
for i in range(N):
    T.set_depth(i)

# set max_depth
T.max_depth = max(T.depth)

# set hight
for i in range(N):
    T.set_hight(i)

# ??????
for i in range(N):
    # ?????????????¨?????????????
    if T.parent[i] is -1:
        node = "root"
    elif T.left[i] is -1:
        node = "leaf"
    else:
        node = "internal node"

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

class Node(object):
    def __init__(self, N):
        self.parent = [-1 for i in range(N)]
        self.left = [-1 for i in range(N)]
        self.right = [-1 for i in range(N)]
        self.depth = [-1 for i in range(N)]
        self.sibling = [-1 for i in range(N)]
        self.hight = [0 for i in range(N)]
        self.degree = [0 for i in range(N)]
        self.max_depth = None

    def set_depth(self, u):
        d, U = 0, u
        while T.parent[u] is not -1:
            u = T.parent[u]
            d += 1
        self.depth[U] = d

    def set_hight(self, u):
        h1 = h2 = 0
        if T.left[u] is not -1:
            h1 = self.set_hight(T.left[u]) + 1
        if T.right[u] is not -1:
            h2 = self.set_hight(T.right[u]) + 1
            
        self.hight[u] = max(h1, h2)
        return max(h1, h2)


N = int(input())

# create node
T = Node(N)

# set data
for j in range(N):
    A = [int(i) for i in input().split()]

    # left???right????±????
    T.left[A[0]] = A[1]
    T.right[A[0]] = A[2]
    
    # parent???degree????±????
    for u in A[1:]:
        if u is not -1:
            T.parent[u] = A[0]
            T.degree[A[0]] += 1
            
    # sibling????±????
    if (A[1] is not -1) and (A[2] is not -1):
        T.sibling[A[1]], T.sibling[A[2]] = A[2], A[1]

# set depth
for i in range(N):
    T.set_depth(i)

# set max_depth
T.max_depth = max(T.depth)

# set hight
T.set_hight(0)

# ??????
for i in range(N):
    # ?????????????¨?????????????
    if T.parent[i] is -1:
        node = "root"
    elif T.left[i] is -1:
        node = "leaf"
    else:
        node = "internal node"

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