Problem:

Rooted Trees

A graph G = (V, E) is a data structure where V is a finite set of vertices and E is a binary relation on V represented by a set of edges. Fig. 1 illustrates an example of a graph (or graphs).

Fig. 1

A free tree is a connnected, acyclic, undirected graph. A rooted tree is a free tree in which one of the vertices is distinguished from the others. A vertex of a rooted tree is called "node."

Your task is to write a program which reports the following information for each node u of a given rooted tree T:

node ID of u

parent of u

depth of u

node type (root, internal node or leaf)

a list of chidlren of u

If the last edge on the path from the root r of a tree T to a node x is (p, x), then p is the parent of x, and x is a child of p. The root is the only node in T with no parent.

siblings.

-->

A node with no children is an external node or leaf. A nonleaf node is an internal node

The number of children of a node x in a rooted tree T is called the degree of x.

The length of the path from the root r to a node x is the depth of x in T.

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

Fig. 2 shows an example of rooted trees where ID of each node is indicated by a number in a circle (node). The example corresponds to the first sample input.

Fig. 2

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 u is given in the following format:

id k c1 c2 ... ck

where id is the node ID of u, k is the degree of u, c1 ... ck are node IDs of 1st, ... kth child of u. If the node does not have a child, the k is 0.

Output

Print the information of each node in the following format ordered by IDs:

node id: parent = p, depth = d, type, [c1...ck]

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

d is depth of the node.

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.

c1...ck is the list of children as a ordered tree.

Please follow the format presented in a sample output below.

Constraints

1 ≤ n ≤ 100000

Sample Input 1

13
0 3 1 4 10
1 2 2 3
2 0
3 0
4 3 5 6 7
5 0
6 0
7 2 8 9
8 0
9 0
10 2 11 12
11 0
12 0

Sample Output 1

node 0: parent = -1, depth = 0, root, [1, 4, 10]
node 1: parent = 0, depth = 1, internal node, [2, 3]
node 2: parent = 1, depth = 2, leaf, []
node 3: parent = 1, depth = 2, leaf, []
node 4: parent = 0, depth = 1, internal node, [5, 6, 7]
node 5: parent = 4, depth = 2, leaf, []
node 6: parent = 4, depth = 2, leaf, []
node 7: parent = 4, depth = 2, internal node, [8, 9]
node 8: parent = 7, depth = 3, leaf, []
node 9: parent = 7, depth = 3, leaf, []
node 10: parent = 0, depth = 1, internal node, [11, 12]
node 11: parent = 10, depth = 2, leaf, []
node 12: parent = 10, depth = 2, leaf, []

Sample Input 2

4
1 3 3 2 0
0 0
3 0
2 0

Sample Output 2

node 0: parent = 1, depth = 1, leaf, []
node 1: parent = -1, depth = 0, root, [3, 2, 0]
node 2: parent = 1, depth = 1, leaf, []
node 3: parent = 1, depth = 1, leaf, []

Note

You can use a left-child, right-sibling representation to implement a tree which has the following data:

the parent of u

the leftmost child of u

the immediate right sibling of u

Template in C

-->

Reference

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



Sample input:
13
0 3 1 4 10
1 2 2 3
2 0
3 0
4 3 5 6 7
5 0
6 0
7 2 8 9
8 0
9 0
10 2 11 12
11 0
12 0


Sample output:
node 0: parent = -1, depth = 0, root, [1, 4, 10]
node 1: parent = 0, depth = 1, internal node, [2, 3]
node 2: parent = 1, depth = 2, leaf, []
node 3: parent = 1, depth = 2, leaf, []
node 4: parent = 0, depth = 1, internal node, [5, 6, 7]
node 5: parent = 4, depth = 2, leaf, []
node 6: parent = 4, depth = 2, leaf, []
node 7: parent = 4, depth = 2, internal node, [8, 9]
node 8: parent = 7, depth = 3, leaf, []
node 9: parent = 7, depth = 3, leaf, []
node 10: parent = 0, depth = 1, internal node, [11, 12]
node 11: parent = 10, depth = 2, leaf, []
node 12: parent = 10, depth = 2, leaf, []

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1000)
   
