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):
import sys
sys.setrecursionlimit(10**6)


class Node():
    def __init__(self, parent=-1, child=-1, sibling=-1, depth=-1):
        self.parent = parent
        self.first_child = child
        self.next_sibling = sibling
        self.depth = depth


class Tree():
    def __init__(self, n):
        self.T = [Node() for _ in range(n)]

    def type_of(self, i):
        node = self.T[i]
        if node.parent == -1:
            return 'root'
        if node.first_child == -1:
            return 'leaf'
        return 'internal node'

    def children_of(self, i):
        node = self.T[i]
        if node.first_child == -1:
            return []

        children = [node.first_child]
        node = self.T[node.first_child]
        while node.next_sibling != -1:
            children.append(node.next_sibling)
            node = self.T[node.next_sibling]

        return children

    def depth_of(self, i):
        return self.T[i].depth

    def get_root(self, ):
        for i, node in enumerate(self.T):
            if node.parent == -1:
                return i

    def set_children(self, i, c):

        if len(c) == 0:
            return False

        self.T[i].first_child = c[0]

        num_c = len(c)
        for j in range(num_c-1):
            self.T[c[j]].parent = i
            self.T[c[j]].next_sibling = c[j+1]
        self.T[c[num_c-1]].parent = i

        return True

    def set_depth(self, ):
        root = self.get_root()
        self.depth(root, 0)

    def depth(self, i, d):
        self.T[i].depth = d
        if self.T[i].next_sibling != -1:
            self.depth(self.T[i].next_sibling, d)
        if self.T[i].first_child != -1:
            self.depth(self.T[i].first_child, d+1)

    def parent_of(self, i):
        return self.T[i].parent


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
T = Tree(N)

for i, *c in A:
    c = c[1:]
    T.set_children(i, c)
T.set_depth()

for i in range(N):
    p = T.parent_of(i)
    d = T.depth_of(i)
    t = T.type_of(i)
    c = T.children_of(i)
    print(f'node {i}: parent = {p}, depth = {d}, {t}, {c}')

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)

def main():
    N = int(input())
    node_attr_list = [[int(item) for item in input().split()] for _ in range(N)]

    tree = [[0, -1, 0, False, False] for _ in range(N)] 
    for node_attr in node_attr_list:
        tree[node_attr[0]][0] = node_attr[0]

        if node_attr[1] != 0:
            tree[node_attr[0]][3] = node_attr[2:]
        else:
            tree[node_attr[0]][3] = False

    def dfs(node, depth, parent, children):
        
        tree[node][4] = True
        tree[node][1] = parent
        tree[node][2] = depth
        if children:
            for item in children:
                dfs(item, depth+1, node, tree[item][3])
        else:
            return

    def all(iterable):
        for element in iterable:
            if not element[4]:
                return False
        return True

    

    for i in range(N):
        
        
        for j in range(N):
            tree[j][4] = False
        dfs(i, 0, -1, tree[i][3])
        
        
        if all(tree):
            break



    for node in tree:
        print('node {}:'.format(node[0]), end=' ')
        print('parent =', node[1], end=', ')
        print('depth =', node[2], end=', ')
        if node[1] == -1:
            print('root', end=', ')
        elif not node[3]:
            print('leaf', end=', ')
        else:
            print('internal node', end=', ')

        if node[3]:
            print(node[3])
        else:
            print([])

if __name__ == "__main__":
    main()

Solution (Python):

n = int(input())
class Node:
  def __init__(self):
    self.p = -1 
    self.l = None 
    self.r = None 

T = [Node() for _ in range(n)]
D = [0]*n

def rec(u,p):
  D[u] = p
  if T[u].r != None: rec(T[u].r,p)
  if T[u].l != None: rec(T[u].l,p+1)

for i in range(n):
    a = input().split()
    v = int(a[0])
    for j,c in enumerate(map(int,a[2:])):
      if j == 0: T[v].l = c
      else: T[pre].r = c
      pre = c
      T[c].p = v

for i in range(n):
  if T[i].p == -1 : r = i
import sys  
sys.setrecursionlimit(150000)
rec(r,0)
for i in range(n):
  if T[i].p == -1:
    kind = "root"
  elif T[i].l != None: kind = "internal node"
  else: kind = "leaf"
  c = []
  n = T[i].l
  while n != None:
    c.append(n)
    n = T[n].r
  print("node {}: parent = {}, depth = {}, {}, {}"
        .format(i,T[i].p,D[i],kind,c))

