Problem:

Binary Tree

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

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

node ID of u

parent of u

sibling of u

the number of children of u

depth of u

height of u

node type (root, internal node or leaf)

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

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

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

Input

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

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

id left right

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

Output

Print the information of each node in the following format:

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

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

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

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

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

Please follow the format presented in a sample output below.

Constraints

1 ≤ n ≤ 25

Sample Input 1

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

Sample Output 1

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

Reference

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



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


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

Submission status: Accepted

Solution code:
NIL = -1

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


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


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


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


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

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


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

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

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

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

Submission status: Accepted

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

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

n = int(input())
rbt = [Node(i) for i in range(n)]
for i in range(n):
    id,left,right = map(int, input().split())
    tgt = rbt[id]
    l,r = None,None
    if not left == -1:
        l = rbt[left]
        l.depth += tgt.depth + 1
        l.parent = tgt
        calc_cld_depth(l)
        tgt.degree.append(l)
    if not right == -1:
        r = rbt[right]
        r.depth += tgt.depth + 1
        r.parent = tgt
        calc_cld_depth(r)
        tgt.degree.append(r)
    if (not left == -1) and (not right == -1):
        l.sibling, r.sibling = r,l
    if left == -1 and right == -1:
        if tgt.parent: tgt.depth = tgt.parent.depth + 1
# calc height
for c in rbt:
    h = 0
    if c.is_leaf():
        c.height = h
        p = c.parent
        while p:
            h += 1
            if p.height < h: p.height = h
            p = p.parent
for t in rbt: print(t)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>

using namespace std;

#define MAX 30
#define NIL -1

struct Node{
    int parent,left,right;
};

Node T[MAX];
int n, D[MAX], H[MAX];

void setDepth(int u, int d) {
    if( u == NIL){
        return;
    }
    D[u] = d;
    setDepth(T[u].left, d+1);
    setDepth(T[u].right, d+1);
}

int setHeight(int u){
    int h1 = 0, h2=0;
    if(T[u].left != NIL){
        h1 = setHeight(T[u].left) + 1;
    }
    if(T[u].right != NIL){
        h2 = setHeight(T[u].right) + 1;
    }
    return H[u] = h1 > h2 ? h1:h2;
}

int getSibling(int u){
    if(T[u].parent == NIL){
        return NIL;
    }
    if(T[T[u].parent].left != u and T[T[u].parent].left != NIL){
        return T[T[u].parent].left;
    }
    if(T[T[u].parent].right != u and T[T[u].parent].right != NIL){
        return T[T[u].parent].right;
    }
    return NIL;
}

void print(int u){
    cout << "node " << u << ": ";
    cout << "parent = " << T[u].parent << ", ";
    cout << "sibling = " << getSibling(u) << ", ";
    int deg = 0;
    if(T[u].left != NIL){
        deg++;
    }
    if(T[u].right != NIL){
        deg ++;
    }
    cout << "degree = " << deg << ", ";
    cout << "depth = " << D[u] << ", ";
    cout << "height = " << H[u] << ", ";
    if(T[u].parent == NIL){
        cout << "root" << endl;
    }else if (T[u].left != NIL or T[u].right != NIL){
        cout << "internal node" << endl;
    }else{
        cout << "leaf" << endl;
    }
}

int main() {
   
    int v,l,r, root = 0;
    cin >> n;
    for (int i=0;i<n;i++){
        T[i].parent = NIL;
    }
    for (int i=0;i<n;i++){
        cin >> v >> l >> r;
        T[v].left = l;
        T[v].right = r;
        if(l!= NIL){
            T[l].parent = v;
        }
        if(r != NIL){
            T[r].parent = v;
        }
    }

    for(int i=0;i<n;i++){
        if(T[i].parent == NIL){
            root = i;
        }
    }

    setDepth(root,0);
    setHeight(root);

    for (int i=0;i<n;i++){
        print(i);
    }

}

Submission status: Runtime Error

Solution code:
n = int(input())


class BiTree():
    def __init__(self, node, left, right):
        self.node = node
        self.left = left
        self.right = right


dali = [0] * n


def inputdata(i):
    node, left, right = list(map(int, input().split()))
    dali[i] = BiTree(node, left, right)


def getParent(i):
    for k in range(n):
        if(dali[k].right == dali[i].node) or (dali[k].left == dali[i].node):
            dali[i].parent = dali[k].node
    
            return dali[i].parent
    dali[i].parent = -1
    
    return dali[i].parent