class Node():
    NIL = -1

    def __init__(self, parent=NIL, left=NIL, right=NIL, depth=-1):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth

def read_nodes(T):
    for _ in range(len(T)):
        id, _, *child = [int(x) for x in input().split()]
        for i, c in enumerate(child):
            if i == 0:
                T[id].left = c
            else:
                T[l].right = c
            l = c
            T[c].parent = id

def calc_depth(T):

    def rec(r, p):
        nonlocal T

        T[r].depth = p
        if T[r].right != Node.NIL:
            rec(T[r].right, p)
        if T[r].left != Node.NIL:
            rec(T[r].left, p + 1)

    rec([u.parent for u in T].index(-1), 0)

def node_type(T, id):
    if T[id].parent == Node.NIL:
        return "root"
    elif T[id].left == Node.NIL:
        return "leaf"
    else:
        return "internal node"

def child(T, id):
    c = []
    i = T[id].left
    while i != Node.NIL:
        c.append(i)
        i = T[i].right
    return c

def print_nodes(T):
    for id in range(len(T)):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(id, T[id].parent, T[id].depth,
                     node_type(T, id), child(T, id)))

def main():
    n = int(input())
    T = [Node() for _ in range(n)]

    read_nodes(T)
    calc_depth(T)
    print_nodes(T)

main()

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(200000)
   
class Node():
    NIL = -1

    def __init__(self, parent=NIL, left=NIL, right=NIL, depth=-1):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth

def read_nodes(T):
    for _ in range(len(T)):
        id, _, *child = [int(x) for x in input().split()]
        for i, c in enumerate(child):
            if i == 0:
                T[id].left = c
            else:
                T[l].right = c
            l = c
            T[c].parent = id

def calc_depth(T):

    def rec(r, p):
        nonlocal T

        T[r].depth = p
        if T[r].right != Node.NIL:
            rec(T[r].right, p)
        if T[r].left != Node.NIL:
            rec(T[r].left, p + 1)

    rec([u.parent for u in T].index(-1), 0)

def node_type(T, id):
    if T[id].parent == Node.NIL:
        return "root"
    elif T[id].left == Node.NIL:
        return "leaf"
    else:
        return "internal node"

def child(T, id):
    c = []
    i = T[id].left
    while i != Node.NIL:
        c.append(i)
        i = T[i].right
    return c

def print_nodes(T):
    for id in range(len(T)):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(id, T[id].parent, T[id].depth,
                     node_type(T, id), child(T, id)))

def main():
    n = int(input())
    T = [Node() for _ in range(n)]

    read_nodes(T)
    calc_depth(T)
    print_nodes(T)

main()

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000)
   
class Node():
    NIL = -1

    def __init__(self, parent=NIL, left=NIL, right=NIL, depth=-1):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth

def read_nodes(T):
    for _ in range(len(T)):
        id, _, *child = [int(x) for x in input().split()]
        for i, c in enumerate(child):
            if i == 0:
                T[id].left = c
            else:
                T[l].right = c
            l = c
            T[c].parent = id

def calc_depth(T):

    def rec(r, p):
        nonlocal T

        T[r].depth = p
        if T[r].right != Node.NIL:
            rec(T[r].right, p)
        if T[r].left != Node.NIL:
            rec(T[r].left, p + 1)

    rec([u.parent for u in T].index(-1), 0)

def node_type(T, id):
    if T[id].parent == Node.NIL:
        return "root"
    elif T[id].left == Node.NIL:
        return "leaf"
    else:
        return "internal node"

def child(T, id):
    c = []
    i = T[id].left
    while i != Node.NIL:
        c.append(i)
        i = T[i].right
    return c