Solution (Python):
class Node():
    def __init__(self, p, l, r, deg):
        self.parent = p
        self.left = l
        self.right = r
        self.deg = deg

def GetDepth(T, u):
    d = 0
    while T[u].parent != -1:
        u = T[u].parent
        d += 1
    return d

def SetDepth(D, T, u, p):
    D[u] = p
    if T[u].right != -1:
        SetDepth(D, T, T[u].right, p)
    if T[u].left != -1:
        SetDepth(D, T, T[u].left, p + 1)

def GetChildren(T, u):
    children = list()
    c = T[u].left
    while c != -1:
        children.append(str(c))
        c = T[c].right
    
    return children

def Main():

    n = int(input())

    T = [Node(-1, -1, -1, 0) for i in range(n)]
    D = [0]*n

    for i in range(n):
        node_id, k, *children = map(int, input().split())
        T[node_id].deg = k

        if k > 0 :
            T[node_id].left = children[0]

            for i in range(k):
                T[children[i]].parent = node_id
                
                if i + 1 <= k - 1:
                    T[children[i]].right = children[i + 1]

    for i in range(len(T)):
        D[i] = GetDepth(T, i)

    for i in range(len(T)):
        t = T[i]
        node_type = ""

        if t.parent == -1:
            node_type = "root"
        elif t.deg == 0:
            node_type = "leaf"
        else:
            node_type = "internal node"

        print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(i, t.parent, D[i], node_type, "[" + ", ".join(GetChildren(T, i)) + "]"))

Main()

Solution (Python):
class Node(object):
    def __init__(self):
        self.id = None
        self.parent = -1
        self.children = None
        self.depth = -1


if __name__ == "__main__":
    n = int(input())
    Nodes = [Node() for _ in range(n)]
    for _ in range(n):
        inputs = list(map(int,input().split()))
        id = inputs[0]
        k = inputs[1]
        chilren = inputs[2:]
        Nodes[id].id = id
        Nodes[id].children = chilren
        for child in chilren:
            Nodes[child].parent = id
    
    root_id = -1
    for node in Nodes:
        if node.parent == -1:
            root_id = node.id
            node.depth = 0

    node_stack = [Nodes[root_id]]
    visit_node_id = {}
    out_str = [""]*n
    while len(node_stack) > 0 or len(visit_node_id) != n:
        node = node_stack.pop()
        visit_node_id[node.id] = 1

        id = node.id
        parent = node.parent
        depth = node.depth
        node_type = ""
        if parent == -1:
            node_type = "root"
        elif node.parent > -1 and len(node.children)>0:
            node_type = "internal node"
        elif node.parent > -1 and len(node.children) == 0:
            node_type = "leaf"
        children = node.children
        out_str[node.id] = "node "+str(id)+": parent = "+str(parent)+", depth = "+str(depth)+", "+node_type+", "+str(children)

        for child in node.children:
            if Nodes[child].id not in visit_node_id:
                Nodes[child].depth = node.depth+1
                node_stack.append(Nodes[child])
    
    for answer in out_str:
        print(answer)

Solution (Python):
class TreeNode():

  def __init__(self, val, parent=-1):
    self.val = val
    self.children = []
    self.parent_val = parent
    self.depth = None

  def node_type(self):
    if self.depth == 0:
      return "root"
    elif len(self.children) > 0:
      return "internal node"
    else:
      return "leaf"

  def children_values(self):
    return [ c.val for c in self.children ]

  def __str__(self):
    return "node {0}: parent = {1}, depth = {2}, {3}, {4}".format(str(self.val), str(self.parent_val), str(self.depth), self.node_type(), self.children_values())

def calc_depths(node, level):
  if node is None: return 
  node.depth = level
  for ch in node.children:
    calc_depths(ch, level+1)

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

for i in range(num):
  ins = list(map(int, input().split()))
  val = ins[0]

  if nodes.get(ins[0]) is None:
    nodes[val] = TreeNode(val)

  n = nodes[val]
  if ins[1] > 0:
    for j in ins[2:]:
      nodes.setdefault(j, TreeNode(j, n.val))
      n.children.append(nodes[j])
      nodes[j].parent_val = n.val

parent = [node for node in nodes.values() if node.parent_val == -1][0]
calc_depths(parent, 0)
sort_nodes = sorted(nodes.items(), key=lambda x:x[0] )

