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


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 = [int(j) for j in sys.stdin.readline().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()

Submission status: Runtime Error

Solution code:
class Tree:
    def __init__(self, ary):
        self.nodes = [Node(node, self) for node in ary]
        [node.set() for node in self.nodes]
        for node in self.nodes:
            if node.parent == -1:
                node.set_depth(0)
                break

    def output(self):
        [node.output() for node in sorted(self.nodes, key=lambda x: x.no)]


class Node:
    def __init__(self, node, tree):
        self.tree = tree
        self.no = node[0]
        self.parent = -1
        self.right = False
        self.left = False
        self.children = node[2:]

    def set(self):
        if self.children:
            for i, child in enumerate(self.children):
                self.tree.nodes[child].parent = self.no
                if i < len(self.children) - 1:
                    self.tree.nodes[child].right = self.children[i + 1]
                self.left = self.children[0]

    def set_depth(self, d):
        self.depth = d
        if self.right:
            self.tree.nodes[self.right].set_depth(d)
        if self.left:
            self.tree.nodes[self.left].set_depth(d + 1)

    def output(self):
        if self.parent == -1:
            kind = 'root'
        elif not self.children:
            kind = 'leaf'
        else:
            kind = 'internal node'

        print('node {}: parent = {}, depth = {}, {}, {}'.format(
            self.no, self.parent, self.depth, kind, self.children))


if __name__ == '__main__':
    import sys

    n = int(input())
    ary = [[int(_) for _ in line.strip().split()] for line in sys.stdin]
    # ary = [[int(_) for _ in input().split()] for i in range(n)]
    tree = Tree(ary)
    tree.output()

    # ary.sort(key=lambda x: x[0])
    # bry = [{
    #     'id': i,
    #     'parent': -1,
    #     'depth': 0,
    #     'type': 'root',
    #     'children': []
    # } for i in range(n)]
    # for node in ary:
    #     no = node[0]
    #     if node[1]:
    #         for cno in node[2:]:
    #             bry[no]['children'].append(cno)
    #             bry[cno]['parent'] = no
    #             if ary[cno][1]:
    #                 bry[cno]['type'] = 'internal node'
    #             else:
    #                 bry[cno]['type'] = 'leaf'
    #     else:
    #         if n > 1:
    #             bry[no]['type'] = 'leaf'

    # tmp = [(node['id'], node['parent']) for node in bry]
    # root = [min(tmp, key=lambda x: x[1])[0]]
    # flag = True
    # while flag:
    #     flag = False
    #     tmp = []
    #     for i in root:
    #         for cno in bry[i]['children']:
    #             bry[cno]['depth'] = bry[i]['depth'] + 1
    #             tmp.append(cno)
    #             flag = True
    #     root = tmp

    # for node in bry:
    #     output(node['id'], node['parent'], node['depth'], node['type'],
    #            node['children'])

Submission status: Runtime Error

Solution code:
class Tree:
    def __init__(self, ary):
        self.nodes = [Node(node, self) for node in ary]
        [node.set() for node in self.nodes]
        for node in self.nodes:
            if node.parent == -1:
                node.set_depth(0)
                break

    def output(self):
        [node.output() for node in sorted(self.nodes, key=lambda x: x.no)]


class Node:
    def __init__(self, node, tree):
        self.tree = tree
        self.no = node[0]
        self.parent = -1
        self.right = False
        self.left = False
        self.children = node[2:]

    def set(self):
        if self.children:
            for i, child in enumerate(self.children):
                self.tree.nodes[child].parent = self.no
                if i < len(self.children) - 1:
                    self.tree.nodes[child].right = self.children[i + 1]
                self.left = self.children[0]

    def set_depth(self, d):
        self.depth = d
        if type(self.right) != bool:
            self.tree.nodes[self.right].set_depth(d)
        if type(self.left) != bool:
            self.tree.nodes[self.left].set_depth(d + 1)

    def output(self):
        if self.parent == -1:
            kind = 'root'
        elif not self.children:
            kind = 'leaf'
        else:
            kind = 'internal node'

        print('node {}: parent = {}, depth = {}, {}, {}'.format(
            self.no, self.parent, self.depth, kind, self.children))


if __name__ == '__main__':
    import sys

    n = int(input())
    ary = [[int(_) for _ in line.strip().split()] for line in sys.stdin]
    # ary = [[int(_) for _ in input().split()] for i in range(n)]
    tree = Tree(ary)
    tree.output()

    # ary.sort(key=lambda x: x[0])
    # bry = [{
    #     'id': i,
    #     'parent': -1,
    #     'depth': 0,
    #     'type': 'root',
    #     'children': []
    # } for i in range(n)]
    # for node in ary:
    #     no = node[0]
    #     if node[1]:
    #         for cno in node[2:]:
    #             bry[no]['children'].append(cno)
    #             bry[cno]['parent'] = no
    #             if ary[cno][1]:
    #                 bry[cno]['type'] = 'internal node'
    #             else:
    #                 bry[cno]['type'] = 'leaf'
    #     else:
    #         if n > 1:
    #             bry[no]['type'] = 'leaf'

    # tmp = [(node['id'], node['parent']) for node in bry]
    # root = [min(tmp, key=lambda x: x[1])[0]]
    # flag = True
    # while flag:
    #     flag = False
    #     tmp = []
    #     for i in root:
    #         for cno in bry[i]['children']:
    #             bry[cno]['depth'] = bry[i]['depth'] + 1
    #             tmp.append(cno)
    #             flag = True
    #     root = tmp

    # for node in bry:
    #     output(node['id'], node['parent'], node['depth'], node['type'],
    #            node['children'])

Submission status: Runtime Error

Solution code:
class Tree:
    def __init__(self, ary):
        self.nodes = [
            Node(node, self) for node in sorted(ary, key=lambda x: x[0])
        ]
        [node.set() for node in self.nodes]
        for node in self.nodes:
            if node.parent == -1:
                node.set_depth(0)
                break

    def output(self):
        [node.output() for node in self.nodes]


class Node:
    def __init__(self, node, tree):
        self.tree = tree
        self.no = node[0]
        self.parent = -1
        self.right = False
        self.left = False
        self.children = node[2:]

    def set(self):
        if self.children:
            for i, child in enumerate(self.children):
                self.tree.nodes[child].parent = self.no
                if i < len(self.children) - 1:
                    self.tree.nodes[child].right = self.children[i + 1]
                self.left = self.children[0]

    def set_depth(self, d):
        self.depth = d
        if type(self.right) != bool:
            self.tree.nodes[self.right].set_depth(d)
        if type(self.left) != bool:
            self.tree.nodes[self.left].set_depth(d + 1)

    def output(self):
        if self.parent == -1:
            kind = 'root'
        elif not self.children:
            kind = 'leaf'
        else:
            kind = 'internal node'

        print('node {}: parent = {}, depth = {}, {}, {}'.format(
            self.no, self.parent, self.depth, kind, self.children))


if __name__ == '__main__':
    import sys

    n = int(input())
    ary = [[int(_) for _ in line.strip().split()] for line in sys.stdin]
    # ary = [[int(_) for _ in input().split()] for i in range(n)]
    tree = Tree(ary)
    tree.output()

Submission status: Runtime Error

Solution code:
#coding:utf-8

n = int(input())
T = [list(map(int, input().split())) for i in range(n)]
A = []
def parentSearch():
    numList = []
    for t in T:
        if t[1] != 0:
            for num in t[2:]:
                numList.append(num)
    numList.sort()
    for i in range(n-1):
        if numList[i] != i:
            return i
            break


def rootedTrees(node, parent, depth):
    t = T[node]
    if t[1] != 0:
        if parent == -1:
            kind = "root"
        else:
            kind = "internal node"
        A.append([t[0], parent, depth, kind, t[2:]])
        parent = node
        for i in t[2:]:
            rootedTrees(i, parent, depth+1)
    else:
        A.append([t[0], parent, depth, "leaf", []])


def Merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append([510000])
    R.append([510000])
    i,j = 0,0
    for k in range(left,right):
        if L[i][0] <= R[j][0]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def MergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right)//2
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)