def print_nodes(T):
    for id in range(len(T)):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(id, T[id].parent, T[id].depth,
                     node_type(T, id), child(T, id)))

def main():
    n = int(input())
    T = [Node() for _ in range(n)]

    read_nodes(T)
    calc_depth(T)
    print_nodes(T)

main()

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(50000)
   
class Node():
    NIL = -1

    def __init__(self, parent=NIL, left=NIL, right=NIL, depth=-1):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth

def read_nodes(T):
    for _ in range(len(T)):
        id, _, *child = [int(x) for x in input().split()]
        for i, c in enumerate(child):
            if i == 0:
                T[id].left = c
            else:
                T[l].right = c
            l = c
            T[c].parent = id

def calc_depth(T):

    def rec(r, p):
        nonlocal T

        T[r].depth = p
        if T[r].right != Node.NIL:
            rec(T[r].right, p)
        if T[r].left != Node.NIL:
            rec(T[r].left, p + 1)

    rec([u.parent for u in T].index(-1), 0)

def node_type(T, id):
    if T[id].parent == Node.NIL:
        return "root"
    elif T[id].left == Node.NIL:
        return "leaf"
    else:
        return "internal node"

def child(T, id):
    c = []
    i = T[id].left
    while i != Node.NIL:
        c.append(i)
        i = T[i].right
    return c

def print_nodes(T):
    for id in range(len(T)):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(id, T[id].parent, T[id].depth,
                     node_type(T, id), child(T, id)))

def main():
    n = int(input())
    T = [Node() for _ in range(n)]

    read_nodes(T)
    calc_depth(T)
    print_nodes(T)

main()

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(99999)
   
class Node():
    NIL = -1

    def __init__(self, parent=NIL, left=NIL, right=NIL, depth=-1):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth

def read_nodes(T):
    for _ in range(len(T)):
        id, _, *child = [int(x) for x in input().split()]
        for i, c in enumerate(child):
            if i == 0:
                T[id].left = c
            else:
                T[l].right = c
            l = c
            T[c].parent = id

def calc_depth(T):

    def rec(r, p):
        nonlocal T

        T[r].depth = p
        if T[r].right != Node.NIL:
            rec(T[r].right, p)
        if T[r].left != Node.NIL:
            rec(T[r].left, p + 1)

    rec([u.parent for u in T].index(-1), 0)

def node_type(T, id):
    if T[id].parent == Node.NIL:
        return "root"
    elif T[id].left == Node.NIL:
        return "leaf"
    else:
        return "internal node"

def child(T, id):
    c = []
    i = T[id].left
    while i != Node.NIL:
        c.append(i)
        i = T[i].right
    return c

def print_nodes(T):
    for id in range(len(T)):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(id, T[id].parent, T[id].depth,
                     node_type(T, id), child(T, id)))

def main():
    n = int(input())
    T = [Node() for _ in range(n)]

    read_nodes(T)
    calc_depth(T)
    print_nodes(T)

main()

Submission status: Runtime Error

Solution code:
#include<stdio.h>
#include<stdlib.h>
#define MAX 100000
#define NIL -1

typedef struct node {
    int p;
    int l;
    int r;
} Node;

Node no[MAX];
int D[MAX];



void setDepth(int u, int p){
    D[u] = p;
    if(no[u].l != NIL){
        setDepth(no[u].l, p + 1);
    } 
    if (no[u].r != NIL){
        setDepth(no[u].r, p);
    }
}

void print(int u){
    int i, c;
    printf("node ");
    printf("%d: ", u);

    printf("parent = %d, ", no[u].p);
    printf("depth = %d, ",  D[u]);
    if(no[u].p == NIL) printf("root, ");
    else if (no[u].l == NIL ) printf("leaf, ");
    else printf("internal node, ");

    printf("[");
    for(i = 0, c = no[u].l; c != NIL; i++, c = no[c].r){
        if(i) printf(", ");
        printf("%d", c);
    }
    printf("]");

    printf("\n");


}