for _, node in sort_nodes:
  print(node)

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):
class Node:
    def __init__(self):
        """
        parent: Parent of the node
        left: Child of the node. THe most left
        right: Sibling of the note. The node next to the node (right side)
        """
        self.parent = None
        self.left = None
        self.right = None
        self.id = None
        self.depth = None
        self.type = None
    def __str__(self):
        if self.type == 'root':
            return 'parent = ' + str(-1) + ', depth = ' + str(self.depth) + ', ' + self.type
        else:
            return 'parent = ' + str(self.parent.id) + ', depth = ' + str(self.depth) + ', ' + self.type

def getDepth(node):
    """
    :param node: node
    :return: depth of the node (int)
    """
    depth = 0
    while node.parent is not None:
        node = node.parent
        depth += 1
    return depth

def getType(node):
    """
    :param node: node
    :return: node type (string)
    """
    if node.parent is None:
        return 'root'
    elif node.left is None:
        return 'leaf'
    else:
        return 'internal node'

def getChildren(node):
    """
    :param node: node
    :return: childrent of the node (list)
    """
    children = []
    result = [] 
    child = node.left
    while child is not None:
        children.append(child)
        child = child.right
    if not children:
        return '[]'
    for i in children:
        result.append(i.id)
    return result

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

for i in range(n):
    id, k, *c = map(int, input().split())
    
    if id not in nodesDic.keys():
        node = Node()
        nodesDic[id] = node
        node.id = id
    else:
        node = nodesDic[id]

    
    if not c:
        pass
    else:
        
        for j in range(len(c)-1, -1, -1): 
            if c[j] not in nodesDic.keys():
                childNode = Node()
                nodesDic[c[j]] = childNode
                childNode.id = c[j]

            nodesDic[c[j]].parent = node
            if len(c) == 1 or j == len(c)-1: 
                pass
            else:
                nodesDic[c[j]].right = nodesDic[c[j+1]]
        node.left = nodesDic[c[0]]

for i in range(n):
    node = nodesDic[i]
    node.depth = getDepth(node)
    node.type = getType(node)
    children = getChildren(node)
    print('node', str(i) + ':', end=' ')
    print(node, end=', ')
    print(children)

Solution (Python):
from collections import defaultdict as dd
dicPar = dd(lambda: -1)
dicChild = dd(lambda: [])

n = int(input())
for i in range(n):
  i = list(map(int, input().split()))
  id, k, C = i[0], i[1], i[2:]
  dicChild[id] = C
  for j in range(k):
    dicPar[C[j]] = id



def depth(dicPar, id):
  if dicPar[id] == -1:
    return 0
  else:
    return depth(dicPar, dicPar[id]) + 1

def nodeType(dicPar, dicChild, id):
  if dicPar[id] == -1:
    return "root"
  elif len(dicChild[id]) == 0:
    return "leaf"
  else:
    return "internal node"


for id in range(n):
  print("node {}: parent = {}, depth = {}, {}, {}".format(id, dicPar[id], depth(dicPar, id), nodeType(dicPar, dicChild, id), dicChild[id]))

Solution (Python):



class Node:
    def __init__(self, id):
        self.id = id
        self.children = []
        self.parent = -1
        self.depth = 0
        self.ntype = None
    
    def __str__(self):
        return 'node {}: parent = {}, depth = {}, {}, {}'\
            .format(self.id, self.parent, self.depth, self.ntype, self.children)

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

for _ in range(N):
    elm = [int(i) for i in input().split()]
    if elm[1] > 0:
        nodes[elm[0]].children = elm[2:]
        nodes[elm[0]].ntype = 'internal node'
        for n in elm[2:]:
            nodes[n].parent = elm[0]
    else:
        nodes[elm[0]].ntype = 'leaf'

root = 0
for node in nodes:
    if node.parent == -1:
        node.ntype = 'root'
        root = node.id
        break
        
def dfs(id, depth):
    node = nodes[id]
    node.depth = depth
    if node.children:
        for child in node.children:
            dfs(child, depth+1)
    else:
        return

dfs(root, 0)

for node in nodes:
    print(node)

Solution (Python):
from collections import OrderedDict

n = int(input())

A = OrderedDict()

for _ in range(n):
    tmp = list(map(int, input().split()))
    node_id = tmp[0]
    k = tmp[1]
    children = tmp[2:]

    node = {}
    node['parent'] = -1
    node['children'] = children
    A[node_id] = node