node = parentSearch()
depth = 0
parent = -1
rootedTrees(node, parent, depth)
MergeSort(A, 0, n)

for t in A:
    print("node {}: parent = {}, depth = {}, {}, {}".format(t[0],t[1],t[2],t[3],t[4]))

Submission status: Runtime Error

Solution code:
#coding:utf-8

n = int(input())
T = [list(map(int, input().split())) for i in range(n)]
A = []
def parentSearch():
    numList = []
    for t in T:
        if t[1] != 0:
            for num in t[2:]:
                numList.append(num)
    numList.sort()
    for i in range(n-1):
        if numList[i] != i:
            return i
            break


def rootedTrees(node, parent, depth):
    t = T[node]
    if t[1] != 0:
        if parent == -1:
            kind = "root"
        else:
            kind = "internal node"
        A.append([t[0], parent, depth, kind, t[2:]])
        parent = node
        for i in t[2:]:
            rootedTrees(i, parent, depth+1)
    else:
        if parent == -1:
            kind = "root"
        else:
            kind = "leaf"
        A.append([t[0], parent, depth, kind, []])


def Merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append([510000])
    R.append([510000])
    i,j = 0,0
    for k in range(left,right):
        if L[i][0] <= R[j][0]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def MergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right)//2
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)

node = parentSearch()
if node == None:
    node = 0
