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. 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  c 1  c 2 ... c k  where id is the node ID of u , k is the degree of u , c 1 ... c k are node IDs of 1st, ... k th 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 , [ c 1 ... c k ]   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 .  c 1 ... c k 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  Reference Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

Solution (Python):
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(self):
        print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(self.id,self.parent,self.depth,self.type,self.children))
  
  
def set_node(node_data):
    L = list(map(int, node_data.split()))
    num = L[0]
    children = L[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())
  
T = [None] * n
  
T.append(int(n * (n - 1) / 2))
  
for i in range(n):
    x = input()
    set_node(x)
  
set_pdt(T[-1], -1, 0)
  
T[T[-1]].type ='root'
  
for n in T[:-1]:
    n.show()

Solution (Python):


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

n = int(input())
data = [list(map(int, input().split())) for x in range(n)]
node_list = [None for i in range(n)]

for data_row in data:
    idx, degree, *children = data_row
    node = Node(idx, degree, children)
    node_list[idx] = node


for node in node_list:
    i = node.id
    if node.children:
        node.type = "internal node"
        for child in node.children:
            node_list[child].parent = i
    else:
        node.type = "leaf"


for i, node in enumerate(node_list):
    depth = 0
    parent = node.parent
    
    if parent == -1:
        node.type = "root"
    while parent != -1:
        parent = node_list[parent].parent
        depth += 1
    node.depth = depth

for node in node_list:
    print("node {}: parent = {}, depth = {}, {}, {}".format(node.id, node.parent, node.depth, node.type, node.children))

Solution (Python):
import sys


def dep(u, p):
    D[u] = p
    for i in tree[u][3]:
        dep(i, p+1)


def print_ans():
    for i in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}"
              .format(i, tree[i][0], D[i],
                      "root" if tree[i][0] == NIL else "leaf" if tree[i][1] == NIL else "internal node",
                      tree[i][3]))


if __name__ == "__main__":
    NIL = -1
    n = int(sys.stdin.readline())
    tree = [[NIL, NIL, NIL] for i in range(n)]
    D = [0 for i in range(n)]
    root = set(range(n))
    for a in sys.stdin.readlines():
        a = list(map(int, a.split()))
        tree[a[0]].append(a[2:])
        if a[1] > 0:
            tree[a[0]][1] = a[2]    
            for i in range(a[1]):
                tree[a[i+2]][0] = a[0] 
                if i != a[1] - 1:
                    tree[a[i+2]][2] = a[i+3] 
        root -= set(a[2:])
    dep(root.pop(), 0)
    print_ans()

Solution (Python):
def main():
    n = input()
    tree = MyTree(n)
    for i in range(n):
        id_k_cn = map(int,raw_input().split())
        id_node = id_k_cn.pop(0)
        k = id_k_cn.pop(0)
        tree.add(id_node,k,None,id_k_cn)
    
    tree.search_children()
    tree.set_depth(tree.nodes[tree.id_root],0)
    
    for node in tree.nodes:
        print "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(node.id_self, node.id_parent, node.depth, node.node_type, node.id_children)


class MyTree():
    def __init__(self,num_nodes):
        self.nodes = [MyNode() for i in range(num_nodes)]
        self.id_root = None

    def add(self,id_node,n_children,id_parent,id_children):
        self.nodes[id_node].id_self = id_node
        self.nodes[id_node].n_children = n_children
        self.nodes[id_node].id_parent = id_parent
        self.nodes[id_node].id_children = id_children
    
    def search_children(self):
        for node in self.nodes:
            if node.n_children == 0:
                node.node_type = "leaf"
            else:
                node.node_type = "internal node"
            for j in node.id_children:
                self.nodes[j].id_parent = node.id_self

        for node in self.nodes:
            if node.id_parent == None:
                node.id_parent = -1
                node.node_type = "root"
                self.id_root = node.id_self
                break

    def set_depth(self,node,depth):
        node.depth = depth
        node.id_children
        for item in node.id_children:
            self.set_depth(self.nodes[item],depth+1)


class MyNode():
    def __init__(self):
        self.id_self = None
        self.id_parent = None
        self.id_children = None
        self.depth = None
        self.node_type = None
        self.n_children = 0
        


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n = input()
    tree = MyTree(n)
    for i in range(n):
        id_k_cn = map(int,raw_input().split())
        id_node = id_k_cn.pop(0)
        k = id_k_cn.pop(0)
        tree.add(id_node,k,None,id_k_cn)
    
    tree.search_children()
    tree.set_depth(tree.nodes[tree.id_root],0)
    
    for node in tree.nodes:
        print "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(node.id_self, node.id_parent, node.depth, node.node_type, node.id_children)


