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):
from sys import stdin

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

class Tree:
    def __init__(self, nodes):
        self.nodes = nodes

        for i in range(self.size()):
            if not self.isLeaf(i):
                for c in self.nodes[i].children:
                    self.nodes[c].parent = i

        for i in range(self.size()):
            self.nodes[i].depth = self.depth(i)

    def depth(self, i):
        n = self.nodes[i]
        if self.isRoot(i):
            return 0
        else:
            return self.depth(n.parent)+1


    def size(self):
        return len(self.nodes)

    def isLeaf(self, i):
        return len(self.nodes[i].children) == 0

    def isRoot(self, i):
        return self.nodes[i].parent == -1

n = int(stdin.readline().rstrip())
nodes = [Node() for _ in range(n)]
for i in range(n):
    l = [int(x) for x in stdin.readline().rstrip().split()]
    if l[1] > 0:
        nodes[l[0]].children.extend(l[2:])

t = Tree(nodes)
for i in range(t.size()):
    l = ["node ", i, ": parent = ", t.nodes[i].parent, ", depth = ", t.nodes[i].depth, ", "]
    if t.isRoot(i):
        l.append("root, ")
    elif t.isLeaf(i):
        l.append("leaf, ")
    else:
        l.append("internal node, ")

    l.append(t.nodes[i].children)
    print(*l, sep="")

Solution (Python):
class node:
    parent = -1
    depth = 0

    def __init__(self, no, Children, k):
        self.no = no
        self.Children = Children
        self.numofchild = k
    
    def dfs(self, nodes, d):
        self.depth = d
        for i in range(self.numofchild):
            nodes[self.Children[i]].dfs(nodes, d+1)

head = -1
nodes = []
n = int(input())
for i in range(n):
    temp = node(i, [], 0)
    nodes.append(temp)

for i in range(n):
    temp = list(map(int,input().split()))
    if temp[1] > 0:
        child = temp[2 : 2+temp[1]]
        nodes[temp[0]].Children =child
        for j in range(temp[1]):
            nodes[nodes[temp[0]].Children[j]].parent = temp[0]
    nodes[temp[0]].numofchild = temp[1]

for i in range(n):
    if nodes[i].parent == -1:
        head = i
        break

nodes[head].dfs(nodes, 0)

for i in range(n):
    if nodes[i].parent == -1:
        print("node " + str(i) + ": parent = " + str(nodes[i].parent) + ", depth = " + str(nodes[i].depth) + ", root, [" + ', '.join(map(str, nodes[i].Children)) + "]")
    elif nodes[i].numofchild == 0:
        print("node " + str(i) + ": parent = " + str(nodes[i].parent) + ", depth = " + str(nodes[i].depth) + ", leaf, [" + ', '.join(map(str, nodes[i].Children)) + "]")
    else:
        print("node " + str(i) + ": parent = " + str(nodes[i].parent) + ", depth = " + str(nodes[i].depth) + ", internal node, [" + ', '.join(map(str, nodes[i].Children)) + "]")

Solution (Python):


"""
・再帰検索を各辺1回通れば良くした版
"""

import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

def upd_dpth(children, depth):
    for i in children:
        nodes[i][1] = depth+1 
        upd_dpth(nodes[i][2], depth+1)

N = INT()


nodes = [[-1, 0, []] for i in range(N)]

for i in range(N):
    node = LIST()
    
    nodes[node[0]][2].extend(node[2:])
    
    for j in nodes[node[0]][2]:
        nodes[j][0] = node[0]

for i in range(N):
    
    if nodes[i][0] == -1:
        
        upd_dpth(nodes[i][2], 0)

for i in range(N):
    parent, depth, children = nodes[i]
    if parent == -1:
        _type = 'root'
    elif len(children) == 0:
        _type = 'leaf'
    else:
        _type = 'internal node'
    print('node {node}: parent = {parent}, depth = {depth}, {type}, {children}'.format(
        node=i, parent=parent, depth=depth, type=_type, children=children))

Solution (Python):
from typing import List






