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,parent, left, right):
        self.parent=parent
        self.left=left
        self.right=right


class tree:
    
    def __init__(self, list):
        
        self.root=None
        self.T=[]
        self.insert(list)

    
    def insert(self,list):
        nnodes=len(list)
        for i in range(nnodes):
            self.T.append(node(None, None, None))
        for i in range(nnodes):
            
            n=int(list[i][0])
            nch=list[i][1]
            for j in range(nch):
                chnode=list[i][2+j]
                
                self.T[chnode].parent=n
                if (j==0):
                    
                    self.T[n].left=chnode

                
                if (j < nch-1):
                    self.T[chnode].right=list[i][j+3]

    def getDepth(self, index):
        d=0
        u=index
        while self.T[u].parent !=None:
            u=self.T[u].parent
            d=d+1

        return d

    def getChildrens(self, index):
        ch=[]
        c=self.T[index].left
        ic=c
        while ic!=None:
            ch.append(ic)
            ic=self.T[ic].right

        return ch

    def printNode(self, index):
        print("parent="+str(self.T[index].parent)+",depth="+str(self.getDepth(index)) +\
              ",right="+str(self.T[index].right)+ ",left="+str(self.T[index].left))
        print(self.getChildrens(index))
        return

    def stringForAOJ(self,index):
        
        strs=""
        strs=strs+"node "+str(index)+":"

        
        if self.T[index].parent==None:
            strs=strs+" parent = -1,"
        else:
            strs = strs + " parent = "+str(self.T[index].parent)+","

        
        strs=strs+" depth = "+str(self.getDepth(index))+","

        
        if self.T[index].parent==None:
            strs=strs+" root,"
        elif self.T[index].left==None:
            strs = strs + " leaf,"
        else:
            strs = strs + " internal node,"

        
        strs=strs+" ["
        ch=self.getChildrens(index)
        for i in range(len(ch)):
            strs=strs+str(ch[i])
            if (i < len(ch)-1):
                strs=strs+", "

        strs=strs+"]"

        return strs





n=int(input())
dlist=[]
for i in range(n):
    dlist.append(list(map(int,(input().split()))))


t=tree(dlist)

for i in range(n):
    print(t.stringForAOJ(i))

Solution (Python):
class Node():
    def __init__(self, id, children):
        self.id = id
        self.children = children

N = int(raw_input())
nodes = {}
for _ in range(N):
    d = map(int, raw_input().split())
    id,k,cs = d[0],d[1],d[2:]
    nodes[id] = Node(id, cs)

roots = range(N)
for i in range(N):
    [roots.remove(j) for j in nodes[i].children]
    nodes[i].children = [nodes[j] for j in nodes[i].children]

data = []
def traverse(node, p, d):
    id = node.id
    cs = map(lambda x:x.id, node.children)
    if p == -1:
        t = "root"
    elif len(cs) == 0:
        t = "leaf"
    else:
        t = "internal node"
    s = "node {}: parent = {}, depth = {}, {}, {}".format(id,p,d,t,cs)
    data.append((id, s))
    
    for child in node.children:
        traverse(child, id, d+1)

root = roots[0]
traverse(nodes[root], -1, 0)
for _,s in sorted(data, key=lambda x:x[0]):
    print s

Solution (Python):
n=int(input())

C=[[] for i in range(n+1)]
P=[-1 for i in range(n+1)]
D=[0 for i in range(n+1)]
T=["" for i in range(n+1)]

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

for i in range(n):
    if len(C[i])>0:
        for nodes in C[i]:
            P[nodes]=i

for i in range(n):
    d=0
    v=i
    while P[v]!=-1:
        v=P[v]
        d+=1
    D[i]=d
    if d==0:
        T[i]="root"
    elif len(C[i])>0:
        T[i]= "internal node"
    else:
        T[i]="leaf"
for i in range(n):
    print(f"node {i}: parent = {P[i]}, depth = {D[i]}, {T[i]}, [",end="")
    if len(C[i])>0:
        str_i=", ".join((map(str,C[i])))
        print(str_i,end="")
    print("]")

Solution (Python):


NULL = -1

class Node():
    def __init__(self):
        self.parent =  NULL 
        self.left = NULL    
        self.right = NULL   
        self.depth = NULL   
        self.type = ""      

def set_depth(T: list, r: int, d: int):
    T[r].depth = d
    if T[r].left != NULL:
        set_depth(T, T[r].left, d + 1)

    if T[r].right != NULL:
        set_depth(T, T[r].right, d)

