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:
# -*- coding: utf-8 -*-
N = int(input())
tree = {n:{"parent":-1, "left": -1, "right": -1} for n in range(N)} # left-child right-sibing
parent = set([n for n in range(N)])
for n in range(N):
    inp = [int(n) for n in input().split()]
    tree[inp[0]]["children"] = inp[2:]

    tree[inp[0]]["left"] = inp[2] if len(inp) > 2 else -1
    
    for ip in inp[2:]:
        tree[ip]["parent"] = inp[0]
    
    for i, ip in enumerate(inp[2:-1]):
        tree[inp[2+i]]["right"] = inp[3+i]
    parent = parent.difference(inp[2:])    

def set_depth(n, depth):
    tree[n]["depth"] = depth
    if tree[n]["left"] != -1:
        set_depth(tree[n]["left"], depth+1)
    if tree[n]["right"] != -1:
        set_depth(tree[n]["right"], depth)

set_depth(parent.pop(), 0)
        
for n in range(N):
    if tree[n]["parent"] == -1:
        tree[n]["type"] = "root"
    elif tree[n]["children"] != []:
        tree[n]["type"] = "internal node"
    else:
        tree[n]["type"] = "leaf"
        
    print("node {}: parent = {}, depth = {}, {}, {}"\
          .format(n, tree[n]["parent"], tree[n]["depth"], tree[n]["type"], tree[n]["children"]))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(114514)


N = int(input())
tree = {n:{"parent":-1, "left": -1, "right": -1} for n in range(N)} # left-child right-sibing
parent = set([n for n in range(N)])
for n in range(N):
    inp = [int(n) for n in input().split()]
    tree[inp[0]]["children"] = inp[2:]

    tree[inp[0]]["left"] = inp[2] if len(inp) > 2 else -1
    
    for ip in inp[2:]:
        tree[ip]["parent"] = inp[0]
    
    for i, ip in enumerate(inp[2:-1]):
        tree[inp[2+i]]["right"] = inp[3+i]
    parent = parent.difference(inp[2:])    

def set_depth(n, depth):
    tree[n]["depth"] = depth
    if tree[n]["left"] != -1:
        set_depth(tree[n]["left"], depth+1)
    if tree[n]["right"] != -1:
        set_depth(tree[n]["right"], depth)

set_depth(parent.pop(), 0)
        
for n in range(N):
    if tree[n]["parent"] == -1:
        tree[n]["type"] = "root"
    elif tree[n]["children"] != []:
        tree[n]["type"] = "internal node"
    else:
        tree[n]["type"] = "leaf"
        
    print("node {}: parent = {}, depth = {}, {}, {}"\
          .format(n, tree[n]["parent"], tree[n]["depth"], tree[n]["type"], tree[n]["children"]))

Submission status: Runtime Error

Solution code:
def set_pdt(i, p, d):
    u = tree[i]
    u[0], u[1] = p, d
    for c in u[3]:
        set_pdt(c, i, d+1)
    else:
        if u[0] == -1:
            u[2] = "root"
        elif u[3]:
            u[2] = "internal node"
        else:
            u[2] = "leaf"

n = int(input())
#         p d t ch
tree = [[-1,0,0,0] for _ in range(n)]
root = set(range(n))

for _ in range(n):
    i, k, *c = map(int, input().split())
    tree[i][3] = c
    root -= set(c)
    
set_pdt(*root, -1, 0)

for i in range(n):
    u = tree[i]
    print("node {}: parent = {}, depth = {}, {}, {}".format(i, *u))

Submission status: Runtime Error

Solution code:
def set_pdt(i, p, d):
    u = tree[i]
    u[0], u[1] = p, d
    for c in u[3]:
        set_pdt(c, i, d+1)
    else:
        if u[0] == -1:
            u[2] = "root"
        elif u[3]:
            u[2] = "internal node"
        else:
            u[2] = "leaf"

n = int(input())
#         p d t ch
tree = [[-1,0,0,0] for _ in range(n)]
root = set(range(n))

for _ in range(n):
    i, k, *c = map(int, input().split())
    tree[i][3] = c
    root -= set(c)
    
set_pdt(root[0], -1, 0)

for i in range(n):
    u = tree[i]
    print("node {}: parent = {}, depth = {}, {}, {}".format(i, *u))