class Node:
    node_id = -999
    child = []
    parent = -1
    depth = -999
    node_type = 'Not set'

    def __init__(self, id: int, child: List[int]):
        self.node_id = id
        self.child = child

    def show(self):
        out = f'node {self.node_id}: '
        out += f'parent = {self.parent}, depth = {self.depth}, '
        out += f'{self.node_type}, '
        tmp = ', '.join(map(str, self.child))
        out += f'[{tmp}]'
        print(out)

    def get_value(self):
        return self.node_id


def show(node_list: List[Node]):
    for n in node_list:
        n.show()


def get_parent(node_id: int) -> int:
    return node_list[node_id].parent


def set_depth(node_id: int, depth: int):
    node_list[node_id].depth = depth
    for ch in node_list[node_id].child:
        set_depth(ch, depth + 1)


def set_node_info(node_list: List[Node]):

    
    for target in node_list:
        if target.parent == -1:
            set_depth(target.node_id, 0)
            break

    
    for target in node_list:
        if target.depth == 0:
            target.node_type = 'root'
        elif target.depth > 0:
            target.node_type = \
                'leaf' if len(target.child) == 0 else 'internal node'
        else:
            raise ValueError()


n = int(input())
node_list = []
for _i in range(n):
    node_list.append(Node(_i, []))

for _i in range(n):
    line = [int(i) for i in input().split()]
    node_id = line[0]
    num = line[1]

    
    for i in range(num):
        child_id = line[2 + i]
        node_list[node_id].child.append(child_id)
        node_list[child_id].parent = node_id

set_node_info(node_list)
show(node_list)

Solution (Python):
def depth(s):
    for i in ch[s]:
        dep[i] = dep[s]+1
        if len(ch[i]) != 0:
            depth(i)


def parent(t):
    for i in ch[t]:
        par[i] = t
        if len(ch[i]) != 0:
            parent(i)


n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]


ch = {}
par = {}
dep = {}
kari = []
for i in range(n):
    kari.append(i)


for i in data:
    ch[i[0]] = list(i[2:])
    for j in list(i[2:]):
        kari.remove(j)


r = kari[0]
dep[r] = 0
par[r] = -1


'''
for i in range(n):
    
    try:
        par[i] = [k for k, v in ch.items() if i in v][0]
    except:
        par[i] = -1
        dep[i] = 0
        r = i
        '''

depth(r)
parent(r)


for i in range(n):
    if par[i] == -1:
        tmp = 'root'
    elif len(ch[i]) == 0:
        tmp = 'leaf'
    else:
        tmp = 'internal node'
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i, par[i], dep[i], tmp, ch[i]))

Solution (Python):
class Node:
    def __init__(self, parent, lchild, sibling):
        self.parent = parent
        self.lchild = lchild
        self.sibling = sibling
        self.depth = None

    def __repr__(self):
        return "{" + str(self.parent) + " " + str(self.lchild) + " " + str(self.sibling) + "}"

class NodeList:
    def __init__(self,size):
        self.nlist = [Node(None,None,None) for i in range(size)]

    def add(self, id, sibs):
        
        self.nlist[id].lchild = sibs[0]
        
        for i in range(len(sibs)-1):
            self.nlist[sibs[i]].parent = id
            self.nlist[sibs[i]].sibling = sibs[i+1]
            
        self.nlist[sibs[-1]].parent = id

    def calcDepth(self, idx):
        cnt = -1
        while  idx != None:
            
            idx = self.nlist[idx].parent
            cnt += 1
        return cnt

    def getChilds(self, lchild):
        res = []
        while lchild != None:
            
            res.append(lchild)
            lchild = self.nlist[lchild].sibling
        return res

    def calcStatus(self, node):
        if node.parent == None:
            return "root"
        if node.lchild == None:
            return "leaf"
        return "internal node"

    def print(self):
        for idx, node in enumerate(self.nlist):
            parent = node.parent
            if parent == None:
                parent = -1
            depth = self.calcDepth(idx)
            childs = self.getChilds(node.lchild)
            status = self.calcStatus(node)
            print("node "+str(idx)+": parent = "+str(parent)+", depth = "+str(depth)+", "+str(status)+", "+str(childs))


    def __repr__(self):
        return str(self.nlist)

            


N = int(input())
NL = NodeList(N)

