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:
"""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

sys.setrecursionlimit(100000)

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

sys.setrecursionlimit(1000000)

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:
import sys

n = int(raw_input())


#class of node
class Node:
    def __init__(self):
        self.p = -1
        self.l = -1
        self.r = -1

T = [ Node() for _ in xrange(n)] #info of u
D = [0] * n #depth of u

def printInfo(u):
    #print 'node', u, ':',
    #print 'parent = ', T[u].p, ',',
    #print 'depth = ', D[u], ',',
    print "node {}: parent = {}, depth = {},".format(u, T[u].p, D[u]) ,
    if T[u].p == -1: 
        print 'root, ',
    elif T[u].l == -1:
        print 'leaf, ',
    else:
        print 'internal node, ',

    #print '[',
    sys.stdout.write("[")

    c = T[u].l
    i = 0
    while c != -1:
        if i > 0:
            print ', ',
        sys.stdout.write(str(c))
        #print "{}".format(c),
        c = T[c].r
        i += 1
    #print ']'
    sys.stdout.write("]\n")

    return 0

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

def main():
    for i in xrange(n):
        a = map(int, raw_input().split())
        v = a[0]
        d = a[1]
        for j in xrange(d):
            if j == 0:
                T[v].l = a[j+2]
            else:
                T[l].r = a[j+2]
            l = a[j+2]
            T[a[j+2]].p = v
    for i in xrange(n):
        if T[i].p == -1:
            r = i

    rec(r, 0)

    for i in xrange(n):
        printInfo(i)

    return 0

main()

Submission status: Runtime Error

Solution code:
from collections import deque, namedtuple

class RootedTree:
    def __init__(self, t, n):
        self.t = t
        self.n = n
        self.d = [-1] * n
    def setDepth(self, u, p):
        self.d[u] = p
        if self.t[u].r != -1:
            self.setDepth(self.t[u].r, p)
        if self.t[u].l != -1:
            self.setDepth(self.t[u].l, p + 1)
        return(self.d)
    def getChildren(self, u):
        ret = []
        c = self.t[u].l
        while c != -1:
            ret.append(c)
            c = self.t[c].r
        return(ret)
    def printNode(self, i):
        p_ = self.t[i].p
        d_ = self.d[i]
        c_ = self.getChildren(i)
        if p_ == -1:
            t_ = "root"
        elif len(c_) == 0:
            t_ = "leaf"
        else:
            t_ = "internal node"
        print("node {}: parent = {}, depth = {}, {}, {}".format(i, p_, d_, t_, c_))

if __name__ == '__main__':
    n = int(input().rstrip())
    Node = namedtuple('Node', ['p', 'l', 'r'])
    t = [Node(-1, -1, -1)] * n
    r = -1
    for i in range(n):
        tmp = deque([int(i) for i in input().rstrip().split(" ")])
        v = tmp.popleft()
        d = tmp.popleft()
        for j in range(d):
            c = tmp.popleft()
            if j == 0:
                t[v] = t[v]._replace(l = c)
            else:
                t[l] = t[l]._replace(r = c)
            l = c
            t[c] = t[c]._replace(p = v)
    for i in range(n):
        if (t[i].p == -1):
            r = i
    x = RootedTree(t, n)
    x.setDepth(r, 0)
    for i in range(n):
        x.printNode(i)

Submission status: Runtime Error

Solution code:
from collections import deque, namedtuple
import sys
sys.setrecursionlimit(10000)

class RootedTree:
    def __init__(self, t, n):
        self.t = t
        self.n = n
        self.d = [-1] * n
    def setDepth(self, u, p):
        self.d[u] = p
        if self.t[u].r != -1:
            self.setDepth(self.t[u].r, p)
        if self.t[u].l != -1:
            self.setDepth(self.t[u].l, p + 1)
        return(self.d)
    def getChildren(self, u):
        ret = []
        c = self.t[u].l
        while c != -1:
            ret.append(c)
            c = self.t[c].r
        return(ret)
    def printNode(self, i):
        p_ = self.t[i].p
        d_ = self.d[i]
        c_ = self.getChildren(i)
        if p_ == -1:
            t_ = "root"
        elif len(c_) == 0:
            t_ = "leaf"
        else:
            t_ = "internal node"
        print("node {}: parent = {}, depth = {}, {}, {}".format(i, p_, d_, t_, c_))

if __name__ == '__main__':
    n = int(input().rstrip())
    Node = namedtuple('Node', ['p', 'l', 'r'])
    t = [Node(-1, -1, -1)] * n
    r = -1
    for i in range(n):
        tmp = deque([int(i) for i in input().rstrip().split(" ")])
        v = tmp.popleft()
        d = tmp.popleft()
        for j in range(d):
            c = tmp.popleft()
            if j == 0:
                t[v] = t[v]._replace(l = c)
            else:
                t[l] = t[l]._replace(r = c)
            l = c
            t[c] = t[c]._replace(p = v)
    for i in range(n):
        if (t[i].p == -1):
            r = i
    x = RootedTree(t, n)
    x.setDepth(r, 0)
    for i in range(n):
        x.printNode(i)

Submission status: Runtime Error

Solution code:
from collections import deque, namedtuple
import sys
sys.setrecursionlimit(100000)

class RootedTree:
    def __init__(self, t, n):
        self.t = t
        self.n = n
        self.d = [-1] * n
    def setDepth(self, u, p):
        self.d[u] = p
        if self.t[u].r != -1:
            self.setDepth(self.t[u].r, p)
        if self.t[u].l != -1:
            self.setDepth(self.t[u].l, p + 1)
        return(self.d)
    def getChildren(self, u):
        ret = []
        c = self.t[u].l
        while c != -1:
            ret.append(c)
            c = self.t[c].r
        return(ret)
    def printNode(self, i):
        p_ = self.t[i].p
        d_ = self.d[i]
        c_ = self.getChildren(i)
        if p_ == -1:
            t_ = "root"
        elif len(c_) == 0:
            t_ = "leaf"
        else:
            t_ = "internal node"
        print("node {}: parent = {}, depth = {}, {}, {}".format(i, p_, d_, t_, c_))

if __name__ == '__main__':
    n = int(input().rstrip())
    Node = namedtuple('Node', ['p', 'l', 'r'])
    t = [Node(-1, -1, -1)] * n
    r = -1
    for i in range(n):
        tmp = deque([int(i) for i in input().rstrip().split(" ")])
        v = tmp.popleft()
        d = tmp.popleft()
        for j in range(d):
            c = tmp.popleft()
            if j == 0:
                t[v] = t[v]._replace(l = c)
            else:
                t[l] = t[l]._replace(r = c)
            l = c
            t[c] = t[c]._replace(p = v)
    for i in range(n):
        if (t[i].p == -1):
            r = i
    x = RootedTree(t, n)
    x.setDepth(r, 0)
    for i in range(n):
        x.printNode(i)

Submission status: Runtime Error

Solution code:
from collections import deque, namedtuple
import sys
sys.setrecursionlimit(1000000)

class RootedTree:
    def __init__(self, t, n):
        self.t = t
        self.n = n
        self.d = [-1] * n
    def setDepth(self, u, p):
        self.d[u] = p
        if self.t[u].r != -1:
            self.setDepth(self.t[u].r, p)
        if self.t[u].l != -1:
            self.setDepth(self.t[u].l, p + 1)
        return(self.d)
    def getChildren(self, u):
        ret = []
        c = self.t[u].l
        while c != -1:
            ret.append(c)
            c = self.t[c].r
        return(ret)
    def printNode(self, i):
        p_ = self.t[i].p
        d_ = self.d[i]
        c_ = self.getChildren(i)
        if p_ == -1:
            t_ = "root"
        elif len(c_) == 0:
            t_ = "leaf"
        else:
            t_ = "internal node"
        print("node {}: parent = {}, depth = {}, {}, {}".format(i, p_, d_, t_, c_))

if __name__ == '__main__':
    n = int(input().rstrip())
    Node = namedtuple('Node', ['p', 'l', 'r'])
    t = [Node(-1, -1, -1)] * n
    r = -1
    for i in range(n):
        tmp = deque([int(i) for i in input().rstrip().split(" ")])
        v = tmp.popleft()
        d = tmp.popleft()
        for j in range(d):
            c = tmp.popleft()
            if j == 0:
                t[v] = t[v]._replace(l = c)
            else:
                t[l] = t[l]._replace(r = c)
            l = c
            t[c] = t[c]._replace(p = v)
    for i in range(n):
        if (t[i].p == -1):
            r = i
    x = RootedTree(t, n)
    x.setDepth(r, 0)
    for i in range(n):
        x.printNode(i)

Submission status: Runtime Error

Solution code:
from collections import deque, namedtuple
import sys
sys.setrecursionlimit(100000000)

class RootedTree:
    def __init__(self, t, n):
        self.t = t
        self.n = n
        self.d = [-1] * n
    def setDepth(self, u, p):
        self.d[u] = p
        if self.t[u].r != -1:
            self.setDepth(self.t[u].r, p)
        if self.t[u].l != -1:
            self.setDepth(self.t[u].l, p + 1)
        return(self.d)
    def getChildren(self, u):
        ret = []
        c = self.t[u].l
        while c != -1:
            ret.append(c)
            c = self.t[c].r
        return(ret)
    def printNode(self, i):
        p_ = self.t[i].p
        d_ = self.d[i]
        c_ = self.getChildren(i)
        if p_ == -1:
            t_ = "root"
        elif len(c_) == 0:
            t_ = "leaf"
        else:
            t_ = "internal node"
        print("node {}: parent = {}, depth = {}, {}, {}".format(i, p_, d_, t_, c_))

if __name__ == '__main__':
    n = int(input().rstrip())
    Node = namedtuple('Node', ['p', 'l', 'r'])
    t = [Node(-1, -1, -1)] * n
    r = -1
    for i in range(n):
        tmp = deque([int(i) for i in input().rstrip().split(" ")])
        v = tmp.popleft()
        d = tmp.popleft()
        for j in range(d):
            c = tmp.popleft()
            if j == 0:
                t[v] = t[v]._replace(l = c)
            else:
                t[l] = t[l]._replace(r = c)
            l = c
            t[c] = t[c]._replace(p = v)
    for i in range(n):
        if (t[i].p == -1):
            r = i
    x = RootedTree(t, n)
    x.setDepth(r, 0)
    for i in range(n):
        x.printNode(i)

Submission status: Runtime Error

Solution code:
from collections import deque, namedtuple
import sys
sys.setrecursionlimit(1000000000)

class RootedTree:
    def __init__(self, t, n):
        self.t = t
        self.n = n
        self.d = [-1] * n
    def setDepth(self, u, p):
        self.d[u] = p
        if self.t[u].r != -1:
            self.setDepth(self.t[u].r, p)
        if self.t[u].l != -1:
            self.setDepth(self.t[u].l, p + 1)
        return(self.d)
    def getChildren(self, u):
        ret = []
        c = self.t[u].l
        while c != -1:
            ret.append(c)
            c = self.t[c].r
        return(ret)
    def printNode(self, i):
        p_ = self.t[i].p
        d_ = self.d[i]
        c_ = self.getChildren(i)
        if p_ == -1:
            t_ = "root"
        elif len(c_) == 0:
            t_ = "leaf"
        else:
            t_ = "internal node"
        print("node {}: parent = {}, depth = {}, {}, {}".format(i, p_, d_, t_, c_))

if __name__ == '__main__':
    n = int(input().rstrip())
    Node = namedtuple('Node', ['p', 'l', 'r'])
    t = [Node(-1, -1, -1)] * n
    r = -1
    for i in range(n):
        tmp = deque([int(i) for i in input().rstrip().split(" ")])
        v = tmp.popleft()
        d = tmp.popleft()
        for j in range(d):
            c = tmp.popleft()
            if j == 0:
                t[v] = t[v]._replace(l = c)
            else:
                t[l] = t[l]._replace(r = c)
            l = c
            t[c] = t[c]._replace(p = v)
    for i in range(n):
        if (t[i].p == -1):
            r = i
    x = RootedTree(t, n)
    x.setDepth(r, 0)
    for i in range(n):
        x.printNode(i)

Submission status: Runtime Error

Solution code:

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

    def show_info(self):
        print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(self.id, self.parent, self.depth,self.type, self.children))


def set_node(i_s):
    num, children = i_s[0], i_s[2:]
    node = Node(num, -1, children)
    T[num] = node
    for n in children:
        T[-1] -= n


def set_pdt(n_i, parent, depth):
    node = T[n_i]
    node.parent = parent
    node.depth = depth
    if node.children:
        node.type = 'internal node'
        for n in node.children:
            set_pdt(n, n_i, depth + 1)
    else:
        node.type = 'leaf'



n = int(input())
tree = [list(map(int, input().split())) for i in range(n)]
T = [None] * n

T += [int(n * (n - 1) / 2)]

for i in range(n):
    set_node(tree[i])
set_pdt(1, -1, 0)

T[0].type ='root'

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

Submission status: Runtime Error

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

class Node(object):
    # left????????¨??????????????????(leaf), right???s?????¨??????????????????????????????
    # ???????????????????????????????????¨???????????´??????parent???-1?????????
    def __init__(self, N):
        self.p = [-1 for i in range(N)]
        self.l = [-1 for i in range(N)]
        self.r = [-1 for i in range(N)]
        self.D = [-1 for i in range(N)]

    def set_depth(self, u, p):
        self.D[u] = p
        if self.r[u] is not -1:
            self.set_depth(self.r[u], p)
        if self.l[u] is not -1:
            self.set_depth(self.l[u], p+1)

    def print_children(self, u):
        children = []
        flag = self.l[u]
        while flag is not -1:
            children.append(flag)
            flag = self.r[flag]
            
        return children
        

#f = open("input.txt")
#N = int(f.readline())
N = input()

T = Node(N)

for j in range(N):
    #A = [int(i) for i in f.readline().split()]
    A = [int(i) for i in input().readline().split()]
    
    # left????±????
    if len(A) > 2:
        T.l[j] = A[2]
    else:
        T.l[j] = -1

    # parent???right????±????
    for index, i in enumerate(A[2:]):
        if(A[-1] == i):
            T.p[i], T.r[i] = A[0], -1
        else:
            T.p[i], T.r[i] = A[0], A[index+3]

T.set_depth(0, 0)

for i in range(N):
    if T.p[i] is -1:
        node = "root"
    elif T.l[i] is -1:
        node = "leaf"
    else:
        node = "internal node"
        
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(i, T.p[i], T.D[i], node, T.print_children(i)))

Submission status: Runtime Error

Solution code:
class Node(object):
    def __init__(self, N):
        self.p = [-1 for i in range(N)]
        self.l = [-1 for i in range(N)]
        self.r = [-1 for i in range(N)]
        self.D = [-1 for i in range(N)]

    def set_depth(self, u, p):
        self.D[u] = p
        if self.r[u] is not -1:
            self.set_depth(self.r[u], p)
        if self.l[u] is not -1:
            self.set_depth(self.l[u], p+1)

    def print_children(self, u):
        children = []
        flag = self.l[u]
        while flag is not -1:
            children.append(flag)
            flag = self.r[flag]
            
        return children

N = int(input())
T = Node(N)

for j in range(N):
    A = [int(i) for i in input().readline().split()]
    
    # left????±????
    if len(A) > 2:
        T.l[j] = A[2]
    else:
        T.l[j] = -1

    # parent???right????±????
    for index, i in enumerate(A[2:]):
        if(A[-1] == i):
            T.p[i], T.r[i] = A[0], -1
        else:
            T.p[i], T.r[i] = A[0], A[index+3]

T.set_depth(0, 0)

for i in range(N):
    if T.p[i] is -1:
        node = "root"
    elif T.l[i] is -1:
        node = "leaf"
    else:
        node = "internal node"
        
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(i, T.p[i], T.D[i], node, T.print_children(i)))

Submission status: Runtime Error

Solution code:
class Node(object):
    def __init__(self, N):
        self.p = [-1 for i in range(N)]
        self.l = [-1 for i in range(N)]
        self.r = [-1 for i in range(N)]
        self.D = [-1 for i in range(N)]

    def set_depth(self, u, p):
        self.D[u] = p
        if self.r[u] is not -1:
            self.set_depth(self.r[u], p)
        if self.l[u] is not -1:
            self.set_depth(self.l[u], p+1)

    def print_children(self, u):
        children = []
        flag = self.l[u]
        while flag is not -1:
            children.append(flag)
            flag = self.r[flag]
            
        return children

N = int(input())
T = Node(N)

for j in range(N):
    A = [int(i) for i in input().readline().split()]
    
    if len(A) > 2:
        T.l[j] = A[2]
    else:
        T.l[j] = -1

    for index, i in enumerate(A[2:]):
        if(A[-1] == i):
            T.p[i], T.r[i] = A[0], -1
        else:
            T.p[i], T.r[i] = A[0], A[index+3]

T.set_depth(0, 0)

for i in range(N):
    if T.p[i] is -1:
        node = "root"
    elif T.l[i] is -1:
        node = "leaf"
    else:
        node = "internal node"
        
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(i, T.p[i], T.D[i], node, T.print_children(i)))

Submission status: Runtime Error

Solution code:
class Node(object):
    def __init__(self, N):
        self.p = [-1 for i in range(N)]
        self.l = [-1 for i in range(N)]
        self.r = [-1 for i in range(N)]
        self.D = [-1 for i in range(N)]
 
    def set_depth(self, u, p):
        self.D[u] = p
        if self.r[u] is not -1:
            self.set_depth(self.r[u], p)
        if self.l[u] is not -1:
            self.set_depth(self.l[u], p+1)
 
    def print_children(self, u):
        children = []
        flag = self.l[u]
        while flag is not -1:
            children.append(flag)
            flag = self.r[flag]
             
        return children
 
N = int(input())
T = Node(N)
 
for j in range(N):
    A = [int(i) for i in input().split()]
     
    if len(A) > 2:
        T.l[j] = A[2]
    else:
        T.l[j] = -1
 
    for index, i in enumerate(A[2:]):
        if(A[-1] == i):
            T.p[i], T.r[i] = A[0], -1
        else:
            T.p[i], T.r[i] = A[0], A[index+3]
 
T.set_depth(T.p.index(None), 0)
 
for i in range(N):
    if T.p[i] is -1:
        node = "root"
    elif T.l[i] is -1:
        node = "leaf"
    else:
        node = "internal node"
         
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(i, T.p[i], T.D[i], node, T.print_children(i)))

Submission status: Runtime Error

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

class Node(object):
    # left????????¨??????????????????(leaf), right???s?????¨??????????????????????????????
    # ???????????????????????????????????¨???????????´??????parent???-1?????????
    def __init__(self, N):
        self.p = [-1 for i in range(N)]
        self.l = [-1 for i in range(N)]
        self.r = [-1 for i in range(N)]
        self.D = [0 for i in range(N)]

    def set_depth(self, u, p):
        self.D[u] = p
        if self.r[u] is not -1:
            self.set_depth(self.r[u], p)
        if self.l[u] is not -1:
            self.set_depth(self.l[u], p+1)

    def print_children(self, u):
        children = []
        flag = self.l[u]
        while flag is not -1:
            children.append(flag)
            flag = self.r[flag]
            
        return children
        
N = int(input())
T = Node(N)

for j in range(N):
    A = [int(i) for i in input().split()]
    
    # left????±????
    if len(A) > 2:
        T.l[A[0]] = A[2]
    else:
        T.l[A[0]] = -1

    # parent???right????±????
    for index, i in enumerate(A[2:]):
        if(A[-1] == i):
            T.p[i], T.r[i] = A[0], -1
        else:
            T.p[i], T.r[i] = A[0], A[index+3]
    
T.set_depth(T.p.index(-1), 0)

for i in range(N):
    if T.p[i] is -1:
        node = "root"
    elif T.l[i] is -1:
        node = "leaf"
    else:
        node = "internal node"
        
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(i, T.p[i], T.D[i], node, T.print_children(i)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.getrecursionlimit(10000)
class Node(object):
    # left????????¨??????????????????(leaf), right???s?????¨??????????????????????????????
    # ???????????????????????????????????¨???????????´??????parent???-1?????????
    def __init__(self, N):
        self.p = [-1 for i in range(N)]
        self.l = [-1 for i in range(N)]
        self.r = [-1 for i in range(N)]
        self.D = [0 for i in range(N)]

    def set_depth(self, u, p):
        self.D[u] = p
        if self.r[u] is not -1:
            self.set_depth(self.r[u], p)
        if self.l[u] is not -1:
            self.set_depth(self.l[u], p+1)

    def print_children(self, u):
        children = []
        flag = self.l[u]
        while flag is not -1:
            children.append(flag)
            flag = self.r[flag]
            
        return children
        
N = int(input())

T = Node(N)

for j in range(N):
    A = [int(i) for i in input().split()]
    
    # left????±????
    if len(A) > 2:
        T.l[A[0]] = A[2]
    else:
        T.l[A[0]] = -1

    # parent???right????±????
    for index, i in enumerate(A[2:]):
        if(A[-1] == i):
            T.p[i], T.r[i] = A[0], -1
        else:
            T.p[i], T.r[i] = A[0], A[index+3]
    
T.set_depth(T.p.index(-1), 0)

for i in range(N):
    if T.p[i] is -1:
        node = "root"
    elif T.l[i] is -1:
        node = "leaf"
    else:
        node = "internal node"
        
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(i, T.p[i], T.D[i], node, T.print_children(i)))

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(10000)

class Node(object):
    # left????????¨??????????????????(leaf), right???s?????¨??????????????????????????????
    # ???????????????????????????????????¨???????????´??????parent???-1?????????
    def __init__(self, N):
        self.p = [-1 for i in range(N)]
        self.l = [-1 for i in range(N)]
        self.r = [-1 for i in range(N)]
        self.D = [0 for i in range(N)]

    def set_depth(self, u, p):
        self.D[u] = p
        if self.r[u] is not -1:
            self.set_depth(self.r[u], p)
        if self.l[u] is not -1:
            self.set_depth(self.l[u], p+1)

    def print_children(self, u):
        children = []
        flag = self.l[u]
        while flag is not -1:
            children.append(flag)
            flag = self.r[flag]
            
        return children
        
N = int(input())
T = Node(N)

for j in range(N):
    A = [int(i) for i in input().split()]
    
    # left????±????
    if len(A) > 2:
        T.l[A[0]] = A[2]
    else:
        T.l[A[0]] = -1

    # parent???right????±????
    for index, i in enumerate(A[2:]):
        if(A[-1] == i):
            T.p[i], T.r[i] = A[0], -1
        else:
            T.p[i], T.r[i] = A[0], A[index+3]
    
T.set_depth(T.p.index(-1), 0)

for i in range(N):
    if T.p[i] is -1:
        node = "root"
    elif T.l[i] is -1:
        node = "leaf"
    else:
        node = "internal node"
        
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(i, T.p[i], T.D[i], node, T.print_children(i)))