int main(){
    int n, i, j, v, l = 0;
    int tmp;
    int a[10];

    scanf("%d", &n);
    /* initialize */
    for(i = 0; i < n; i++){
        no[i].p = no[i].l = no[i].r = NIL;
    }

    for(i = 0; i < n; i++){
        int id, k;
        scanf("%d%d", &id, &k);
    
        for(j = 0; j < k; j++){
            int c;
            tmp = scanf("%d", &c);
            if(j == 0) no[id].l = c;
            else no[l].r = c;
            l = c;
            no[t].p = id;
        }
    }

    int r;
    for(i = 0; i < n; i++){
        if(no[i].p == NIL) r = i;
    }
    setDepth(r, 0);
    for(i = 0; i < n; i++) print(i);
    return 0;
}

Submission status: Runtime Error

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


def rec(u, p):
    D[u] = p
    if T[u].r != -1:
        rec(T[u].r, p)
    if T[u].l != -1:
        rec(T[u].l, p + 1)


N = int(input())
T = [Node(-1, -1, -1) for _ in range(N)]
D = [-1] * N
for i in range(N):
    i, k, *cs = map(int, input().split())
    for j, c in enumerate(cs):
        if j == 0:
            T[i].l = c
        else:
            T[l].r = c
        l = c
        T[c].p = i
for i, t in enumerate(T):
    if t.p == -1:
        r = i
rec(r, 0)
for i, t in enumerate(T):
    cs = []
    c = t.l
    while c != -1:
        cs.append(c)
        c = T[c].r
    if t.p == -1:
        print('node {}: parent = {}, depth = {}, root, {}'
              .format(i, t.p, D[i], cs))
    elif t.l == -1:
        print('node {}: parent = {}, depth = {}, leaf, {}'
              .format(i, t.p, D[i], cs))
    else:
        print('node {}: parent = {}, depth = {}, internal node, {}'
              .format(i, t.p, D[i], cs))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

class Node():
    def __init__(self, p, l, r):
        self.p = p
        self.l = l
        self.r = r


def rec(u, p):
    D[u] = p
    if T[u].r != -1:
        rec(T[u].r, p)
    if T[u].l != -1:
        rec(T[u].l, p + 1)


N = int(input())
T = [Node(-1, -1, -1) for _ in range(N)]
D = [-1] * N
for i in range(N):
    i, k, *cs = map(int, input().split())
    for j, c in enumerate(cs):
        if j == 0:
            T[i].l = c
        else:
            T[l].r = c
        l = c
        T[c].p = i
for i, t in enumerate(T):
    if t.p == -1:
        r = i
rec(r, 0)
for i, t in enumerate(T):
    cs = []
    c = t.l
    while c != -1:
        cs.append(c)
        c = T[c].r
    if t.p == -1:
        print('node {}: parent = {}, depth = {}, root, {}'
              .format(i, t.p, D[i], cs))
    elif t.l == -1:
        print('node {}: parent = {}, depth = {}, leaf, {}'
              .format(i, t.p, D[i], cs))
    else:
        print('node {}: parent = {}, depth = {}, internal node, {}'
              .format(i, t.p, D[i], cs))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

class Node():
    def __init__(self, p, l, r):
        self.p = p
        self.l = l
        self.r = r


def rec(u, p):
    D[u] = p
    if T[u].r != -1:
        rec(T[u].r, p)
    if T[u].l != -1:
        rec(T[u].l, p + 1)


N = int(input())
T = [Node(-1, -1, -1) for _ in range(N)]
D = [-1] * N
for i in range(N):
    i, k, *cs = map(int, input().split())
    for j, c in enumerate(cs):
        if j == 0:
            T[i].l = c
        else:
            T[l].r = c
        l = c
        T[c].p = i
for i, t in enumerate(T):
    if t.p == -1:
        r = i