def getDepth(i):
    h = 0
    tmp = dali[i].parent
    while True:
        if tmp == -1:
            dali[i].depth = h
            break
        else:
            tmp = getParent(tmp)
            h += 1


def getHeight(i):  # i == daliの要素番号
    
    h1 = 0
    h2 = 0
    if dali[i].right != -1:
        h1 = getHeight(dali[i].right) + 1

    if dali[i].left != -1:
        h2 = getHeight(dali[i].left) + 1

    return max(h1, h2)


def getDegree(i):
    if dali[i].right == -1:
        dali[i].deg = 0
    else:
        dali[i].deg = 2


def getType(i):
    if dali[i].parent == -1:
        dali[i].type = "root"
    elif dali[i].deg == 0:
        dali[i].type = "leaf"
    else:
        dali[i].type = "internal node"

def getSibling(i):
    if dali[i].type == "root":
        dali[i].sibling = -1
        return 0
    sib = []
    sib.append((dali[dali[i].parent].right))
    sib.append(dali[dali[i].parent].left)
    if sib[0] == dali[i].node:
        dali[i].sibling = sib[1]
    else:
        dali[i].sibling = sib[0]


for j in range(n):
    inputdata(j)

for j in range(n):
    getParent(j)

for j in range(n):
    getDepth(j)

h1 = 0
h2 = 0
for j in range(n):
    dali[j].height = getHeight(j)
    print(h1,h2,j)
    h1 = 0
    h2 = 0

for j in range(n):
    getDegree(j)
for j in range(n):
    getType(j)
for j in range(n):
    getSibling(j)
for j in range(n):
    print("node %d: parent = %d,sibling = %d, degree = %d, depth = %d, height = %d, %s" % (
        dali[j].node, dali[j].parent,dali[j].sibling, dali[j].deg, dali[j].depth, dali[j].height, dali[j].type))

Submission status: Runtime Error

Solution code:
n = int(input())
class BiTree():
    def __init__(self, node, left, right):
        self.node = node
        self.left = left
        self.right = right
dali = [0] * n
def inputdata(i):
    node, left, right = list(map(int, input().split()))
    dali[node] = BiTree(node, left, right)
def getParent(i):
    for k in range(n):
        if(dali[k].right == dali[i].node) or (dali[k].left == dali[i].node):
            dali[i].parent = dali[k].node
            return dali[i].parent
    dali[i].parent = -1

    return dali[i].parent
def getDepth(i):
    h = 0
    tmp = dali[i].parent
    while True:
        if tmp == -1:
            dali[i].depth = h
            break
        else:
            tmp = getParent(tmp)
            h += 1


def getHeight(i):  # i == daliの要素番号
    h1 = 0
    h2 = 0
    if dali[i].right != -1:
        h1 = getHeight(dali[i].right) + 1
    if dali[i].left != -1:
        h2 = getHeight(dali[i].left) + 1 
    return max(h1, h2)
def getDegree(i):
    if dali[i].right == -1 and dali[i].left == -1:
        dali[i].deg = 0
    elif. (dali[i].right) * dali[i].left == -1:
        dali[i].deg = 1
    else:
        dali[i].deg = 2


def getType(i):
    if dali[i].parent == -1:
        dali[i].type = "root"
    elif dali[i].deg == 0:
        dali[i].type = "leaf"
    else:
        dali[i].type = "internal node"
def getSibling(i):
    if dali[i].type == "root":
        dali[i].sibling = -1
        return 0
    sib = []
    sib.append((dali[dali[i].parent].right))
    sib.append(dali[dali[i].parent].left)
    if sib[0] == dali[i].node:
        dali[i].sibling = sib[1]
    else:
        dali[i].sibling = sib[0]
for j in range(n):
    inputdata(j)
for j in range(n):
    getParent(dali[j].node)
for j in range(n):
    getDepth(dali[j].node)
h1 = 0
h2 = 0
for j in range(n):
    dali[j].height = getHeight(dali[j].node)
    h1 = 0
    h2 = 0
for j in range(n):
    getDegree(dali[j].node)
for j in range(n):
    getType(dali[j].node)
for j in range(n):
    getSibling(dali[j].node)
for j in range((dali[j].node)+1):
    print("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s" % (dali[j].node, dali[j].parent, dali[j].sibling, dali[j].deg, dali[j].depth, dali[j].height, dali[j].type))