class MyTree():
    def __init__(self,num_nodes):
        self.nodes = [MyNode() for i in range(num_nodes)]
        self.id_root = None

    def add(self,id_node,n_children,id_parent,id_children):
        node = self.nodes[id_node]
        node.id_self = id_node
        node.n_children = n_children
        node.id_parent = id_parent
        node.id_children = id_children
    
    def search_children(self):
        for node in self.nodes:
            if node.n_children == 0:
                node.node_type = "leaf"
            else:
                node.node_type = "internal node"
            for j in node.id_children:
                self.nodes[j].id_parent = node.id_self

        for node in self.nodes:
            if node.id_parent == None:
                node.id_parent = -1
                node.node_type = "root"
                self.id_root = node.id_self
                break

    def set_depth(self,node,depth):
        node.depth = depth
        node.id_children
        for item in node.id_children:
            self.set_depth(self.nodes[item],depth+1)


class MyNode():
    def __init__(self):
        self.id_self = None
        self.id_parent = None
        self.id_children = None
        self.depth = None
        self.node_type = None
        self.n_children = 0
        


if __name__ == "__main__":
    main()

Solution (Python):
import sys

I = 0
K = 1
C = 2
P = 3
D = 4

def setd(A, id, d):
    n = A[id]

    n[D] = d
    if n[K] > 0:
        for c in n[C]:
            setd(A, c, d + 1)

def setp(A, id, pid):
    n = A[id]

    if pid > -1:
        n[P] = pid
    if n[K] > 0:
        for c in n[C]:
            setp(A, c, n[I])

def getroot(A, id):
    if A[id][P] > -1:
        return getroot(A,A[id][P])
    return A[id][I]

def main():

    """ ????????? """
    num = int(input().strip())
    istr = sys.stdin.read()
    nlist = list(istr.splitlines())
    
    nodes = [[i,0,None,-1,0] for i in range(num)]

    for nstr in nlist:
        i = list(map(int,nstr.split()))
        id = i[0]
        n = nodes[id]

        if i[K] != 0:
            n[K] = i[K]
            n[C] = i[2:]
            setp(nodes, i[0], -1)

    r = getroot(nodes, 0)
    setd(nodes,r, 0)

    for id in range(num):
        n = nodes[id]

        type = "leaf"
        children = ""
        if n[K] > 0:
            type = "internal node"
            children = ", ".join(map(str,n[C]))
        if n[P] == -1:
            type = "root"
        print("node {0}: parent = {1}, depth = {2}, {3}, [{4}]".format(n[I], n[P], n[D], type, children))

if __name__ == '__main__':
    main()

Solution (Python):
class Node():
    def __init__(self, id, num, child, nodetype=None, depth=-1, parent=-1):
        self.id = id
        self.num = num
        self.child = child
        self.nodetype = nodetype
        self.depth = depth
        self.parent = parent
    def showFinal(self):
        print 'node %d: parent = %d, depth = %d, %s,' % (self.id, self.parent, self.depth, self.nodetype), self.child
        
def calcDepth(node):
    if node.parent == -1:
        return 0
    return calcDepth(tree[node.parent]) + 1

n = int(raw_input())
dict = {}
tree = []

for i in range(n):
    a = map(int, raw_input().split())
    if len(a) > 2:
        dict[a[0]] = Node(a[0], a[1], a[2:])
    else:
        dict[a[0]] = Node(a[0], a[1], [], nodetype='leaf')

for i in range(n):
    tree.append(dict[i])

for i in range(n):
    children = tree[i].child
    for j in children:
        tree[j].parent = tree[i].id

for i in range(n):
    tree[i].depth = calcDepth(tree[i])
    if tree[i].parent != -1 and tree[i].child != []:
        tree[i].nodetype = 'internal node'
    elif tree[i].parent == -1:
        tree[i].nodetype = 'root'
        
for i in range(n):
    tree[i].showFinal()

Solution (Python):
import sys

NIL = -1

def set_depth(v, depth):
    tree[v][2] = depth
    
    for child in tree[v][1]:
        set_depth(child, depth + 1)

N = int(input())
tree = [[NIL, [], 0, 'leaf'] for _ in range(N)]

for _ in range(N):
    line = [int(i) for i in sys.stdin.readline().split()]
    t_id = line[0]
    children = line[2:]
    tree[t_id][1] = children
    
    if children:
        tree[t_id][3] = 'internal node'
    
    for child in children:
        tree[child][0] = t_id
        