n = int(input())

T = []
for i in range(n):
    T.append(Node())

cur = 0
for i in range(n):
    nodeinfo = [int(x) for x in input().split()]
    for j in range(nodeinfo[1]):
        if j == 0:
            T[nodeinfo[0]].left = nodeinfo[2+j]
        else:
            T[cur].right = nodeinfo[2+j]
        cur = nodeinfo[2+j]
        T[cur].parent = nodeinfo[0]


root = 0
for i, v in enumerate(T):
    if v.parent == NULL:
        root = i
        break





for v in T:
    if v.parent == NULL:
        v.type = "root"
    elif v.left == NULL:
        v.type = "leaf"
    else:
        v.type = "internal node"

for i, v in enumerate(T):
    childlen = []
    if T[i].left != NULL:
        child = T[i].left
        childlen.append(str(child))

        while T[child].right != NULL:
            child = T[child].right
            childlen.append(str(child))

    depth = 0
    cur = i
    while T[cur].parent != NULL:
        depth += 1
        cur = T[cur].parent
            
    print("node {}: parent = {}, depth = {}, {}, {}".format(i, v.parent, depth, v.type, "[" + ", ".join(childlen) + "]"))

Solution (Python):
class Node:
    '''
    p: parent node
    l: child node
    r: sibling node
    '''
    def __init__(self, p=-1, l=-1, r=-1):
        self._p = p
        self._l = l
        self._r = r

Depth = []
T = []

def rec(node, depth):
    global Depth
    global T
    Depth[node] = depth

    child = T[node]._l
    while child != -1:
        rec(child, depth + 1)
        child = T[child]._r


    
    

    
    

def print_node(index):
    global Depth
    global T
    print('node %d: parent = %d, depth = %d, '%(index, T[index]._p, Depth[index]), end='')

    if T[index]._p == -1:
        print('root, [', end='')
    elif T[index]._l == -1:
        print('leaf, [', end='')
    else:
        print('internal node, [', end='')

    i = 0
    node = T[index]._l
    while node != -1:
        if i:
            print(', ', end='')
        print(node, end='')

        i += 1
        node = T[node]._r
    print(']')
    


if __name__ == '__main__':
    n = int(input())

    for i in range(n):
        T.append(Node())
    Depth = [-1]*n
    for i in range(n):
        parent_node, child_cnt, *child_node = map(int, input().split())
        for j in range(child_cnt):
            if j == 0:
                T[parent_node]._l = child_node[j]
            else:
                T[child_node[j - 1]]._r = child_node[j]
            T[child_node[j]]._p = parent_node

    root = 0
    for i in range(n):
        if T[i]._p == -1:
            root = i
            break
    
    rec(root, 0)

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

Solution (Python):
def compute_depth(node: int, depth: int) -> None:
    global trees
    trees[node][1] = depth
    for child in trees[node][3]:
        compute_depth(child, depth + 1)


if __name__ == "__main__":
    node_num = int(input())
    trees = {idx: [-1, 0, "", [0]] for idx in range(node_num)}  

    for _ in range(0, node_num):
        node, _, *children = map(lambda x: int(x), input().split())
        trees[node][3] = children
        for child in children:
            trees[child][0] = node  

    for node, values in sorted(trees.items(), key=lambda x: x[1][0]):
        parent = values[0]
        children = values[3]
        if -1 == parent:
            trees[node][2] = "root"
            compute_depth(node, 0)
        else:
            
            
            if [] == children:
                trees[node][2] = "leaf"
            else:
                trees[node][2] = "internal node"

    for node, values in trees.items():
        parent = values[0]
        depth = values[1]
        node_type = values[2]
        children = values[3]
        print(f"node {node}: parent = {parent}, depth = {depth}, {node_type}, {children}")

Solution (Python):

class Node_information():
    def __init__(self):
        self.id = -1
        self.parent = -1
        self.depth = 0
        self.type = ""
        self.child = list()

def get_tree_id_child_and_parent(tree_id, tree_k, tree_information, node_information):
    for j in range(tree_k):
        tree_information[tree_id].child.append(node_information[j+2])
        tree_information[node_information[j+2]].parent = tree_id

def get_tree_id_type(number_of_child):
    if number_of_child == 0:
        return "leaf"
    else:
        return "internal node"

def depth_search(tree_information, now_depth, now_id):
    tree_information[now_id].depth = now_depth
    for i in range(len(tree_information[now_id].child)):
        depth_search(tree_information, now_depth+1,tree_information[now_id].child[i])
    