rec(r, 0)
for i, t in enumerate(T):
    cs = []
    c = t.l
    while c != -1:
        cs.append(c)
        c = T[c].r
    if t.p == -1:
        print('node {}: parent = {}, depth = {}, root, {}'
              .format(i, t.p, D[i], cs))
    elif t.l == -1:
        print('node {}: parent = {}, depth = {}, leaf, {}'
              .format(i, t.p, D[i], cs))
    else:
        print('node {}: parent = {}, depth = {}, internal node, {}'
              .format(i, t.p, D[i], cs))

Submission status: Runtime Error

Solution code:
class Tree():
    def __init__(self, root_id):
        self.nodes = {root_id:Node(root_id)}
    def add_node(self, parent_id, child_id):
        child = Node(child_id, self.nodes[parent_id])
        self.nodes[child.id] = child
    
class Node():
    def __init__(self, id, parent = None):
        self.id = id
        self.parent = parent
        self.children = []
        if self.parent:
            self.parent.children.append(self)
            self.depth = self.parent.depth + 1
            self.nodetype = 'leaf'
            if self.parent.nodetype == 'leaf':
                self.parent.nodetype = 'internal node'
        else:
            self.depth = 0
            self.nodetype = 'root'
            
    def walk(self):
        yield self
        for child in self.children:
            for node in child.walk():
                yield node

    def __str__(self):
        parent = self.parent.id if self.parent else -1
        children = ' ,'.join([str(node.id) for node in self.children])
        return 'node {}: parent = {}, depth = {}, {}, [{}]'.format(self.id, parent, self.depth, self.nodetype, children)

    
tree

n = int(input())
for i in range(n):
    line = input().split()
    id = int(line[0])
    if i == 0:
        tree = Tree(id)
    for ci in map(int, line[2:]):
        tree.add_node(id, ci)

for id in tree.nodes:
    print( tree.nodes[id])

Submission status: Runtime Error

Solution code:
class Tree():
    def __init__(self, root_id):
        self.nodes = {root_id:Node(root_id)}
    def add_node(self, parent_id, child_id):
        child = Node(child_id, self.nodes[parent_id])
        self.nodes[child.id] = child
    
class Node():
    def __init__(self, id, parent = None):
        self.id = id
        self.parent = parent
        self.children = []
        if self.parent:
            self.parent.children.append(self)
            self.depth = self.parent.depth + 1
            self.nodetype = 'leaf'
            if self.parent.nodetype == 'leaf':
                self.parent.nodetype = 'internal node'
        else:
            self.depth = 0
            self.nodetype = 'root'
            
    def walk(self):
        yield self
        for child in self.children:
            for node in child.walk():
                yield node

    def __str__(self):
        parent = self.parent.id if self.parent else -1
        children = ' ,'.join([str(node.id) for node in self.children])
        return 'node {}: parent = {}, depth = {}, {}, [{}]'.format(self.id, parent, self.depth, self.nodetype, children)

    
tree = None

n = int(input())
for i in range(n):
    line = input().split()
    id = int(line[0])
    if i == 0:
        tree = Tree(id)
    for ci in map(int, line[2:]):
        tree.add_node(id, ci)

for id in tree.nodes:
    print( tree.nodes[id])

Submission status: Runtime Error

Solution code:
def Get_leafs_list(T, p):
    l = p.l
    ans = []
    while(T[l].r != -1):
        ans.append(T[l].r)
        l = T[l].r
    return ans

def rec(T,node, p):
    T[node].d = p
    if(T[node].r != -1):
        rec(T,T[node].r, p)
    if(T[node].l != -1):
        rec(T,T[node].l, p+1)


class Node():
    def __init__(self,i):
        self.p = -1
        self.l = -1
        self.r = -1
        self.d = 0
        self.n = i

    def Get_leafs_list(self,T):
        l = self.l
        if l != -1:
            ans = [l]
        else:
            ans = []
        while(T[l].r != -1):
            ans.append(T[l].r)
            l = T[l].r
        return ans


    def print_ans(self):
        print("node",self.n, end=": ")
        print("parent =",self.p, end=", ")
        print('depth =',self.d, end=", ")
        if self.l == -1 and self.p != -1:
            print('leaf, []')
            return
        else:
            if self.p == -1:
                print("root",end=", ")
            else :
                print("internal node",end=", ")
            ans = self.Get_leafs_list(T)
            print(ans)