for t_id in range(N):
    if tree[t_id][0] == NIL:
        tree[t_id][3] = 'root'
        r = t_id
        break

set_depth(r, 0)

for t_id in range(N):
    parent = tree[t_id][0]
    depth = tree[t_id][2]
    children = tree[t_id][1]
    type_t = tree[t_id][3]
    
    print('node {}: parent = {}, depth = {}, {}, {}'.format(t_id, parent, depth, type_t, children))

Solution (Python):

N = int(input())
tree = {n:{} for n in range(N)}
children = set()

for n in range(N):
    inp = [int(m) for m in input().split()]
    tree[inp[0]]["leaf"] = inp[2:]
    children.update(inp[2:])

parent = set([n for n in range(N)]).difference(children).pop()
tree[parent]["depth"] = 0
tree[parent]["parent"] = -1

siblings = tree[parent]["leaf"]
for c in siblings:
    tree[c]["depth"] = 1
    tree[c]["parent"] = parent

depth = 2
while len(children):
    children = children.difference(siblings)
    next_gen = []
    for s in siblings:
        next_gen.extend(tree[s]["leaf"])
        for c in tree[s]["leaf"]:
            tree[c]["depth"] = depth
            tree[c]["parent"] = s
    siblings = next_gen
    depth += 1

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

Solution (Python):





N = int(input())
tree = {n:{"parent":-1, "left": -1, "right": -1} for n in range(N)} 
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):
    print(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)

def get_depth(n):
    d = 0
    while tree[n]["parent"] != -1:
        d += 1
        n = tree[n]["parent"]
    return d


        
for n in range(N):
    tree[n]["depth"] = get_depth(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"]))

Solution (Python):
def rootedtrees():
    def set_depth(node_id):
        if tree[node_id]['parent'] == -1:
            return 0
        else:
            return set_depth(tree[node_id]['parent']) + 1

    n = int(input())

    tree = [{'parent': -1, 'depth': 0, 'node_type': 'leaf', 'children': []}
            for i in range(n)]

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

        for child in children:
            tree[child]['parent'] = node_id

        if children:
            tree[node_id]['node_type'] = 'internal node'

        tree[node_id]['children'] = children

    for node_id in range(n):
        tree[node_id]['depth'] = set_depth(node_id)

        if tree[node_id]['parent'] == -1:
            tree[node_id]['node_type'] = 'root'

    for node_id in range(n):
        parent = tree[node_id]['parent']
        depth = tree[node_id]['depth']
        node_type = tree[node_id]['node_type']
        children = tree[node_id]['children']

        print('node {}: parent = {}, depth = {}, {}, {}'.format
            (node_id, parent, depth, node_type, children))

if __name__ == '__main__':
    rootedtrees()

Solution (Python):
N = int(input())
tree = [[-1, 0, []] for _ in [0]*N]

for _ in [0]*N:
    a = tuple(map(int, input().split()))
    v = a[0]
    n = a[1]
    children = list(a[2:])
    tree[v][2] = children
    for child in children:
        tree[child][0] = v

q = [a[2] for a in tree if a[0] == -1][0]
d = 1
while q:
    for v in q:
        tree[v][1] = d
    q = [n for v in q for n in tree[v][2]]
    d += 1

for i in range(N):
    v = tree[i]
    parent = v[0]
    depth = v[1]
    children = v[2]
    node_type = "root" if parent == -1 else "leaf" if len(children) == 0 else "internal node"
    print("node %d: parent = %d, depth = %d, %s, %s" % (i, parent, depth, node_type, str(children)))

Solution (Python):
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())

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)
    
for u in root:
    set_pdt(u, -1, 0)

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

Solution (Python):
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())
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.pop(), -1, 0)

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

Solution (Python):
def set_info(a, i, p, d):
    a[i][1], a[i][2] = p, d
    for b in a[i][0]:
        set_info(a, b, i, d + 1)

n = int(input())
tree = [[None] for i in range(n)]
root = set(range(n))

for i in range(n):
    l = list(map(int, input().split()))
    tree[l[0]] = [l[2:], None, None]
    root -= set(l[2:])

set_info(tree, root.pop(), -1, 0)

for i in range(n):
    c, p, d = tree[i]
    if p == -1:
        t = "root"
    elif len(c) == 0:
        t = "leaf"
    else:
        t = "internal node"
    print("node ", i, ": parent = ", p, ", depth = ", d, ", ", t, ", ", c, sep="")

Solution (Python):
def dfs(here, p, connect, depth, parent, d):
    parent[here] = p
    depth[here] = d
    for c in connect[here]:
        dfs(c, here, connect, depth, parent, d + 1)