def print_tree_information(tree_information, N):
    for i in range(N):
        print("node {}: parent = {}, depth = {}, {}, [".format(tree_information[i].id,tree_information[i].parent,tree_information[i].depth,tree_information[i].type),end="")
        for j in range(len(tree_information[i].child)):
            if j != len(tree_information[i].child) - 1:
                print("{},".format(tree_information[i].child[j]),end=" ")
            else: 
                print("{}".format(tree_information[i].child[j]),end="")
        print("]")


def main():
    N = int(input())
    tree_information = list()
    for i in range(N):
        tree_information.append(Node_information())
    for i in range(N):
        node_information = [int(i) for i in input().split()]
        tree_id = node_information[0]
        tree_k = node_information[1]
        tree_information[tree_id].id = node_information[0]
        get_tree_id_child_and_parent(tree_id, tree_k, tree_information, node_information)
        tree_information[tree_id].type = get_tree_id_type(len(tree_information[tree_id].child))
    for i in range(N):
        if tree_information[i].parent == -1:
            tree_information[i].type = "root"
            depth_search(tree_information,0,i)
    print_tree_information(tree_information, N)

if __name__ == "__main__":
    main()

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

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

def printChildren(u):
    c = Nodes[u].left
    output_list = []
    while c != -1:
        output_list.append(c)
        c = Nodes[c].right
    return output_list


def printNodes(u):
    output_str = "node " + str(u) + ": parent = " + str(Nodes[u].parent) + ", depth = " + str(getDepth(u))
    if -1 == Nodes[u].parent:
        output_str = output_str + ", root, "
    elif Nodes[u].left != -1:
        output_str = output_str + ", internal node, "
    else:
        output_str = output_str + ", leaf, "
    
    print(output_str, "[{}]".format(", ".join(map(str, printChildren(u)))), sep="")

Nodes = []
for i in range(100000):
    tmp_obj = Node()
    Nodes.append(tmp_obj)


n = int(input())


for tmp_count in range(n):
    input_val = list(map(int, input().split()))
    if 0 != input_val[1]:
        
        Nodes[input_val[0]].left = input_val[2]
        
        Nodes[input_val[2]].parent = input_val[0]
        
        for i in range(input_val[1] - 1):
            
            Nodes[input_val[i+2]].right = input_val[i+3]
            
            Nodes[input_val[i+3]].parent = input_val[0]

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

Solution (Python):
n = int(input())
nodes = [None] * n
rootIdx = None

class Node:
    parent = property
    node_type = property
    depth = property

    def __init__(self, ID, k, c):
        self.parent = -1
        self.ID = ID
        self.k = k
        self.c = c

    def print_self(self):
        print('node {}: parent = {}, depth = {}, {}, '.format(self.ID, self.parent, self.depth, self.node_type) + str(self.c))

def trace(node, depth):
    node.depth = depth
    if len(node.c) > 0:
        for i in range(len(node.c)):
            child = nodes[node.c[i]]

            trace(child, depth + 1)

for i in range(n):
    s = list(map(int, input().split()))
    ID = s[0]
    k = s[1]
    c = s[2:]
    node = Node(ID, k, c)
    nodes[ID] = node

    
    



for i in range(n):
    node = nodes[i]
    if len(node.c) > 0:
        for i in range(len(node.c)):
            child = nodes[node.c[i]]
            child.parent = node.ID

for i in range(n):
    node = nodes[i]
    if node.parent == -1:
        rootIdx = node.ID

trace(nodes[rootIdx], 0)

for i in range(n):
    node = nodes[i]

    if node.parent == -1:
        node.node_type = 'root'
    elif len(node.c) > 0:
        node.node_type = 'internal node'
    else:
        node.node_type = 'leaf'

for i in range(n):
    nodes[i].print_self()

Solution (Python):

class Node:
    def __init__(self):
        self.parent = -1
        self.type = ""
        self.depth = 0
        self.children = []


def dfs(id, d):
    Nodes[id].depth = d
    for child in Nodes[id].children:
        dfs(child, d+1)


def main():
    n = int(input())
    global Nodes
    Nodes = [Node() for i in range(n)]

    for i in range(n):
        id, k, *c = map(int, input().split())
        Nodes[id].children = c
        if k == 0:
            Nodes[id].type = "leaf"
        else:
            Nodes[id].type = "internal node"
            for j in range(k):
                Nodes[c[j]].parent = id

    rootid = ""
    for i, node in enumerate(Nodes):
        if node.parent == -1:
            rootid = i
    Nodes[rootid].type = "root"
    dfs(rootid, 0)

    for i, node in enumerate(Nodes):
        print("node {}: parent = {}, depth = {}, {}, {}".format(
            i, node.parent, node.depth, node.type, node.children))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())