Submission status: Runtime Error

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


class Node():
    def __init__(self, ID, parent=-1, left=-1, right=-1, depth=0, children=[]):
        self.id = ID
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.children = children


if __name__ == '__main__':

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

    for _ in range(n):
        line = [int(l) for l in input().split(" ")]
        ID = line[0]
        d = line[1]
        if d == 0:
            continue
        else:
            children = line[2:]
            tree[ID].children = children
            tree[ID].left = children[0]
            for j in range(0, d):
                tree[children[j]].parent = ID
                if j < d - 1:
                    tree[children[j]].right = children[j + 1]

    def setDepth(u, p):
        tree[u].depth = p
        if tree[u].right != -1:
            setDepth(tree[u].right, p)
        if tree[u].left != -1:
            setDepth(tree[u].left, p + 1)

    for node in tree:
        if node.parent == -1:
            root = node.id

    setDepth(root, 0)

    for node in tree:
        if node.parent == -1:
            n_type = "root"
        elif node.left != -1:
            n_type = "internal node"
        else:
            n_type = "leaf"

        print("node {}: parent = {}, depth = {}, {}, {}".format(
            node.id, node.parent, node.depth, n_type, node.children))

Submission status: Runtime Error

Solution code:
class tree:
    def __init__(self,name,parent,left,right):
        self.name = name
        self.parent = parent
        self.left = left
        self.right = right
trees = {}
trees['0'] = tree('0','-1','-1','-1')

n = int(input())
for i in range(n):
    s = [i for i in input().split()]
    p = s[0]
    k = s[1]

    s_t = ['-1']+s[2:]+['-1']
    for j in range(1,int(k)+1):
        trees[s_t[j]] = tree(s_t[j],p,s_t[j-1],s_t[j+1])

def getDepth(u):
    d = 0
    while trees[u].parent != '-1':
        u = trees[u].parent
        d += 1
    return d

def getChildren(u):
    c = []
    for i in trees.values():
        if i.parent == u:
            c.append(i.name)
    return c

for i in range(n):
    
    par = trees[str(i)].parent
    dep = getDepth(str(i))
    r = trees[str(i)].right
    l = trees[str(i)].left
    ch = sorted([int(i) for i in getChildren(str(i))])
    
    if par == '-1':sit = 'root'
    elif l == '-1':sit = 'internal node'
    else:sit = 'leaf'
    
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i,par,dep,sit,ch))

Submission status: Runtime Error

Solution code:
class tree:
    def __init__(self,name,parent):
        self.name = name
        self.parent = parent

trees = {}
trees['0'] = tree('0','-1')

n = int(input())
for i in range(n):
    s = [i for i in input().split()]
    p = s[0]

    s_t = s[2:]
    for j in range(len(s_t)):
        trees[s_t[j]] = tree(s_t[j],p)

def getDepth(u):
    d = 0
    while trees[u].parent != '-1':
        u = trees[u].parent
        d += 1
    return d

def getChildren(u):
    c = []
    for i in trees.values():
        if i.parent == u:
            c.append(i.name)
    return c

for i in range(n):
    
    par = trees[str(i)].parent
    dep = getDepth(str(i))
    ch = sorted([int(i) for i in getChildren(str(i))])
    
    if par == '-1':sit = 'root'
    elif len(ch) != 0:sit = 'internal node'
    else:sit = 'leaf'
    
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i,par,dep,sit,ch))

Submission status: Runtime Error

Solution code:
t={}
p={}
for _ in[0]*int(input()):
    e=input().split()
    t[e[0]]=e[2:]
    for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
d={r:0}
for 
for i in t:
    f='root,'if'-1'==p[i]else'internal node,'if t[i]else'leaf,'
    d='0'
    print('node',i+':','parent =',p[i]+',','depth =',d+',',f,list(map(int,t[i])))

Submission status: Runtime Error

Solution code:
def q(a,h):
 d[a]=str(h)
 for b in t[a]:q(b,h+1)
t,p,d={},{},{}
for _ in[0]*int(input()):
 e=input().split()
 t[e[0]]=e[2:]
 for i in e[2:]:p[i]=e[0]