from collections import defaultdict
v_num = int(input())
connect = defaultdict(list)
parent = [-1 for n in range(v_num)]
in_v = [0 for n in range(v_num)]
depth = [0 for n in range(v_num)]
for _ in range(v_num):
    inp = [int(n) for n in input().split(" ")]
    connect[inp[0]].extend(inp[2:])
    for c in inp[2:]:
        in_v[c] += 1
for i, n in enumerate(in_v):
    if not n:
        root = i
dfs(root, -1, connect, depth, parent, 0)
for v in range(v_num):
    if v == root:
        is_type = "root"
    elif len(connect[v]) == 0:
        is_type = "leaf"
    else:
        is_type = "internal node"
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(v, parent[v], depth[v], is_type, connect[v]))

Solution (Python):

import sys
from collections import OrderedDict


def cleate_node_dict(children):
    node_dict = OrderedDict()
    for val in children:
        node_dict[val] = OrderedDict()
    return node_dict


def cleate_tree(nodes):
    tree = nodes.copy()
    for node, children in nodes.items():
        for key in children.keys():
            children[key] = nodes[key]
            del tree[key]

    return tree


def rec(current, acc, parent=-1, depth=0):
    if current == {}:
        return
    for node, children in current.items():
        cld_lst = list(children.keys())
        acc[node] = "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(
                node, parent, depth, node_type(parent, children), cld_lst)
        rec(children, acc, node, depth+1)


def node_type(parent, children):
    if parent == -1:
        return "root"
    elif children != {}:
        return "internal node"
    else:
        return "leaf"


if __name__ == "__main__":
    n = int(input())
    lst = [[int(n) for n in val.split()] for val in sys.stdin.readlines()]
    nodes = {val[0]: cleate_node_dict(val[2:]) for val in lst}
    tree = cleate_tree(nodes)
    node_info = {}
    rec(tree, node_info)
    for key, val in sorted(node_info.items()):
        print(val)

Solution (Python):
class Node:
    def __init__(self, x, y):
        self.id = x
        self.k = y
        self.children = []
        self.type = ''
        self.depth = 20
        self.parent = '-1'

def findRoot(tree):
    for x in tree:
        for y in x.children:
            tree[int(y)].parent = x.id
            if tree[int(y)].k == 0:
                tree[int(y)].type = 'leaf'
            else:
                tree[int(y)].type = 'internal node'
            '''for a in tree:
                if y == a.id:
                    if a.k == 0:
                        a.type = 'leaf'
                    else:
                        a.type = 'internal node'
                    a.parent = x.id
            '''
    for i,x in enumerate( tree):
        if x.type == 'root':
            return i


def setd(tree,node,d):
    node.depth = d
    if node.k == 0:
        return
    else:
        for tmp in node.children:
            setd(tree,tree[int(tmp)],d+1)
            '''for x in tree:
                if x.id == tmp:
                    setd(tree,x,d+1)
            '''


if __name__ == '__main__':
    n = (int)(input())
    tree = [None]*n
    for i in range(0,n):
        tmp = input().split()
        a = Node(tmp[0],(int)(tmp[1]))
        a.children=tmp[2:]
        a.type = 'root'
        tree[int(a.id)] = a
    ri = findRoot(tree)
    setd(tree,tree[ri],0)
    
    for tmp in tree:
        print("node {}: parent = {}, depth = {}, {}, {}".format(tmp.id, tmp.parent,tmp.depth,tmp.type,list(map(int,tmp.children))))

Solution (Python):

import sys
from collections import OrderedDict


def cleate_node_dict(children):
    node_dict = OrderedDict()
    for val in children:
        node_dict[val] = None
    return node_dict


def cleate_tree(nodes):
    tree = nodes.copy()
    for node, children in nodes.items():
        for key in children.keys():
            children[key] = nodes[key]
            del tree[key]

    return tree


def rec(current, acc, parent=-1, depth=0):
    if current == {}:
        return
    for node, children in current.items():
        cld_lst = list(children.keys())
        acc[node] = "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(
                node, parent, depth, node_type(parent, children), cld_lst)
        rec(children, acc, node, depth+1)


def node_type(parent, children):
    if parent == -1:
        return "root"
    elif children != {}:
        return "internal node"
    else:
        return "leaf"


def rooted_trees(lst, n):
    nodes = {val[0]: cleate_node_dict(val[2:]) for val in lst}
    tree = cleate_tree(nodes)
    node_info = [None] * n
    rec(tree, node_info)
    print("\n".join(node_info))


if __name__ == "__main__":
    n = int(input())
    lst = [[int(n) for n in val.split()] for val in sys.stdin.readlines()]
    rooted_trees(lst, n)