list_tree = [[] for _ in range(n)]
list_parent = [None for _ in range(n)]

for _ in range(n):

    id, k, *C = map(int, input().split())

    list_tree[int(id)].extend(C)

    for c in C:
        list_parent[int(c)] = int(id)


for id in range(n):
    child = list_tree[id]

    if list_parent[id] == None:
        parent = -1
    else:
        parent = list_parent[id]

    depth = 0
    parent_now = list_parent[id]

    while parent_now != None:
        depth += 1
        parent_now = list_parent[parent_now]

    if depth == 0:
        type_node = "root"
    elif not child:
        type_node = "leaf"
    else:
        type_node = "internal node"

    print(f"node {id}: parent = {parent}, depth = {depth}, {type_node}, {child}")

Solution (Python):
n = int(input())

tree = []
for i in range(n):
  data = list(map(int,input().split()))
  node = data[0]
  depth = data[1]
  child = []
  parent = -1
  for j in data[2:]:
    child.append(j)
  tree.append([node,depth,child,parent])

tree.sort()

for i in range(len(tree)):

  for j in tree[i][2]:
    tree[j][3] = i

def rooting(tree,node,depth):
  tree[node][1] = depth
  if len(tree[node][2]) == 0:
    return
  for i in tree[node][2]:
    rooting(tree,i,depth+1)

for i in range(n):
  if tree[i][3] == -1:
    root = i
rooting(tree,root,0)


for i in range(n):
  print("node %d: parent = %d, depth = %d," %(tree[i][0],tree[i][3],tree[i][1]),end=" ")
  if tree[i][3] == -1:
    print("root,",end=" ")
  elif tree[i][3] != -1 and len(tree[i][2]) != 0:
    print("internal node,",end=" ")
  else:
    print("leaf,",end=" ")
  print(tree[i][2])

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 6)

class Tree:
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]
        self.depth = [0 for _ in range(n)]
        self.children = [[] for _ in range(n)]

    def add(self, x, children):
        self.children[x] = children
        for child in children:
            self.parent[child] = x

    def update(self):
        root = -1
        for node, p in enumerate(self.parent):
            if p == -1:
                root = node
                break
        stack = [root]
        d = 0
        while stack:
            temp = []
            for node in stack:
                self.depth[node] = d
                temp += self.getChildren(node)
            stack = temp
            d += 1
    
    def getParent(self, x):
        return self.parent[x]
    
    def getChildren(self, x):
        return self.children[x]

    def getDepth(self, x):
        return self.depth[x]

    def isRoot(self, x):
        return self.getParent(x) == -1

    def isLeaf(self, x):
        return self.getChildren(x) == []

    def getType(self, x):
        if self.isRoot(x):
            return 'root'
        elif self.isLeaf(x):
            return 'leaf'
        return 'internal node'
    
N = int(input())
t = Tree(N)

for _ in range(N):
    q = list(map(int, input().split()))
    i = q[0]
    k = q[1]
    childs = q[2:]
    t.add(i, childs)

t.update()

for i in range(N):
    print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(i, t.getParent(i), t.getDepth(i), t.getType(i), t.getChildren(i)))

Solution (Python):
n = int(input())

class Node:
    def __init__(self, id, k, c):
        self.id = id
        self.k = k
        self.c = c
        self.parent = -1
        self.depth = -1

    def setParent(self, parent):
        self.parent = parent

    def setDepth(self, depth):
        self.depth = depth

    def getId(self):
        return self.id

    def getChildren(self):
        return self.c

    def getParent(self):
        return self.parent

    def getDepth(self):
        return self.depth

    def printInfo(self):
        info = ''
        if self.parent == -1:
            info = 'root'
        elif self.k != 0:
            info = 'internal node'
        else:
            info = 'leaf'
        print("node {}: parent = {}, depth = {}, {}, {}".format(
            self.id, self.parent, self.depth, info, self.c
        ))

nodes = [0] * n

for i in range(n):
    arr = input().split()
    id = int(arr[0])
    k = int(arr[1])
    c = list(map(int, arr[2:]))
    nodes[id] = Node(id, k, c)

for e in nodes:
    for id in e.getChildren():
        nodes[id].setParent(e.getId())