for node_id, node in A.items():
    for child_id in node['children']:
        A[child_id]['parent'] = node_id


for node_id, node in A.items():
    depth = 0
    parent = node['parent']
    while parent != -1:
        depth += 1
        parent = A[parent]['parent']
    node['depth'] = depth

    if depth == 0:
        node['type'] = 'root'
    elif len(node['children']) == 0:
        node['type'] = 'leaf'
    else:
        node['type'] = 'internal node'

A = OrderedDict(
    sorted(A.items(), key=lambda x: x[0])
)

for key, value in A.items():
    print("node {}: parent = {}, depth = {}, {},"
          .format(
              key,
              value['parent'],
              value['depth'],
              value['type'],
          ),
          end="")
    print(" [", end="")
    print(', '.join(map(str, value['children'])), end="")
    print("]")

Solution (Python):
class Tree:
    def __init__(self,n):
        self.ver=[[] for _ in range(n)]
        self.par=[-1 for _ in range(n)]
    
    def unite(self,x,y):
        self.ver[x].append(y)
        self.ver[y].append(x)

        self.par[y]=x

    def getdepth(self,i):
        ret=0
        while True:
            if self.par[i]==-1:
                return ret
            else:
                i=self.par[i]
                ret+=1

        
N=int(input())
T=Tree(N)
for _ in range(N):
    i,m,*chi=map(int,input().split())
    for j in chi:
        T.unite(i,j)




for i in range(N):
    ans=''
    ans+='node %i: '%i
    ans+='parent = %i, '%T.par[i]
    ans+='depth = %i, '%T.getdepth(i)

    kind=''
    if T.par[i]==-1:
        kind+='root'
    elif len(T.ver[i])==1:
        kind+='leaf'
    else:
        kind+='internal node'
    ans+=kind+', '
    ans+=str(list(v for v in T.ver[i] if v!=T.par[i]))
    print(ans)

Solution (Python):
from collections import defaultdict

n = int(input())
nodes = {}
for _ in range(n):
    id_, _k, *c = map(int, input().split())
    nodes[id_] = c
root = set(nodes.keys())
for v in nodes.values():
    root -= set(v)
root = root.pop()
ans = defaultdict(dict)


def solve(id_, depth=0):
    children = nodes[id_]
    type_ = "internal node" if children else "leaf"
    ans[id_].update({"depth": depth, "type": type_, "children": children})
    for child in children:
        ans[child].update({"parent": id_})
        solve(child, depth + 1)


solve(root)
ans[root].update({"parent": -1, "type": "root"})
for k in sorted(ans):
    n = ans[k]
    print(
        "node {}: parent = {}, depth = {}, {}, [{}]".format(
            k,
            n["parent"],
            n["depth"],
            n["type"],
            ", ".join([str(i) for i in n["children"]]),
        )
    )

Solution (Python):
class node:
    def __init__(self, s):
        self.id = int(s.split()[0])
        self.dim = int(s.split()[1])
        self.child_ids = None
        if self.dim>0:
            self.child_ids = list(map(int, s.split()[2:]))
        
        self.pearent = None
        self.child = None
    
    def set_pearent(self, p):
        self.pearent = p
    
    def set_depth(self, d):
        self.depth = d
    
    def set_kind(self, k):
        self.kind = k
    
    def __repr__(self):
        str_node = 'node ' + str(self.id) + ': '
        str_pearent = 'parent = ' + str(self.pearent if self.pearent is not None else -1)
        str_depth = 'depth = ' + str(self.depth)
        str_kind = self.kind
        str_child = '[' + ', '.join([str(i) for i in self.child_ids] if self.child_ids is not None else '') + ']'
        return str_node + ', '.join([str_pearent, str_depth, str_kind, str_child])
        

n = int(input())
inputs = [input() for i in range(n)]
nodes = [0]*n

for i in inputs:
    nd = node(i)
    nodes[nd.id] = nd
    
for nd in nodes:
    if nd.child_ids:
        for i in nd.child_ids:
            nodes[i].set_pearent(nd.id)
            
def get_depth(idx):
    nd = nodes[idx]
    d = 0
    while nd.pearent is not None:
        nd = nodes[nd.pearent]
        d += 1
     
    nodes[idx].depth = d

def get_kind(idx):
    nd = nodes[idx]
    if nd.pearent is None:
        nd.kind = 'root'
    elif nd.child_ids:
        nd.kind = 'internal node'
    else:
        nd.kind = 'leaf'