Solution (Python):

import sys
sys.setrecursionlimit(200000)

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

Solution (Python):
class Tree:
    def __init__(self):
        self.id = 0
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.len_c = 0
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = [Tree() for _ in range(n)]
for _ in range(n):
    id, k, *c = map(int, input().split())
    if k == 0:
        c = []
    else:
        li[id].type = "internal node"
    li[id].id = id
    li[id].c = c
    for j in c:
        li[j].p = id
root = 0
while True:
    a = li[root].p
    if a == -1:
        li[root].type = "root"
        li[root].depth = 0
        break
    root = a
dp = [(root, 0)]
while dp:
    id, d = dp.pop()
    for i in li[id].c:
        li[i].depth = d + 1
        dp.append((i, d + 1))
for i in range(n):
    print(li[i])

Solution (Python):
import sys
readline = sys.stdin.readline
class Tree:
    def __init__(self):
        self.id = 0
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.len_c = 0
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = [Tree() for _ in range(n)]
for _ in range(n):
    id, k, *c = map(int, readline().split())
    if k == 0:
        c = []
    else:
        li[id].type = "internal node"
    li[id].id = id
    li[id].c = c
    for j in c:
        li[j].p = id
root = 0
while True:
    a = li[root].p
    if a == -1:
        li[root].type = "root"
        li[root].depth = 0
        break
    root = a
dp = [(root, 0)]
while dp:
    id, d = dp.pop()
    for i in li[id].c:
        li[i].depth = d + 1
        dp.append((i, d + 1))
for i in range(n):
    print(li[i])

Solution (Python):
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'depth', 'type', 'len_c', 'c']
    def __init__(self):
        self.id = 0
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.len_c = 0
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = [Tree() for _ in range(n)]
for _ in range(n):
    id, k, *c = map(int, readline().split())
    if k == 0:
        c = []
    else:
        li[id].type = "internal node"
    li[id].id = id
    li[id].c = c
    for j in c:
        li[j].p = id
root = 0
while True:
    a = li[root].p
    if a == -1:
        li[root].type = "root"
        li[root].depth = 0
        break
    root = a
dp = [(root, 0)]
while dp:
    id, d = dp.pop()
    for i in li[id].c:
        li[i].depth = d + 1
        dp.append((i, d + 1))
for i in range(n):
    print(li[i])

Solution (Python):
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'depth', 'type', 'c']
    def __init__(self):
        self.id = 0
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = [Tree() for _ in range(n)]
for _ in range(n):
    id, k, *c = map(int, readline().split())
    if k == 0:
        c = []
    else:
        li[id].type = "internal node"
    li[id].id = id
    li[id].c = c
    for j in c:
        li[j].p = id
root = 0
while True:
    a = li[root].p
    if a == -1:
        li[root].type = "root"
        li[root].depth = 0
        break
    root = a
dp = [(root, 0)]
while dp:
    id, d = dp.pop()
    d += 1
    for i in li[id].c:
        li[i].depth = d
        dp.append((i, d))
print(*li, sep="\n")

Solution (Python):
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'depth', 'type', 'c']
    def __init__(self):
        self.id = 0
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = tuple(Tree() for _ in range(n))
for _ in range(n):
    id, k, *c = map(int, readline().split())
    if k == 0:
        c = []
    else:
        li[id].type = "internal node"
    li[id].id = id
    li[id].c = c
    for j in c:
        li[j].p = id
root = 0
while True:
    a = li[root].p
    if a == -1:
        li[root].type = "root"
        li[root].depth = 0
        break
    root = a
dp = [(root, 0)]
while dp:
    id, d = dp.pop()
    d += 1
    for i in li[id].c:
        li[i].depth = d
        dp.append((i, d))
print(*li, sep="\n")

Solution (Python):
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'depth', 'type', 'c']
    def __init__(self, id):
        self.id = id
        self.p = -1
        self.depth = -1
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, depth = {self.depth}, {self.type}, {self.c}"
n = int(input())
li = tuple(Tree(i) for i in range(n))
for _ in range(n):
    id, k, *c = map(int, readline().split())
    if k != 0:
        li[id].type = "internal node"
        li[id].c = c
        for j in c:
            li[j].p = id
root = 0
while li[root].p != -1:
    root = li[root].p
li[root].type = "root"
li[root].depth = 0
def depth_check(id, d):
    d += 1
    for i in li[id].c:
        li[i].depth = d
        if li[i].type != "leaf":
            depth_check(i, d)
depth_check(root, 0)
print(*li, sep="\n")