r=(set(t)-set(p)).pop()
p[r]='-1'
q(r,0)
for i in sorted(map(int,t)):
 i=str(i);print(f'node {i}: parent = {p[i]}, depth = {d[i]}, {'root'if'-1'==p[i]else'internal node'if t[i]else'leaf'}, {list(map(int,t[i]))}')

Submission status: Runtime Error

Solution code:
def rec_function(i, p):
    node_info[i]['depth'] = p

    if node_info[i]['parent'] == -1:
        node_info[i]['type'] = 'root'
    elif node_info[i]['left'] == None:
        node_info[i]['type'] = 'leaf'
    else:
        node_info[i]['type'] = 'internal node'

    if node_info[i]['right'] != None:
        rec_function(node_info[i]['right'],  p)
    if node_info[i]['left'] != None:
        rec_function(node_info[i]['left'], p + 1)


n = int(input())
node_info = [ { 
    'parent': None,
    'right': None,
    'left': None,
    'depth': None,
    'type': None,
    'children': [],
} for _ in range(n) ]

for _ in range(n):
    input_info = list(map(int, input().split()))
    node = input_info[0]
    children = input_info[2:]
    
    node_info[node]['children'] = children

    if len(children) > 0:
        node_info[node]['left'] = children[0] 

    for i in range(len(children)):
        node_info[children[i]]['parent'] = node
        if i < len(children) - 1:
            node_info[children[i]]['right'] = children[i+1]

root_node = 0

for i in range(len(node_info)):
    if node_info[i]['parent'] == None:
        node_info[i]['parent'] = -1
        root_node = i
        break

rec_function(root_node, 0)

for i in range(len(node_info)):
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(
        i,
        node_info[i]['parent'],
        node_info[i]['depth'],
        node_info[i]['type'],
        node_info[i]['children']
    ))

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, parent = -1, left = -1, right = -1, depth = 0):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
    
def print_node(i):
    global node
    print("node " + str(i) + ": ", end = "")
    print("parent = " + str(node[i].parent) +", ", end = "")
    print("depth = " + str(node[i].depth) + ", ", end = "")
    if node[i].parent == -1:
        print("root, [", end = "")
    elif node[i].left != -1:
        print("internal node, [", end = "")
    else:
        print("leaf, [", end = "")
    if node[i].left != -1:
        print(str(node[i].left), end = "")
        j = node[i].left
        while node[j].right != -1:
            j = node[j].right
            print(", " + str(j), end = "")
    print("]")
            

n = int(input())
node = [Node() for i in range(n)]
def input_depth(i, n):
    global node
    node[i].depth = n
    if node[i].right != -1:
        input_depth(node[i].right, n)
    if node[i].left != -1:
        input_depth(node[i].left, n + 1)

for i in range(n):
    p, k, *c = list(map(int, input().split()))
    if k > 0:
        node[p].left = c[0]
    for j in range(k):
        node[c[j]].parent = p
        if j != k - 1:
            node[c[j]].right = c[j + 1]

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

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

Submission status: Runtime Error

Solution code:
from enum import Enum, auto

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