Submission status: Runtime Error

Solution code:
n = int(input())
deg = [0]*n
child, parent = {}, {}
sib = [None]*n
for i in range(n):
    a = list(map(int, input().split()))
    if a[1] != -1:
        child[a[0]] = a[1:]
        sib[a[1]] = a[2]
        sib[a[2]] = a[1]
        deg[a[0]] = 2
        for j in child[a[0]]:
            parent[j] = a[0]
    else:
        child[a[0]] = []

root = (set(child)-set(parent)).pop()
depth = [None]*n
depth[root] = 0
hei = [None]*n
parent[root] = -1
sib[root] = -1

def dfs(s):
    if len(child[s]) == 0:
        hei[s] = 0
        return
    for i in child[s]:
        depth[i] = depth[s] + 1
        dfs(i)
    hei[s] = max(hei[i] for i in child[s]) + 1
    
    
dfs(root)

for i in range(n):
    node_type = 'root' if parent[i] == -1 else 'leaf' if len(child[i]) == 0 else 'internal node'
    print(f'node {i}: parent = {parent[i]}, sibling = {sib[i]}, degree = {deg[i]}, depth = {depth[i]}, height = {hei[i]}, {node_type}')

Submission status: Runtime Error

Solution code:
n = int(input())
deg = [0]*n
child, parent = {}, {}
sib = [None]*n
for i in range(n):
    a = list(map(int, input().split()))
    if a[1] != -1:
        if a[2] == -1:
            child[a[0]] = [a[1]]
            sib[a[1]] = a[2]
            deg[a[0]] = 1
        else:
            child[a[0]] = a[1:]
            sib[a[1]] = a[2]
            sib[a[2]] = a[1]
            deg[a[0]] = 2
        for j in child[a[0]]:
            parent[j] = a[0]
    else:
        child[a[0]] = []

root = (set(child)-set(parent)).pop()
depth = [None]*n
depth[root] = 0
hei = [None]*n
parent[root] = -1
sib[root] = -1

def dfs(s):
    if len(child[s]) == 0:
        hei[s] = 0
        return
    for i in child[s]:
        depth[i] = depth[s] + 1
        dfs(i)
    hei[s] = max(hei[i] for i in child[s]) + 1
    
    
dfs(root)

for i in range(n):
    node_type = 'root' if parent[i] == -1 else 'leaf' if len(child[i]) == 0 else 'internal node'
    print(f'node {i}: parent = {parent[i]}, sibling = {sib[i]}, degree = {deg[i]}, depth = {depth[i]}, height = {hei[i]}, {node_type}')

Submission status: Runtime Error

Solution code:
#include <iostream>
#define TREE_SIZE 30
#define NIL -1
using namespace std;

struct Node 
{
    int parent_node = NIL;
    int left_child = NIL;
    int right_child = NIL;
};

Node Tree[TREE_SIZE];
int Depth[TREE_SIZE];
int Height[TREE_SIZE];

// set depth of all nodes by recursion
void Set_depth_of_node(int node_id, int depth)
{
    Depth[node_id] = depth;
    // if there is a child
    if (Tree[node_id].left_child != NIL) Set_depth_of_node(Tree[node_id].left_child, depth+1);
    if (Tree[node_id].right_child != NIL) Set_depth_of_node(Tree[node_id].right_child, depth+1);
}

// set height of all nodes by recursion
int Set_height_of_node(int node_id) 
{
    int l_height = 0, r_height = 0;
    // if there is a child
    if (Tree[node_id].left_child != NIL) l_height = Set_height_of_node(Tree[node_id].left_child) + 1;
    if (Tree[node_id].right_child != NIL) r_height = Set_height_of_node(Tree[node_id].right_child) + 1;

    return Height[node_id] = (l_height < r_height ? r_height : l_height);
}