for i in range(N):
    D = list(map(int, input().split()))
    if len(D) is not 2:
        NL.add(D[0], D[2:])
NL.print()

Solution (Python):
import sys

n = int(input())
node_list = []

sys.setrecursionlimit(10 ** 8)
for i in range(n):
    node_list.append(list(map(int, sys.stdin.readline().split())))

parents = [-1 for i in range(n)]
right = [None for i in range(n)]
left = [None for i in range(n)]
depth = [None for i in range(n)]


def get_children(num):
    c = left[num]
    r = []
    while c is not None:
        r.append(c)
        c = right[c]
    return r


def set_depth(num, p):
    depth[num] = p
    if right[num] is not None:
        set_depth(right[num], p)
    if left[num] is not None:
        set_depth(left[num], p + 1)


for i in range(n):
    node = node_list[i]
    v = node[0]
    d = node[1]
    for j in range(d):
        if j == 0:
            left[v] = node[2 + j]
        else:
            right[m] = node[2 + j]
        m = node[2 + j]
        parents[node[2 + j]] = v
root = -1
for i in range(n):
    if parents[i] == -1:
        root = i
set_depth(root, 0)
for i in range(n):
    print("node " + str(i) + ":", end=" ")
    print("parent = " + str(parents[i]) + ",", end=" ")
    print("depth = " + str(depth[i]) + ",", end=" ")

    if parents[i] == -1:
        print("root,", end=" ")
    elif left[i] is None:
        print("leaf,", end=" ")
    else:
        print("internal node,", end=" ")
    print(get_children(i))

Solution (Python):
import sys

TYPE_ROOT = 0
TYPE_NODE = 1
TYPE_LEAF = 2


class Node:
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.children = []
        self.type = None
        self.depth = 0


def set_depth(node, depth):
    node.depth = depth
    for child in node.children:
        set_depth(child, depth + 1)


nodes = {}


def get_node(id):
    if id in nodes:
        return nodes[id]
    node = Node(id)
    nodes[id] = node
    return node


n = int(sys.stdin.readline())
for _ in range(n):
    id, k, *children = map(int, sys.stdin.readline().split())
    node = get_node(id)
    for cid in children:
        child = get_node(cid)
        child.parent = node
        node.children.append(child)
    node.type = TYPE_NODE if node.children else TYPE_LEAF

root = next(node for node in nodes.values() if not node.parent)
root.type = TYPE_ROOT
set_depth(root, 0)


for _, node in sorted(nodes.items()):
    print('node %d: parent = %d, depth = %d, %s, [%s]' % (
        node.id,
        node.parent.id if node.parent else -1,
        node.depth,
        ['root', 'internal node', 'leaf'][node.type],
        ', '.join(str(child.id) for child in node.children)
    ))

Solution (Python):


class node:
    def __init__(self,nodeid):
        self.parent = "" 
        self.child = []
        self.childid = []
        self.depth = 0
        self.parent = -1
        self.parentid = -1
        self.nodeid = nodeid
        self.type = "root"
    def setChild(self,cn):
        self.child.append(cn)
        self.childid.append(cn.nodeid)
        cn.parent = self
        cn.parentid = self.nodeid
        cn.depth = self.depth + 1
        cn.setNodeType()
        self.setNodeType()
        return
    def getDepth(self):
        cnt = 0
        t = self
        while True:
            if (t.parentid == -1 or  cnt > 10):
                break
            t = t.parent
            cnt = cnt + 1
        return cnt

    def getChildCount(self):
        return len(self.child)
    def setNodeType(self):
        if (self.depth == 0):
            self.type = "root"
        else:
            if (len(self.child) == 0 ):
                self.type = "leaf"
            else:
                self.type = "internal node" 
    def getNodeType(self):
        return self.type
    def showNode(self):
        print ('node {}: parent = {}, depth = {}, {}, {}'.format(self.nodeid,self.parentid,self.getDepth(),self.getNodeType(),self.childid))
        return

nl = []
n = int(input())
for i in range(0,n):
    nl.append(node(i))

for i in range(0,n):
    nodeinfo = list (map(int,input().split()))
    for j in nodeinfo[2:]:
        nl[nodeinfo[0]].setChild(nl[j])