for e in nodes:
    if e.getParent() == -1:
        e.setDepth(0)

for i in range(21):
    for e in nodes:
        if e.getDepth() == i:
            for j in e.getChildren():
                nodes[j].setDepth(i + 1)

for e in nodes:
    e.printInfo()

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


n = int(input())
root = set(range(n))
T = [None] * n

for _ in range(n):
    A = list(map(int, input().split()))
    children = A[2:]
    T[A[0]] = [children, None, None]
    root -= set(children)

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

for i,node in enumerate(T):
    ch, p, d = node
    print('node {}: parent = {}, depth = {}, {}, {}'.format(
            i, p, d, 'root' if not d else 'internal node' if ch else 'leaf', ch
        ))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

nodedict = {}

class Node:
    def __init__(self, id, jisu, children):
        self.id = id
        self.jisu = jisu
        self.children = children
        self.parent = -1
        self.depth = -1

    def __repr__(self):
        return "id:{}, jisu:{}, parent:{}, depth:{}, children:{}".format(self.id, self.jisu, self.parent, self.depth, self.children)

def assign_depth(node, current_depth):
    node.depth = current_depth
    for childid in node.children:
        assign_depth(nodedict[childid], current_depth+1)

def solve():
    n = int(input())

    
    for i in range(n):
        input_list = list(map(int, input().split()))
        id = input_list[0]
        jisu = input_list[1]
        children = input_list[2:]
        nodedict[id] = Node(id, jisu, children)

    
    for i in range(n):
        node = nodedict[i]
        for childid in node.children:
            child = nodedict[childid]
            child.parent = node.id

    
    
    neid = None
    for i in range(n):
        node = nodedict[i]
        if node.parent == -1:
            neid = node.id
            break

    
    assign_depth(nodedict[neid], 0)

    
    for i in range(n):
        node = nodedict[i]
        if node.depth == 0:
            type = "root"
        elif len(node.children) == 0:
            type = "leaf"
        else:
            type = "internal node"

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

solve()

Solution (Python):
class Node:
    def __init__(self,id):
        self.id = id
        self.child = []
        self.parent = -1
        self.depth = 0
        self.type = "root"    

n = int(input())
T = [Node(i) for i in range(n)]
for ni in range(n):
    id,  k, *c = [int(i) for i in input().split()]
    T[id].child = c 


for ni in range(n):
    for c in T[ni].child:
        T[c].parent = ni


for ni in range(n):
    i = ni
    cnt = 0
    while T[i].parent != -1:
        i = T[i].parent
        cnt += 1
    T[ni].depth = cnt


for ni in range(n):
    if T[ni].parent == -1:
        T[ni].type = "root"
    elif T[ni].child == []:
        T[ni].type = "leaf"
    else:
        T[ni].type = "internal node"

for ni in range(n):
    print("node "+str(T[ni].id)+": parent = "+str(T[ni].parent)+\
    ", depth = "+str(T[ni].depth)+", "+T[ni].type+", ",end="")
    print(T[ni].child)

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

def get_depth(u, p):
  D[u] = p
  if result[u].right is not None:
    get_depth(result[u].right, p)
  if result[u].left is not None:
    get_depth(result[u].left, p+1)

def get_depth_1(u, p):
  i = u
  d = 0
  while result[u].parent != -1:
    u = result[u].parent
    d += 1
  D[i] = d

n = int(input())
node  = [list(map(int, input().split())) for _ in range(n)] 
result = [Node() for _ in range(n)]
D = [0 for _ in range(n)]

def initiate(li):
  for l in li:
    n = l[0]
    child_num = l[1]
    child = []
    i = 1
    if child_num != 0:
      child = l[2:]
    for c in child:
      if i == 1:
        result[n].left = c 
        i += 1
      else:
        result[idx].right = c 
      idx = c
      result[c].parent = n

initiate(node)
u = 0
for i in range(n):
  if result[i].parent == -1:
    u = i
for u in range(n):
  get_depth_1(u, 0)
final = []
for i in range(n):
  n = i 
  p = result[i].parent
  d = D[i]
  c = [result[i].left]
  j = result[i].left
  if j is not None:
    while result[j].right is not None:
      c.append(result[j].right)
      j = result[j].right
  final.append([n, p, d, c])
  
for i in range(n+1):
  n, p, d, c = final[i]
  typ = ""
  if p == -1:
    typ = "root"
    if c == [None]:
      c = []
  else:
    if c == [None]:
      typ = "leaf"
      c = []
    else:
      typ = "internal node"
  print("node {}: parent = {}, depth = {}, {}, {}".format(n, p, d, typ, c))