int main() 
{
    int node_num, node_id, l_child, r_child;
    scanf("%d", &node_num);
    for (int i = 0; i < node_num; ++i) 
    {
        scanf("%d %d %d", &node_id, &l_child, &r_child);
        Tree[node_id].left_child = l_child;  // set left child
        Tree[node_id].right_child = r_child; // set right child 
        
        // set parent if the node has children
        if (l_child != -1) Tree[l_child].parent_node = node_id;
        if (r_child != -1) Tree[r_child].parent_node = node_id;
    }

    // search root of Tree
    int root = 0;
    while (Tree[root].parent_node != NIL) 
    {
        root++;
    }

    // set depth of all nodes
    Set_depth_of_node(root, 0);

    // set height of all nodes
    Set_height_of_node(root);

    // print out below
    for (int i = 0; i < node_num; ++i) 
    {
        printf("node %d: parent = %d, ", i, Tree[i].parent_node);

        // print out siblings
        if (Tree[i].parent_node == NIL) printf("sibling = -1, "); // if this is root
        else 
        {
            if (i == Tree[Tree[i].parent_node].left_child) // if this is left child, print right child
            {
                printf("sibling = %d, ", Tree[Tree[i].parent_node].right_child);
            }
            else // if this is right child, print left child
            {
                printf("sibling = %d, ", Tree[Tree[i].parent_node].left_child);
            }
        }

        // print out degree (number of children)
        int degree = 0;
        if (Tree[i].left_child != NIL) degree++;
        if (Tree[i].right_child != NIL) degree++;
        printf("degree = %d, ", degree);

        // print out depth
        printf("depth = %d, ", Depth[i]);

        // print out height
        printf("height = %d, ", Height[i]);

        // print out position
        if (i == root) printf("root\n");
        else if (degree == 0) printf("leaf\n");
        else printf("internal node\n");
    }
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#define TREE_SIZE 30
#define NIL -1

struct Node 
{
    int parent_node = NIL;
    int left_child = NIL;
    int right_child = NIL;
};

Node Tree[TREE_SIZE];
int Depth[TREE_SIZE];
int Height[TREE_SIZE];

// set depth of all nodes by recursion
void Set_depth_of_node(int node_id, int depth)
{
    Depth[node_id] = depth;
    // if there is a child
    if (Tree[node_id].left_child != NIL) Set_depth_of_node(Tree[node_id].left_child, depth+1);
    if (Tree[node_id].right_child != NIL) Set_depth_of_node(Tree[node_id].right_child, depth+1);
}

// set height of all nodes by recursion
int Set_height_of_node(int node_id) 
{
    int l_height = 0, r_height = 0;
    // if there is a child
    if (Tree[node_id].left_child != NIL) l_height = Set_height_of_node(Tree[node_id].left_child) + 1;
    if (Tree[node_id].right_child != NIL) r_height = Set_height_of_node(Tree[node_id].right_child) + 1;

    return Height[node_id] = (l_height < r_height ? r_height : l_height);
}

int main() 
{
    int node_num, node_id, l_child, r_child;
    scanf("%d", &node_num);
    for (int i = 0; i < node_num; ++i) 
    {
        scanf("%d %d %d", &node_id, &l_child, &r_child);
        Tree[node_id].left_child = l_child;  // set left child
        Tree[node_id].right_child = r_child; // set right child 
        
        // set parent if the node has children
        if (l_child != -1) Tree[l_child].parent_node = node_id;
        if (r_child != -1) Tree[r_child].parent_node = node_id;
    }

    // search root of Tree
    int root = 0;
    while (Tree[root].parent_node != NIL) 
    {
        root++;
    }

    // set depth of all nodes
    Set_depth_of_node(root, 0);

    // set height of all nodes
    Set_height_of_node(root);

    // print out below
    for (int i = 0; i < node_num; ++i) 
    {
        printf("node %d: parent = %d, ", i, Tree[i].parent_node);

        // print out siblings
        if (Tree[i].parent_node == NIL) printf("sibling = -1, "); // if this is root
        else 
        {
            if (i == Tree[Tree[i].parent_node].left_child) // if this is left child, print right child
            {
                printf("sibling = %d, ", Tree[Tree[i].parent_node].right_child);
            }
            else // if this is right child, print left child
            {
                printf("sibling = %d, ", Tree[Tree[i].parent_node].left_child);
            }
        }

        // print out degree (number of children)
        int degree = 0;
        if (Tree[i].left_child != NIL) degree++;
        if (Tree[i].right_child != NIL) degree++;
        printf("degree = %d, ", degree);

        // print out depth
        printf("depth = %d, ", Depth[i]);

        // print out height
        printf("height = %d, ", Height[i]);

        // print out position
        if (i == root) printf("root\n");
        else if (degree == 0) printf("leaf\n");
        else printf("internal node\n");
    }
}

Submission status: Runtime Error

Solution code:
def f(n,d):
    t=[f(i,d+1)+1 for i in l[n][1]]
    h=0 if t==[] else max(t)
    c[n][3:3]=[len(l[n][1]),d,h,"root" if d<1 else "leaf" if h<1 else "internal node"]
    return h
m=input()
c=[0]*m
l=sorted([map(int,raw_input().split()) for _ in range(m)])
for i in l:
    n,a,b=i
    if a>0:c[a]=[a,n,b]
    if b>0:c[b]=[b,n,a]
    i[1:]=[[j for j in i[1:] if j>=0]]
n=c.index(0)
c[n]=[n,-1,-1]
f(n,0)
for i in c:print "node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}".format(*i)

Submission status: Runtime Error

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: Runtime Error

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):
    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:
                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: Runtime Error