for i in range(0,n):
    nl[i].showNode()

Solution (Python):
class Node:
    parent = ""
    depth = ""

    def __init__(self, children=[]):
        self.children = children
        if len(children) == 0:
            self.type = 'leaf'
        else:
            self.type = 'internal node'


def add_parent_node_and_depth(nodes, parent_node_no, node_no, depth):
    nodes[node_no].parent = parent_node_no
    nodes[node_no].depth = depth
    for child in nodes[node_no].children:
        add_parent_node_and_depth(nodes, node_no, child, depth+1)
    return


def main():
    n = int(input())
    nodes = {}
    leafs = {}
    for i in range(n):
        node_no, child_num, *children = [int(x) for x in input().split()]
        if child_num == 0:
            leafs[node_no] = Node([])
        else:
            nodes[node_no] = Node(children)

    nodes.update(leafs)
    
    node_no = list(leafs.keys())[0]
    while True:
        parent_node_no = [key for key, value in nodes.items() if node_no in value.children]
        if len(parent_node_no) == 0:
            root_node_no = node_no
            nodes[root_node_no].type = 'root'
            break
        node_no = parent_node_no[0]

    
    add_parent_node_and_depth(nodes, parent_node_no=-1, node_no=root_node_no, depth=0)

    for i in range(n):
        node = nodes[i]
        print("node {}: parent = {}, depth = {}, {}, [{}]".
              format(str(i), node.parent, node.depth, node.type, ", ".join(map(str, node.children))))

    return


main()

Solution (Python):
class Trees():
    def __init__(self):
        self.nodes = {}
    def add_nodes(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)
    def add_child(self, id, child_id):
        self.add_nodes(child_id)
        self.nodes[id].add_child_id(self.nodes[child_id])
        
class Node():
    def __init__(self, id):
        self.node = id
        self.parent = None
        self.depth = 0
        self.nodetype = 'root'
        self.children = []
    
    def add_child_id(self, child):
        child.parent = self
        self.children.append(child)
        child.update_depth()
        self.update_nodetype()
        child.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.depth == 0:
            self.nodetype = 'root'
        elif len(self.children) > 0:
            self.nodetype = 'internal node'
        else:
            self.nodetype = 'leaf'
    
    def __str__(self):
        parent = self.parent.node if self.parent else -1
        children = ', '.join([str(node.node) for node in self.children])
        return 'node {}: parent = {}, depth = {}, {}, [{}]'.format(self.node, parent, 
                                                                   self.depth, self.nodetype, children)
    

tree = Trees()

n = int(input())

for i in range(n):
    a = list(map(int,input().split()))
    tree.add_nodes(a[0])
    for child in a[2:]:
        tree.add_child(id=a[0], child_id=child)

for id in range(n):
    print(f"{tree.nodes[id]}")

Solution (Python):
class Node:
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.children=[]
        self.degree=0
        self.depth=-1
        self.state="leaf"




def get_depth(Tree,node,depth):
    for child in node.children:
        Tree[child].depth=depth+1
        get_depth(Tree,Tree[child],depth+1)



Tree=[]
n=int(input())
for i in range(n):
    Tree.append(Node())
for loop in range(n):
    info=list(map(int,input().split()))
    i=info[0]
    Tree[i].name=info[0]
    Tree[i].degree=info[1]
    for j in range(2,len(info)):
        (Tree[i].children).append(info[j])
        Tree[i].state="internal node"
        Tree[info[j]].parent=i


for node in Tree:
    if(node.parent==-1):
        node.state="root"
        node.depth=0
        get_depth(Tree,node,0)



        


for node in Tree:
    print(f"node {node.name}: parent = {node.parent}, depth = {node.depth}, {node.state}, {node.children}")

Solution (Python):
import sys
readline = sys.stdin.readline
writelines = sys.stdout.writelines
N = int(readline())
depth = [0]*N
PR = [-1]*N
G = [None]*N
for i in range(N):
    i, _, *cs, = map(int, readline().split())
    G[i] = cs
    for v in G[i]:
        PR[v] = i
def dfs(v, d):
    depth[v] = d
    for w in G[v]:
        dfs(w, d+1)