class Node():
    def __init__(self, parent=None, left=None, right=None, depth=None, nodetype=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.nodetype = nodetype

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

for i in range(n):
    arr = list(map(int, input().split(' ')))
    if arr[1] == 0:
        nodes[arr[0]].nodetype = NodeType.LEAF
        continue
    id, k, c = arr[0], arr[1], arr[2:]
    nodes[id].nodetype = NodeType.INTERNAL_NODE
    nodes[id].left = c[0]
    for j in range(k-1):
        nodes[c[j]].right = c[j+1]
        nodes[c[j]].parent = id
    nodes[c[k-1]].parent = id

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

# 深さの探索
# h < 20 なので再帰的にたどっても良い
def rec(u, d):
    nodes[u].depth = d
    if nodes[u].right: rec(nodes[u].right, d)
    if nodes[u].left: rec(nodes[u].left, d+1)

rec(root, 0)

for i in range(n):
    if nodes[i].nodetype == NodeType.LEAF:
        print('node %d: parent = %d, depth = %d, leaf, []'%(i, nodes[i].parent, nodes[i].depth))

    c = nodes[i].left
    child_list = []
    while c:
        child_list.append(c)
        c = nodes[c].right

    if nodes[i].nodetype == NodeType.ROOT:
        print('node %d: parent = -1, depth = 0, root,'%(i), child_list)
    elif nodes[i].nodetype == NodeType.INTERNAL_NODE:
        print('node %d: parent = %d, depth = %d, internal node,'%(i, nodes[i].parent, nodes[i].depth), child_list)

Submission status: Runtime Error

Solution code:
from enum import Enum, auto

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

class Node():
    def __init__(self, parent=None, left=None, right=None, depth=None, nodetype=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.nodetype = nodetype

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

for i in range(n):
    arr = list(map(int, input().split(' ')))
    if arr[1] == 0:
        nodes[arr[0]].nodetype = NodeType.LEAF
        continue
    id, k, c = arr[0], arr[1], arr[2:]
    nodes[id].nodetype = NodeType.INTERNAL_NODE
    nodes[id].left = c[0]
    for j in range(k-1):
        nodes[c[j]].right = c[j+1]
        nodes[c[j]].parent = id
    nodes[c[k-1]].parent = id

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

# 深さの探索
# h < 20 なので再帰的にたどっても良い
def rec(u, d):
    nodes[u].depth = d
    if nodes[u].right != None: rec(nodes[u].right, d)
    if nodes[u].left != None: rec(nodes[u].left, d+1)

rec(root, 0)

for i in range(n):
    if nodes[i].nodetype == NodeType.LEAF:
        print('node %d: parent = %d, depth = %d, leaf, []'%(i, nodes[i].parent, nodes[i].depth))

    c = nodes[i].left
    child_list = []
    while c != None:
        child_list.append(c)
        c = nodes[c].right

    if nodes[i].nodetype == NodeType.ROOT:
        print('node %d: parent = -1, depth = 0, root,'%(i), child_list)
    elif nodes[i].nodetype == NodeType.INTERNAL_NODE:
        print('node %d: parent = %d, depth = %d, internal node,'%(i, nodes[i].parent, nodes[i].depth), child_list)

Submission status: Runtime Error

Solution code:
from enum import Enum, auto
import sys

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

class Node():
    def __init__(self, parent=None, left=None, right=None, depth=None, nodetype=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.nodetype = nodetype

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

# 再帰上限の変更
sys.setrecursionlimit(n)

for i in range(n):
    arr = list(map(int, input().split(' ')))
    if arr[1] == 0:
        nodes[arr[0]].nodetype = NodeType.LEAF
        continue
    id, k, c = arr[0], arr[1], arr[2:]
    nodes[id].nodetype = NodeType.INTERNAL_NODE
    nodes[id].left = c[0]
    for j in range(k-1):
        nodes[c[j]].right = c[j+1]
        nodes[c[j]].parent = id
    nodes[c[k-1]].parent = id

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

# 深さの探索
# h < 20 なので再帰的にたどっても良い
def rec(u, d):
    nodes[u].depth = d
    if nodes[u].right != None: rec(nodes[u].right, d)
    if nodes[u].left != None: rec(nodes[u].left, d+1)

rec(root, 0)

for i in range(n):
    if nodes[i].nodetype == NodeType.LEAF:
        print('node %d: parent = %d, depth = %d, leaf, []'%(i, nodes[i].parent, nodes[i].depth))

    c = nodes[i].left
    child_list = []
    while c != None:
        child_list.append(c)
        c = nodes[c].right

    if nodes[i].nodetype == NodeType.ROOT:
        print('node %d: parent = -1, depth = 0, root,'%(i), child_list)
    elif nodes[i].nodetype == NodeType.INTERNAL_NODE:
        print('node %d: parent = %d, depth = %d, internal node,'%(i, nodes[i].parent, nodes[i].depth), child_list)

Submission status: Runtime Error

Solution code:
from enum import Enum, auto
import sys

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

class Node():
    def __init__(self, parent=None, left=None, right=None, depth=None, nodetype=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.nodetype = nodetype

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

# 再帰上限の変更
sys.setrecursionlimit(100000)

for i in range(n):
    arr = list(map(int, input().split(' ')))
    if arr[1] == 0:
        nodes[arr[0]].nodetype = NodeType.LEAF
        continue
    id, k, c = arr[0], arr[1], arr[2:]
    nodes[id].nodetype = NodeType.INTERNAL_NODE
    nodes[id].left = c[0]
    for j in range(k-1):
        nodes[c[j]].right = c[j+1]
        nodes[c[j]].parent = id
    nodes[c[k-1]].parent = id

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

# 深さの探索
# h < 20 なので再帰的にたどっても良い
def rec(u, d):
    nodes[u].depth = d
    if nodes[u].right != None: rec(nodes[u].right, d)
    if nodes[u].left != None: rec(nodes[u].left, d+1)

rec(root, 0)

for i in range(n):
    if nodes[i].nodetype == NodeType.LEAF:
        print('node %d: parent = %d, depth = %d, leaf, []'%(i, nodes[i].parent, nodes[i].depth))

    c = nodes[i].left
    child_list = []
    while c != None:
        child_list.append(c)
        c = nodes[c].right

    if nodes[i].nodetype == NodeType.ROOT:
        print('node %d: parent = -1, depth = 0, root,'%(i), child_list)
    elif nodes[i].nodetype == NodeType.INTERNAL_NODE:
        print('node %d: parent = %d, depth = %d, internal node,'%(i, nodes[i].parent, nodes[i].depth), child_list)

Submission status: Runtime Error

Solution code:
from enum import Enum, auto
import sys

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

class Node():
    def __init__(self, parent=None, left=None, right=None, depth=None, nodetype=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.nodetype = nodetype

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

sys.setrecursionlimit(100000)

for i in range(n):
    arr = list(map(int, input().split(' ')))
    if arr[1] == 0:
        nodes[arr[0]].nodetype = NodeType.LEAF
        continue
    id, k, c = arr[0], arr[1], arr[2:]
    nodes[id].nodetype = NodeType.INTERNAL_NODE
    nodes[id].left = c[0]
    for j in range(k-1):
        nodes[c[j]].right = c[j+1]
        nodes[c[j]].parent = id
    nodes[c[k-1]].parent = id

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

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

rec(root, 0)

for i in range(n):
    if nodes[i].nodetype == NodeType.LEAF:
        print('node %d: parent = %d, depth = %d, leaf, []'%(i, nodes[i].parent, nodes[i].depth))

    c = nodes[i].left
    child_list = []
    while c != None:
        child_list.append(c)
        c = nodes[c].right

    if nodes[i].nodetype == NodeType.ROOT:
        print('node %d: parent = -1, depth = 0, root,'%(i), child_list)
    elif nodes[i].nodetype == NodeType.INTERNAL_NODE:
        print('node %d: parent = %d, depth = %d, internal node,'%(i, nodes[i].parent, nodes[i].depth), child_list)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

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

n = int(input())
nodes = [Node() for i in range(n)]
for i in range(n):
    id, k, *c = list(map(int, input().split(' ')))
    if k == 0: continue
    nodes[id].left = c[0]
    nodes[c[0]].parent = id
    for j in range(1, k):
        nodes[c[j-1]].right = c[j]
        nodes[c[j]].parent = id

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

def get_childs(i):
    if nodes[i].left == None: return []
    j = 0
    childs = [nodes[i].left]
    while nodes[childs[j]].right != None:
        childs.append(nodes[childs[j]].right)
        j += 1
    return childs

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

set_depth(root, 0)

for i in range(n):
    nodetype = 'internal node'
    childs = get_childs(i)
    if childs == []:
        nodetype = 'leaf'
    parent = nodes[i].parent
    if parent == None:
        parent = -1
        nodetype = 'root'
    print('node ' + str(i) + ': parent = ' + str(parent) + ', depth = ' + str(nodes[i].depth) + ', ' + nodetype + ', ' + str(childs))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May 19 19:34:44 2018
ALDS1_7_A
@author: maezawa
"""

n = int(input())

parent =[]
left = []
right = [None for _ in range(n)]
child = [[] for _ in range(n)]
depth = [None for _ in range(n)]

def get_parent(i):
    for j in range(n):
        if i in child[j]:
            return j
    return -1

def get_left(i):
    if len(child[i]) == 0:
        return None
    return child[i][0]

def set_right():
    global right
    for j in range(n):
        for i, k in enumerate(child[j]):
            #if len(child[j]) > i+1:
            try:
                right[k] = child[j][i+1]
            except:
                continue


#def get_right(i):
#    j = parent[i]
#    try:
#        ind = child[j].index(i)
#    except:
#        return None
#    if len(child[j]) > ind+1:
#        return child[j][ind+1]
#    else:
#        return None
    
def set_depth(i, p):
    global depth
    if depth[i] != None:
        return
    depth[i] = p
    if right[i] != None:
        set_depth(right[i], p)
    if left[i] != None:
        set_depth(left[i], p+1)
       
def get_depth(i):
    global depth
    if depth[i] != None:
        return depth[i]
    d = 0
    u = i
    while parent[u] != -1:
        u = parent[u]
        d += 1
    depth[i] = d
    return d

    
for i in range(n):
    line = list(map(int, input().split()))
    child[line[0]] = [line[i+2] for i in range(line[1])]

for i in range(n):
    parent.append(get_parent(i))
    left.append(get_left(i))
    get_depth(i)
set_right()
    
for i in range(n):
    out_str = 'node {}: parent = {}, depth = {}, '.format(i,parent[i],depth[i])
    if parent[i] == -1:
        out_str += 'root, '
    elif len(child[i]) == 0:
        out_str += 'leaf, '
    else:
        out_str += 'internal node, '
    out_str += str(child[i])
    print(out_str)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May 19 19:34:44 2018
ALDS1_7_A
@author: maezawa
"""

n = int(input())

parent =[]
left = []
right = [None for _ in range(n)]
child = [[] for _ in range(n)]
depth = [None for _ in range(n)]

def get_parent(i):
    for j in range(n):
        if i in child[j]:
            return j
    return -1

def get_left(i):
    if len(child[i]) == 0:
        return None
    return child[i][0]

def set_right():
    global right
    for j in range(n):
        for i, k in enumerate(child[j]):
            #if len(child[j]) > i+1:
            try:
                right[k] = child[j][i+1]
            except:
                continue


#def get_right(i):
#    j = parent[i]
#    try:
#        ind = child[j].index(i)
#    except:
#        return None
#    if len(child[j]) > ind+1:
#        return child[j][ind+1]
#    else:
#        return None
    
def set_depth(i, p):
    global depth
    if depth[i] != None:
        return
    depth[i] = p
    if right[i] != None:
        set_depth(right[i], p)
    if left[i] != None:
        set_depth(left[i], p+1)
       
def get_depth(i):
    global depth
    if depth[i] != None:
        return depth[i]
    d = 0
    u = i
    while parent[u] != -1:
        u = parent[u]
        d += 1
    depth[i] = d
    return d

    
for i in range(n):
    line = list(map(int, input().split()))
    child[line[0]] = [line[i+2] for i in range(line[1])]

for i in range(n):
    parent.append(get_parent(i))
    left.append(get_left(i))
    get_depth(i)
set_right()
    
for i in range(n):
    out_str = 'node {}: parent = {}, depth = {}, '.format(i,parent[i],get_depth(i))
    if parent[i] == -1:
        out_str += 'root, '
    elif len(child[i]) == 0:
        out_str += 'leaf, '
    else:
        out_str += 'internal node, '
    out_str += str(child[i])
    print(out_str)

Submission status: Runtime Error

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


n = int(input())
rooted_tree = [Node() for i in range(n)]
d = [0 for k in range(n)]


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


def print_child(u):
    cur = rooted_tree[u].left
    child_lst = []
    while cur != -1:
        child_lst.append(cur)
        cur = rooted_tree[cur].right

    return child_lst


def print_tree(u):
    if rooted_tree[u].parent == -1:
        t = "root"
    elif rooted_tree[u].left == -1:
        t = "leaf"
    else:
        t = "internal node"

    print("node {}: parent = {}, depth = {}, {}, {}".
          format(u, rooted_tree[u].parent, d[u], t, print_child(u)))


def main():
    # 根付き木の構築
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(data[1]):
            rooted_tree[data[2+j]].parent = data[0]
            if rooted_tree[data[0]].left == -1:
                rooted_tree[data[0]].left = data[2+j]
            if j != data[1] - 1:
                rooted_tree[data[2+j]].right = data[3+j]

    # 根の探索
    root_idx = 0
    for i in range(n):
        if rooted_tree[i].parent == -1:
            root_idx = i

    # 深さの探索
    set_depth(root_idx, 0)

    # 木の出力
    for i in range(n):
        print_tree(i)


if __name__ == '__main__':
    main()