depth = 0
parent = -1
rootedTrees(node, parent, depth)
MergeSort(A, 0, n)

for t in A:
    print("node {}: parent = {}, depth = {}, {}, {}".format(t[0],t[1],t[2],t[3],t[4]))

Submission status: Runtime Error

Solution code:
from typing import List

class Node:
    def __init__(self, node_id, parent_id):
        self.node_id = node_id
        self.parent_id = parent_id
        self.children = []
        
        self.depth = None
        self.node_type =None

    def __str__(self):
        return str(self.node_id)
    def __repr__(self):
        return self.__str__()
        
    
class Tree:
    def __init__(self, n):
        self.root = None
        self.n_node = n
        self.node_list = [None for _ in range(n)]
    
    def find_node(self, node_id: int):
        if self.node_list[node_id] != None:
            return self.node_list[node_id]
        return None
    
    def add_children_from_ids(self, node_id: int, children_ids: List[int]):
        # check parent already exists
        parent_node = self.find_node(node_id)
        if parent_node == None:
            # create new node from parent_id
            parent_node = Node(node_id = node_id, parent_id = -1)
            self.node_list[node_id] = parent_node
            
        if len(children_ids) > 0:
            # add all the children (unregistered)
            # register parent_id, node_id, children
            for child_id in children_ids:
                child_node = self.find_node(child_id)
                
                if child_node == None:
                    child_node = Node(node_id = child_id, parent_id = node_id)
                else:
                    child_node.parent.parent_id = node_id
                    
                parent_node.children.append(child_node)
                self.node_list[child_id] = child_node
    
    def overwrite_node_type(self):
        # find root and overwrite node type
        
        for node in self.node_list:
            # root, internal node, leaf
            if node.parent_id == -1:
                node_type = "root"
                self.root = node
            else:
                if node.children != []:
                    node_type = "internal node"
                else:
                    node_type = "leaf"
                    
            node.node_type = node_type

    def overwrite_depth(self, node, depth):
        if node.children == []:
            node.depth = depth
            # print("node.id: ", node.node_id, ",  node.depth: ", node.depth)
            return None
        else:
            for child_node in node.children:
                self.overwrite_depth(child_node, depth+1)
        return None

    def print_nodes(self):
        for node in self.node_list:
            print("node {}: parent = {}, depth = {}, {}, {}".format(
                node.node_id, node.parent_id, node.depth, node.node_type, node.children
            ))            
  
def main():
    n = int(input())
    tree = Tree(n)
    for _ in range(n):
        node_id, k, *children = map(int, input().split())
        tree.add_children_from_ids(node_id = node_id, children_ids = children)
    tree.overwrite_node_type()

    tree.overwrite_depth(tree.root, 0)
    tree.print_nodes()    