Solution code:
def print_node(i, node):
    parent = -1 if node[1] == None else node[1]
    degree = len([x for x in node[0] if x != -1])
    sibling = -1 if parent == -1 else node[2]
    depth = node[3]
    height = node[4]
    t = 'root' if parent == -1 else 'leaf' if height == 0 else 'internal node'
    ans = "node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(i, parent, sibling, degree, depth, height, t)
    print(ans)

n = int(input())

root = set([x for x in range(n)])
T = [None] * n
for x in range(n):
    i, l, r = list(map(int, input().split()))

    # children, parent, sibling, depth, height
    T[i] = [[l, r], None, None, None, None]
    root -= set([l, r])

def set_info(i, depth):
    node = T[i]
    node[3] = depth
    l = None
    r = None
    if node[0][0] != -1:
        l = T[node[0][0]]
        l[1] = i
        set_info(node[0][0], depth + 1)
    if node[0][1] != -1:
        r = T[node[0][1]]
        r[1] = i
        set_info(node[0][1], depth + 1)
    if l != None and r != None:
        l[2] = node[0][1]
        r[2] = node[0][0]
    node[4] = height(i)

def height(i):
    node = T[i]
    l = node[0][0]
    r = node[0][1]
    lh = None
    rh = None
    h = None
    if l != -1:
        lh = height(l)
    if r != -1:
        rh = height(r)
    if lh != None or rh != None:
        h = max(lh, rh)
    if h == None:
        return 0
    else:
        return 1 + h


r = root.pop()
T[r][1] = -1
set_info(r, 0)

for i, n in enumerate(T):
    print_node(i, n)

Submission status: Runtime Error

Solution code:
NIL = -1
class Node:
    parent,left,right = NIL,NIL,NIL
    type = NIL
    depth = NIL
    sibling = NIL
    degree = NIL
def setHeight(H,u):
    h1 = h2 = 0
    if T[u].right != NIL:
        h1 = setHeight(H,T[u].right) + 1
    if T[u].left != NIL:
        h2 = setHeight(H,T[u].left) + 1

    return max(h1,h2)

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

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

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

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

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

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

Submission status: Runtime Error

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


def setHeight(u):
    global T, H
    hr = hl = 0
    if T[u].right != -1:
        hr = setHeight(T[u].right) + 1
    if T[u].left != -1:
        hl = setHeight(T[u].left) + 1
    H[u] = max(hr, hl)
    return H[u]


def setDepth(u, d):
    global T, D
    D[u] = d
    if T[u].right != -1: setDepth(T[u].right, d + 1)
    if T[u].left != -1: setDepth(T[u].left, d + 1)


def getSibling(u):
    global T
    if T[u].parent == -1: return False

    if T[T[u].parent].right != u and T[T[u].parent].right != -1:
        return T[T[u].parent].right
    if T[T[u].parent].left != u and T[T[u].parent].left != -1:
        return T[T[u].parent].left

    return -1


def deg(u):
    global T
    dg = 0
    if T[u].right != -1: dg += 1
    if T[u].left != -1: dg += 1
    return dg


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


if __name__ == "__main__":
    n = int(input())
    T = []
    D = [-1] * n
    H = [-1] * n
    for i in range(n):
        tmp = list(map(int, input().split()))
        T.append(Node(tmp[0], tmp[1], tmp[2]))

    # parent?????£??\
    for i in range(n):
        if T[i].right != -1:
            T[T[i].right].parent = i
        if T[i].left != -1:
            T[T[i].left].parent = i

    setHeight(0)
    setDepth(0, 0)

    for i in range(n):
        print("node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}" \
              .format(T[i].id, T[i].parent, getSibling(i), deg(i), D[i], H[i], label(i)))