T = []
n = int(input())
for i in range(0,n):
    T.append(Node(i))

for i in range(0,n):
    data = [int(x) for x in input().split()]
    k = data[0]
    if(data[1] != 0):   # node has leafs
        for j in range(0,data[1]):  #leafs
            if j == 0:
                T[k].l = data[2]
            else:
                T[l].r = data[2+j]
            l = data[2+j]
            T[l].p = data[0]
#get root 
for x in range(0,n):
    if(T[x].p == -1):
        root = x
        break

rec(T,root,0)

for x in T:
    x.print_ans()

Submission status: Runtime Error

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

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

def set_depth(u,d):
    global D
    global tree
    D[u] = d
    if not tree[u].right == -1:
        set_depth(tree[u].right, d)
    if not tree[u].left == -1:
        set_depth(tree[u].left, d+1)

def print_tree(t,D):
    for i in range(len(t)):
        children = []
        c = t[i].left
        if not c == -1:
            while True:
                children.append(c)
                c = t[c].right
                if c == -1: break
        print "node %s: parent = %s, depth = %s, %s, [%s]" % (i, t[i].parent, D[i], t[i].get_type(), ", ".join(map(str, children)))

n = int(raw_input())

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

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

D = {}
set_depth(r, 0)

print_tree(tree, D)

Submission status: Runtime Error

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

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

def set_depth(u,d):
    global D
    global tree
    D[u] = d
    if not tree[u].right == -1:
        set_depth(tree[u].right, d)
    if not tree[u].left == -1:
        set_depth(tree[u].left, d+1)

def print_tree(t,D):
    for i in range(len(t)):
        children = []
        c = t[i].left
        if not c == -1:
            while True:
                children.append(c)
                c = t[c].right
                if c == -1: break
        print "node %s: parent = %s, depth = %s, %s, [%s]" % (i, t[i].parent, D[i], t[i].get_type(), ", ".join(map(str, children)))

n = int(raw_input().strip())

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

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

D = {}
set_depth(r, 0)

print_tree(tree, D)

Submission status: Runtime Error

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

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

def set_depth(u,d):
    global D
    global tree
    D[u] = d
    while not tree[u].right == -1:
        u = tree[u].right
        D[u] = d
    if not tree[u].left == -1:
        set_depth(tree[u].left, d+1)

def print_tree(t,D):
    for i in range(len(t)):
        children = []
        c = t[i].left
        if not c == -1:
            while True:
                children.append(c)
                c = t[c].right
                if c == -1: break
        print "node %s: parent = %s, depth = %s, %s, [%s]" % (i, t[i].parent, D[i], t[i].get_type(), ", ".join(map(str, children)))

n = int(raw_input().strip())

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

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

D = {}
set_depth(r, 0)

print_tree(tree, D)

Submission status: Runtime Error

Solution code:
n = int(input())
tree = [None] * n
formatted_tree = [None] * n


def register_node(i, node, searching):
    if not searching:
        return False
    for si, st in enumerate(searching[1]):
        if st[0] == i:
            searching[1][si] = node
            return True
        elif st[1]:
            if register_node(i, node, st):
                return True
    return False


def format(node, parent, depth):
    (i, cs) = node
    cis = [format(c, i, depth + 1) for c in cs]
    formatted_tree[i] = 'node {0}: parent = {1}, depth = {2}, {3}, [{4}]'.format(
        i, parent, depth,
        'root' if not depth else 'internal node' if cis else 'leaf',
        ', '.join(cis)
    )
    return str(i)