main()

Submission status: WA: Presentation Error

Solution code:
n = int(input())
rt = {}
clist = [0 for i in range(n)]
for i in range(n):
    id, k, *c = list(map(int, input().split()))
    for j in c:
        rt[j] = id
    clist[id] = c
for i in range(n):
    print("node %d: parent = "%i, end = "")
    p = [i]
    while 1:
        try:
            p.append(rt[p[-1]])
        except:
            break
    if len(p) == 1:
        print("-1, depth = 0, root, ",clist[i])
    else:
        print("%d, depth ="%p[1] ,len(p) - 1, end = "")
        if clist[i] == []:
            print(", leaf, []")
        else:
            print(", internal node, ",clist[i])

Submission status: WA: Presentation Error

Solution code:
n = int(input())
child = {}
parent = {}

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

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

    
def dfs(s):
    for i in child[s]:
            depth[i]=depth[s]+1
            dfs(i)
    
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]}, depth = {depth[i]}, {node_type}, {child[i]}')

Submission status: WA: Presentation Error

Solution code:
class Tree():
    def __init__(self):
        self.nodes = {}
    def add_node(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)        
    def add_child(self, parent_id, child_id):
        self.add_node(parent_id)
        self.add_node(child_id)
        self.nodes[parent_id].add_child(self.nodes[child_id])
    
class Node():
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.children = []
        self.depth = 0
        self.nodetype = 'root'

    def add_child(self, child):
        self.children.append(child)
        child.parent = self
        child.update_depth()
        child.update_nodetype()
        self.update_nodetype()
        if self.parent:
            self.parent.update_nodetype()
            
    def update_depth(self):
        depth = self.depth
        if self.parent:
            self.depth = self.parent.depth + 1
        if depth != self.depth:
            for child in self.children:
                child.update_depth()
                
    def update_nodetype(self):
        if self.parent:
            if len(self.children):
                self.nodetype = 'internal node'
            else:
                self.nodetype = 'leaf'
        else:
            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 = Tree()

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

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

Submission status: WA: Presentation Error

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


def dfs(v, d=0):
    G[v].depth = d
    for child in G[v].children:
        dfs(child, d+1)


N = int(input())
G = [Node() for _ in range(N)]
for _ in range(N):
    idx, k, *children = [int(x) for x in input().split()]
    G[idx].children = children
    if k:
        G[idx].type = 'internal node'
    else:
        G[idx].type = 'leaf'
    for child in children:
        G[child].parent = idx
root = [i for i, x in enumerate(G) if x.parent == -1][0]
G[root].type = 'root'
dfs(root)
for i, node in enumerate(G):
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(i, node.parent, node.depth, node.type, ','.join(map(str, node.children))))

Submission status: WA: Presentation Error

Solution code:
NIL = -1

class Node:
    parent = NIL
    left = NIL
    right = NIL

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

for i in range(n):
    tmp = list(map(int, input().split()))
    id = tmp.pop(0)
    k = tmp.pop(0)
    c = tmp
    if k != 0:
        for j in c:
            t[j].parent = id
        t[id].left = c[0]
        for j in range(len(c)-1):
            t[c[j]].right = c[j+1]

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

def getchildren(u):
    c = t[u].left
    result = []
    while c != NIL:
        result.append(c)
        c = t[c].right
    return result

for i in range(n):
    d = getdepth(i)
    c = getchildren(i)
    if d == 0:
        v = "root"
    elif c == []:
        v = "leaf"
    else:
        v = "internal node"
    print("node ", i, ": ", "parent = ", t[i].parent, ", depth = ", d, ", ", v, ", ", c)

Submission status: WA: Presentation 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 = []
child =[[] 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 get_right(i):
    for j in range(n):
        if i in child[j]:
           ind = child[j].index(i)
           if len(child[j]) > ind+1:
               return child[j][ind+1]
           else:
               return None
           
def get_depth(i):
    d = 0
    u = i
    while parent[u] != -1:
        u = parent[u]
        d += 1
    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))
    right.append(get_right(i))
    
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)