for i in range(n):
    get_depth(i)
    get_kind(i)

for nd in nodes:
    print(nd)

Solution (Python):

class Node:
    def __init__(self, id):
        self.id = id
        self.chi_list = []
        self.depth = None
        self.parent = None
    
    def create_out(self, node_map):  
        
        if self.parent is None:
            self.parent = -1

        self.depth = self.get_depth(node_map)
        self.type = self.get_type()

    def get_depth(self, node_map):

        if self.depth is not None:
            return self.depth
        
        if self.parent is None or self.parent == -1:
            return 0

        return node_map.get(self.parent).get_depth(node_map) + 1
    
    def get_type(self):
        if self.parent == -1:
            return 'root'

        return 'internal node' if self.chi_list else 'leaf'

node_num = int(input())
node_map = {}
for id in range(0, node_num):
            node_map[id] = Node(id)

for _ in range(node_num):
    temp = list(map(int, input().split()))
    id = temp[0]
    chi_list = []
    for i in range(2, len(temp)):
        chi_id = temp[i]
        chi_list.append(temp[i])

        chi_node = node_map.get(chi_id)
        chi_node.parent = id
        node_map[chi_id] = chi_node
    
    node = node_map.get(id)
    node.chi_list = chi_list
    node_map[id] = node

for node in list(node_map.values()):
    node.create_out(node_map)
    print('node '+ str(node.id) + ': parent = ' + str(node.parent)\
         + ', depth = ' + str(node.depth) + ', ' + str(node.type) + ', ' + str(node.chi_list))

Solution (Python):
class Tree:
    def __init__(self, n):
        self.nodes = {node: {'parent': None, 'children': [], 'depth': None} for node in range(n)}

    def add_node_with_child(self, node, children):
        for c in children:
            self.nodes[node]['children'].append(c)
            self.nodes[c]['parent'] = node
    
    def get_parent(self, node):
        return self.nodes[node]['parent']

    def get_children(self, node):
        return self.nodes[node]['children']
    
    def get_depth(self, node):
        if self.nodes[node]['depth'] != None:
            return self.nodes[node]['depth']
        elif self.nodes[node]['parent'] == None:
            self.nodes[node]['depth'] = 0
            return 0
        else:
            depth = self.get_depth(self.nodes[node]['parent']) + 1
            self.nodes[node]['depth'] = depth
            return depth


n = int(input())
T = []
for _ in range(n):
    t = list(map(int, input().split()))
    T.append(t)

RootedTree = Tree(n)
for t in T:
    if t[1] == 0:
        continue

    node = t[0]
    children = t[2:]
    RootedTree.add_node_with_child(node, children)

for node in range(n):
    parent = RootedTree.get_parent(node)
    if parent == None:
        parent = -1
    depth = RootedTree.get_depth(node)
    children = RootedTree.get_children(node)
    children = ', '.join(list(map(str, children)))

    if parent == -1:
        node_type = 'root'
    elif children == '':
        node_type = 'leaf'
    else:
        node_type = 'internal node'

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

Solution (Python):
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    from collections import defaultdict

    NIL = -1

    n = int(input())

    
    
    T = defaultdict(lambda: {'p':NIL, 'l':NIL, 'r':NIL})
    D = {}

    
    for _ in range(n):
        id, k, *cc = map(int, input().split())
        if k != 0:
            T[id]['l'] = cc[0]
        else:
            T[id]['l'] = NIL
        r = NIL
        for c in cc[::-1]:
            T[c]['p'] = id
            T[c]['r'] = r
            r = c

    
    
    
    
    def rec(u, p):
        D[u] = p
        l = T[u]['l']
        while l != NIL:
            rec(l, p+1) 
            l = T[l]['r']

    for i, value in T.items():
        if value['p'] == NIL:
            r = i
            break  

    rec(r, 0)

    def print_children(u):
        c = T[u]['l']
        i = 0
        while c != NIL:
            if i == 0:
                i = 1
            else:
                print(', ', end='')
            print(str(c), end='')
            c = T[c]['r']

    for u in range(n):
        value = T[u]
        print('node ' + str(u) + ': ', end='')
        print('parent = ' + str(value['p']) + ', ', end='')
        print('depth = ' + str(D[u]) + ', ',end='')
        if value['p'] == NIL:
            type = 'root'
        elif value['l'] == NIL:
            type = 'leaf'
        else:
            type = 'internal node'
        print(type + ', ', end = '')
        print('[',end = '')
        print_children(u)
        print(']')

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

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