Solution (Python):
class Node():
    def __init__(self,id):
        self.id = id
        self.parent = -1
        self.child = []

    def addParent(self,parent):
        self.parent = parent

    def addChild(self,child):
        self.child = child

n = int(input())
nodes = {}

for i in range(n):
    line = list(input().split(" "))
    id = int(line[0])
    child = []
    for k in range(int(line[1])):
        childId = int(line[2+k])
        child.append(childId)
        if not childId in nodes:
            nodes[childId] = Node(childId)
        nodes[childId].addParent(id)

    if not id in nodes:
        nodes[id] = Node(id)
    nodes[id].addChild(child)

for i in sorted(nodes):
    node = nodes[i]
    depth = 0
    startNode = node
    while not startNode.parent == -1:
        startNode = nodes[startNode.parent]
        depth += 1

    if node.parent == -1:
        type = "root"
    elif not node.parent == -1 and not node.child == []:
        type = "internal node"
    elif not node.parent == -1 and node.child == []:
        type = "leaf"

    ans = ''
    ans += 'node ' + str(node.id) + ': '
    ans += 'parent = '
    ans += str(node.parent)
    ans += ', depth = ' + str(depth)
    ans += ', ' + type + ', '
    ans += str(node.child)

    print(ans)

Solution (Python):
class Node:
    def __init__(self):
        self.id = -1
        self.parent = None
        self.childs = []

    def parentId(self):
        return -1 if self.parent == None else self.parent.id

    def depth(self):
        r = 0
        p = self.parent
        while p != None:
            r += 1
            p = p.parent
        return r

    def type(self):
        if self.parent == None:
            return "root"
        elif len(self.childs) > 0:
            return "internal node"
        return "leaf"

    def childIds(self):
        return [c.id for c in self.childs]


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

for i in range(n):
    id, k, *c, = map(int, input().split())
    p = nodes[id]
    p.id = id
    for v in c:
        p.childs.append(nodes[v])
        nodes[v].parent = p

for node in nodes:
    s = f"node {node.id}: "
    s += f"parent = {node.parentId()}, "
    s += f"depth = {node.depth()}, "
    s += f"{node.type()}, "
    s += f"{node.childIds()}"
    print(s)

Solution (Python):
class Node:
    def __init__(self, n, parent=None, child=None):
        self.n = n
        self.p = parent
        self.child = child

    @property
    def parent(self):
        return self.p

    @parent.setter
    def parent(self, v):
        self.p = v

    @property
    def depth(self):
        count = 0
        p = self.parent
        while p is not None:
            count += 1
            p = p.parent
        return count

    @property
    def type(self):
        if self.parent is None:
            return "root"
        elif not self.child:
            return "leaf"
        else:
            return "internal node"

    def __str__(self):
        if self.parent is None:
            parent = -1
        else:
            parent = self.parent.n

        return "node {}: parent = {}, depth = {}, {}, {}".format(
            self.n, parent, self.depth, self.type, self.child
        )


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

for i in range(n):
    l = [int(i) for i in input().split()]
    id_ = l[0]
    k = l[1]
    nodes[id_].child = l[2:]
    if k != 0:
        for li in l[2:]:
            nodes[li].parent = nodes[id_]

for n in nodes:
    print(n)

Solution (Python):

import queue

class Node:
    def __init__(self, myNum, childNums):
        self.myNum = myNum
        self.parentNum = -1
        self.childNums = childNums
        self.nodeType = ""
        self.depth = -1
        
n = int(input().rstrip())
nodes = []

for i in range(n):
    line = [int(i) for i in input().rstrip().split()]
    childNums = [i for i in line[2:]]
    nodes.append(Node(line[0],childNums))

nodes = sorted(nodes,key=lambda x: x.myNum)

for node in nodes:
    for num in node.childNums:
        nodes[num].parentNum = node.myNum


for node in nodes:
    if node.parentNum == -1:
        node.nodeType = "root"
        rootNum = node.myNum
    elif not node.childNums:
        node.nodeType = "leaf"
    else:
        node.nodeType = "internal node"
        

q = queue.Queue()
q.put(nodes[rootNum])
nodes[rootNum].depth=0
while not q.empty():
    nd = q.get()
    for c in nd.childNums:
        nodes[c].depth = nd.depth + 1
        q.put(nodes[c])


for node in nodes:
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(node.myNum,node.parentNum,node.depth,node.nodeType,node.childNums))