dfs(PR.index(-1), 0)
writelines(["node %d: parent = %d, depth = %d, %s, %s\n" % (i, PR[i], depth[i], ('root' if PR[i] == -1 else 'leaf' if len(G[i]) == 0 else 'internal node'), G[i]) for i in range(N)])

Solution (Python):
import sys

n = int(sys.stdin.readline())
parent = [-1 for _ in range(n)]
children = [[] for _ in range(n)]
nodes = []
for _ in range(n):
    ll = list(map(int, sys.stdin.readline().split()))
    nodes.append(ll[0])
    children[ll[0]] = ll[2:]
    for i in range(ll[1]):
        parent[ll[2+i]] = ll[0]

for n in sorted(nodes):
    p = parent[n]
    if p==-1:
        type='root'
    else:
        if len(children[n])==0:
            type='leaf'
        else:
            type='internal node'
        
    depth = 0
    k=n
    while parent[k]>=0:
        k = parent[k]
        depth+=1
        
    print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(n, p, depth, type, children[n]))

Solution (Python):
def getDepth(u):
    d = 0
    while node_list[u].parent != -1:
        u = node_list[u].parent
        d += 1
    return d
def getChildren(u):
    c = node_list[u].left
    child_list = []
    while c != -1:
        child_list.append(c)
        c = node_list[c].right
    return child_list

def getType(u):
    if node_list[u].parent == -1:
        return "root"
    if node_list[u].left == -1:
        return "leaf"
    return "internal node"
max_value = 10 ** 10
nil = -1

class Node():
    " node of the tree structure"
    def __init__(self, name = -1, parent = -1, left = -1, right = -1):
        self.name = name
        self.parent = parent
        self.left = left
        self.right = right
node_list = []
n = int(input())
for i in range(n):
    node = Node()
    node_list.append(node)

for i in range(n):
    a,b,*args = map(int, input().split())
    for j in range(b):
        if j == 0:
            node_list[a].left = args[j]
        else:
            node_list[l].right = args[j]
        l = args[j]
        node_list[args[j]].parent = a




for i in range(n):
    print("node", str(i) + ":" , "parent =", str(node_list[i].parent) + ",", "depth =", str(getDepth(i)) + ",", getType(i) + ",", getChildren(i))

Solution (Python):
from collections import deque
from enum import Enum
import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

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

global nodes

def calc_depth(node_id,arg_depth):

    nodes[node_id].depth = arg_depth
    for child in nodes[node_id].children:
        calc_depth(child, arg_depth+1)


V = int(input())

nodes = []

for loop in range(V):
    node = Node()
    nodes.append(node)


for loop in range(V):

    table = list(map(int,input().split()))
    node_id = table[0]
    num = table[1]

    for i in range(num):
        child_id = table[2+i]
        nodes[node_id].children.append(child_id)
        nodes[child_id].parent_id = node_id



for i in range(V):
    if nodes[i].parent_id == -1:
        calc_depth(i,0)
        break


for i in range(V):

    print("node %d: parent = %d, depth = %d, "%(i,nodes[i].parent_id,nodes[i].depth),end = "")

    if nodes[i].parent_id == -1:
        print("root,",end = "")
    else:
        if len(nodes[i].children) == 0: 
            print("leaf,",end = "")
        else: 
            print("internal node,",end = "")

    print(" [",end = "")
    print(', '.join(map(str,nodes[i].children)),end = "")
    print("]")

Solution (Python):
n = int(input())
nodes = []
par_kid = {}
depthnot0 = []
for i in range(n):
    node = list(map(int, input().split()))
    nodes.append(node)
    if (node[1] != 0):
        par_kid[node[0]] = node[2:]
        depthnot0 += node[2:]
for i in range(n):
    if (i not in depthnot0):
        first_node = i
        break


par_dep = {first_node:(-1,0)}
def pd(f):
    if (len(par_kid) == 0):
        return 0
    A = par_kid[f]
    c = 0
    for a in A:
        par_dep[a] = (f,par_dep[f][1]+1)
        if (a not in par_kid.keys()):
            c += 1
            continue
        pd(a)
    if (c == len(A)):
        return 0