while n:
    l = list(map(int, input().split()))
    i, cs = l[0], l[2:]
    node = (i, [(c, None) for c in cs])
    for p in tree:
        if register_node(i, node, p):
            break
    else:
        tree[i] = node

    for i, ci in enumerate(cs):
        if tree[ci]:
            cs[i] = tree[ci]
            tree[ci] = None

    n -= 1

format(next(filter(None, tree)), -1, 0)

for fn in formatted_tree:
    print(fn)

Submission status: Runtime Error

Solution code:
"""Rooted Trees."""

class Node:
    def __init__(self, num, parent, rightSibling, *children):
        self.id = num
        self.parent = parent
        self.rightSibling = rightSibling
        self.children = list(children)
        self.depth = 0
    def showInfo(self):
        print('node {0}: '.format(self.id), end = '')
        print('parent = {0}, '.format(self.parent), end = '')
        print('depth = {0}, '.format(self.depth), end = '')
        if self.children and self.parent != -1:
            print('internal node, ', end = '')
        elif self.parent != -1:
            print('leaf, ', end = '')
        else:
            print('root, ', end = '')
        print('{0}'.format(self.children))

def setNode(num, k, *children):
    if T[num]:
        T[num].children = list(children)
    else:
        node = Node(num, -1, None, *children)
        T[num] = node
    if children:
        for i, x in enumerate(children[:-1]):
            if T[x]:
                T[x].parent = num
                T[x].rightSibling = children[i + 1]
            else:
                node = Node(x, num, children[i + 1])
                T[x] = node
        lastChild = children[-1]
        if T[lastChild]:
            T[lastChild].parent = num
        else:
            node = Node(lastChild, num, None)
            T[lastChild] = node

def setDepth(u, p):
    T[u].depth = p
    if T[u].children:
        setDepth(T[u].children[0], p + 1)
    if T[u].rightSibling:
        setDepth(T[u].rightSibling, p)

def findRoot(r):
    if T[r].parent == -1:
        return r
    findRoot(T[r].parent)


import sys

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

T = [None for i in range(n)]

for x in sys.stdin.readlines():
    setNode(*list(map(int, x.split())))

r = findRoot(0)

setDepth(r, 0)

for x in T:
    x.showInfo()

Submission status: Runtime Error

Solution code:
"""Rooted Trees."""

class Node:
    def __init__(self, num, parent, rightSibling, *children):
        self.id = num
        self.parent = parent
        self.rightSibling = rightSibling
        self.children = list(children)
        self.depth = 0
    def showInfo(self):
        print('node {0}: '.format(self.id), end = '')
        print('parent = {0}, '.format(self.parent), end = '')
        print('depth = {0}, '.format(self.depth), end = '')
        if self.children and self.parent != -1:
            print('internal node, ', end = '')
        elif self.parent != -1:
            print('leaf, ', end = '')
        else:
            print('root, ', end = '')
        print('{0}'.format(self.children))

def setNode(num, k, *children):
    if T[num]:
        T[num].children = list(children)
    else:
        node = Node(num, -1, None, *children)
        T[num] = node
    if children:
        for i, x in enumerate(children[:-1]):
            if T[x]:
                T[x].parent = num
                T[x].rightSibling = children[i + 1]
            else:
                node = Node(x, num, children[i + 1])
                T[x] = node
        lastChild = children[-1]
        if T[lastChild]:
            T[lastChild].parent = num
        else:
            node = Node(lastChild, num, None)
            T[lastChild] = node

def setDepth(u, p):
    T[u].depth = p
    if T[u].children:
        setDepth(T[u].children[0], p + 1)
    if T[u].rightSibling != None:
        setDepth(T[u].rightSibling, p)

def findRoot(r):
    if T[r].parent == -1:
        return r
    return findRoot(T[r].parent)


import sys

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

T = [None for i in range(n)]

for x in sys.stdin.readlines():
    setNode(*list(map(int, x.split())))

r = findRoot(0)

setDepth(r, 0)

for x in T:
    x.showInfo()