def get_children(node):
    c = node.left_child
    cs = []
    if c is not None:
        cs.append(c)
        c = nodes[int(node.left_child)]
        while c.right_sibling:
            c = c.right_sibling
            cs.append(c)
            c = nodes[int(c)]
    return cs









def set_depth(i, depth):
    if depths[i] or i >= n:
        return
    depths[i] = depth
    node = nodes[i]
    if node.right_sibling:
        set_depth(int(node.right_sibling), depth)
    if node.left_child:
        set_depth(int(node.left_child), depth+1)

def get_root_index():
    for i, node in enumerate(nodes):
        if node.parent == -1:
            return i
            
def get_kind_of_tree(node):
    if node.parent == -1:
        return "root"
    if node.left_child:
        return "internal node"
    return "leaf"

if __name__ == "__main__":
    n = int(input())
    nodes = [Node() for _ in range(n)]
    depths = [None for _ in range(n)]
    for _ in range(n):
        data, number_of_children, *children = input().split()
        node = nodes[int(data)]
        for i, child_data in enumerate(children):
            if i == 0:
                node.left_child = child_data
            else:
                child.right_sibling = child_data
            child = nodes[int(child_data)]
            child.parent = int(data)
    root_node_index = get_root_index()
    set_depth(root_node_index, 0)
    for i, node in enumerate(nodes):
        children = get_children(node)
        print("node {}: parent = {}, depth = {}, {}, [{}]".format(i, node.parent, depths[i], get_kind_of_tree(node), ', '.join(children)))

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


def getdepth(node,node_id):
    d = 0
    while node[node_id].parent != -1:
        node_id = node[node_id].parent
        d += 1
    return d


def getchild(node,node_id):
    if node[node_id].left == -1:
        return []
    ret = [node[node_id].left]
    while node[ret[-1]].right != -1:
        ret.append(node[ret[-1]].right)
    return ret

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


for i in range(N):
    n,k,*child = map(int,input().split())
    if k != 0:
        nodes[n].left = child[0]
        for j in range(len(child)):
            nodes[child[j]].parent = n
            if j != len(child)-1:
                nodes[child[j]].right = child[j+1]

for i in range(N):
    depth = getdepth(nodes,i)
    children = getchild(nodes,i)
    if nodes[i].parent == -1:
        node_type = 'root'
    elif nodes[i].left == -1:
        node_type = 'leaf'
    else:
        node_type = 'internal node'
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i,nodes[i].parent, depth, node_type, children))

Solution (Python):


import sys
sys.setrecursionlimit(2**20)  

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

def get_depth(T: dict, u: int):
    d = 0
    while T[u].parent is not None:
        u = T[u].parent
        d += 1
    return d

D = {}  

def get_all_depth(T: dict, u: int, p: int):
    '''  
    一度にすべてのノードの深さを取得する関数(再帰的に処理を行う)。
    一気に全体の深さを求めるならばこちらの方がオーダーが小さい。
    pは現在扱う深さ
    '''
    D[u] = p
    if T[u].right is not None:
        
        get_all_depth(T, T[u].right, p)
    if T[u].left is not None:
        
        get_all_depth(T, T[u].left, p+1)

def ret_children(T, u):
    children = []
    c = T[u].left
    while c is not None:
        children.append(c)
        c = T[c].right
    return children

def print_for_a_node(T: dict, node: int, D: dict):
    node_type = 'internal node' if T[node].left is not None else 'leaf'
    if T[node].parent is None:
        parent = -1
        node_type = 'root'
    else:
        parent = T[node].parent
    children = ret_children(T, node)

    print(
        f'node {node}: parent = {parent}, depth = {D[node]}, {node_type}, {children}')

N = int(input())
T = {k: Node(None, None, None) for k in range(N)}
for _ in range(N):
    lst = list(map(int, input().split()))
    if lst[1] == 0:  
        continue
    T[lst[0]].left = lst[2]
    T[lst[2]].parent = lst[0]
    prev_sibling = lst[2]  
    for sib in lst[3:]:
        T[prev_sibling].right = sib
        T[sib].parent = lst[0]  
        prev_sibling = sib

for node in range(N):
    if T[node].parent is None:
        get_all_depth(T, node, 0)  
        
        break

for node in range(N):
    print_for_a_node(T, node, D)