s = pd(first_node)
    
for i in range(n):
    parent = par_dep[i][0]
    depth = par_dep[i][1]
    if (n == 1):
        print('node 0: parent = -1, depth = 0, root, []')
    elif (i == first_node):
        print('node {}: parent = {}, depth = {}, root,'.format(i,parent,depth), par_kid[i])
    elif (i in par_kid.keys()):
        print('node {}: parent = {}, depth = {}, internal node,'.format(i,parent,depth), par_kid[i])
    else:
        print('node {}: parent = {}, depth = {}, leaf, []'.format(i,parent,depth))

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

class Node():
    def __init__(self):
        self.parent = None
        self.left_child = None
        self.right_sibling = None
        self.type = None

tree = []
for _ in range(n):
    tree.append(Node())

for _ in range(n):
    tmp = list(map(int, input().split()))
    id = tmp[0]
    degree = tmp[1]
    children = tmp[2:]
    if degree > 0:
        tree[id].left_child = children[0]
        for (cnt, child) in enumerate(children):
            tree[child].parent = id
            if cnt < degree - 1:
                tree[child].right_sibling = children[cnt + 1]
    
    
def get_depth(id):
    out = 0
    node = tree[id]
    while node.parent is not None:
        out += 1
        node = tree[node.parent]
    return out

def get_children(id):
    left_child_id = tree[id].left_child
    if left_child_id is None:
        return []
    node = tree[left_child_id]
    out = [left_child_id]
    while node.right_sibling is not None:
        out.append(node.right_sibling)
        node = tree[node.right_sibling]
    return out

def get_type(id):
    node = tree[id]
    if node.parent is None:
        return 'root'
    elif node.left_child is not None:
        return 'internal node'
    else:
        return 'leaf'
    
for id in range(n):
    print(f"node {id}: parent = {-1 if tree[id].parent is None else tree[id].parent}, depth = {get_depth(id)}, {get_type(id)}, {get_children(id)}")

Solution (Python):

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 sorted(tree.nodes):
    print(tree.nodes[id])

Solution (Python):
class Node:
    def __init__(self, nid, k, c):
        self.nid = nid
        self.parent = -1
        self.depth = 0
        if k == 0:
            self.type = "leaf"
        else:
            self.type = "internal node"
        self.c = c
    
    def dump(self):
        print("node {}: parent = {}, depth = {}, {}, {}".format(self.nid,self.parent,self.depth,self.type,self.c))
from collections import deque
n = int(input())
T = [[int(j) for j in i] for i in [input().split() for i in range(n)]]
D = {}
for i in T:
    D[i[0]] = Node(i[0],i[1],i[2:])
    
for i in range(n):
    for j in D[i].c:
        D[j].parent = D[i].nid
rootid = 0
while(True):
    if D[rootid].parent == -1:
        break
    else:
        rootid = D[rootid].parent
D[rootid].type = "root"
d = deque()
d.append(D[rootid])
while(len(d)>0):
    tmp = d.pop()
    if tmp.parent == -1:
        pass
    else:
        tmp.depth = D[tmp.parent].depth + 1
    for i in tmp.c:
        d.appendleft(D[i])
for i in range(n):
    D[i].dump()

Solution (Python):

class Node:
    def __init__(self, idnty):
        self.id = idnty
        self.parent = None
        self.children = []
        self.depth = 0
    def __str__(self):
        prnt = self.parent.id if self.parent else -1
        typ = 'root'
        if self.depth > 0: typ = 'internal node'
        if self.depth > 0 and not self.children: typ = 'leaf'
        cld = [n.id for n in self.children]
        return 'node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(self.id, prnt, self.depth, typ, cld)

n = int(input())
tr = [Node(i) for i in range(n)]
for _ in range(n):
    rl = list(map(int, input().split()))
    id, k = rl[0],rl[1]
    if k > 0:
        for i in rl[2:]:
            c = tr[i]
            c.parent = tr[id]
            c.depth += tr[id].depth + 1
            tr[id].children.append(c)
    else:
        p = tr[id].parent
        if p:
            tr[id].depth = p.depth + 1
for t in tr: print(t)