Problem:

Rooted Trees

A graph G = (V, E) is a data structure where V is a finite set of vertices and E is a binary relation on V represented by a set of edges. Fig. 1 illustrates an example of a graph (or graphs).

Fig. 1

A free tree is a connnected, acyclic, undirected graph. A rooted tree is a free tree in which one of the vertices is distinguished from the others. A vertex of a rooted tree is called "node."

Your task is to write a program which reports the following information for each node u of a given rooted tree T:

node ID of u

parent of u

depth of u

node type (root, internal node or leaf)

a list of chidlren of u

If the last edge on the path from the root r of a tree T to a node x is (p, x), then p is the parent of x, and x is a child of p. The root is the only node in T with no parent.

siblings.

-->

A node with no children is an external node or leaf. A nonleaf node is an internal node

The number of children of a node x in a rooted tree T is called the degree of x.

The length of the path from the root r to a node x is the depth of x in T.

Here, the given tree consists of n nodes and evey node has a unique ID from 0 to n-1.

Fig. 2 shows an example of rooted trees where ID of each node is indicated by a number in a circle (node). The example corresponds to the first sample input.

Fig. 2

Input

The first line of the input includes an integer n, the number of nodes of the tree.

In the next n lines, the information of each node u is given in the following format:

id k c1 c2 ... ck

where id is the node ID of u, k is the degree of u, c1 ... ck are node IDs of 1st, ... kth child of u. If the node does not have a child, the k is 0.

Output

Print the information of each node in the following format ordered by IDs:

node id: parent = p, depth = d, type, [c1...ck]

p is ID of its parent. If the node does not have a parent, print -1.

d is depth of the node.

type is a type of nodes represented by a string (root, internal node or leaf). If the root can be considered as a leaf or an internal node, print root.

c1...ck is the list of children as a ordered tree.

Please follow the format presented in a sample output below.

Constraints

1 ≤ n ≤ 100000

Sample Input 1

13
0 3 1 4 10
1 2 2 3
2 0
3 0
4 3 5 6 7
5 0
6 0
7 2 8 9
8 0
9 0
10 2 11 12
11 0
12 0

Sample Output 1

node 0: parent = -1, depth = 0, root, [1, 4, 10]
node 1: parent = 0, depth = 1, internal node, [2, 3]
node 2: parent = 1, depth = 2, leaf, []
node 3: parent = 1, depth = 2, leaf, []
node 4: parent = 0, depth = 1, internal node, [5, 6, 7]
node 5: parent = 4, depth = 2, leaf, []
node 6: parent = 4, depth = 2, leaf, []
node 7: parent = 4, depth = 2, internal node, [8, 9]
node 8: parent = 7, depth = 3, leaf, []
node 9: parent = 7, depth = 3, leaf, []
node 10: parent = 0, depth = 1, internal node, [11, 12]
node 11: parent = 10, depth = 2, leaf, []
node 12: parent = 10, depth = 2, leaf, []

Sample Input 2

4
1 3 3 2 0
0 0
3 0
2 0

Sample Output 2

node 0: parent = 1, depth = 1, leaf, []
node 1: parent = -1, depth = 0, root, [3, 2, 0]
node 2: parent = 1, depth = 1, leaf, []
node 3: parent = 1, depth = 1, leaf, []

Note

You can use a left-child, right-sibling representation to implement a tree which has the following data:

the parent of u

the leftmost child of u

the immediate right sibling of u

Template in C

-->

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
13
0 3 1 4 10
1 2 2 3
2 0
3 0
4 3 5 6 7
5 0
6 0
7 2 8 9
8 0
9 0
10 2 11 12
11 0
12 0


Sample output:
node 0: parent = -1, depth = 0, root, [1, 4, 10]
node 1: parent = 0, depth = 1, internal node, [2, 3]
node 2: parent = 1, depth = 2, leaf, []
node 3: parent = 1, depth = 2, leaf, []
node 4: parent = 0, depth = 1, internal node, [5, 6, 7]
node 5: parent = 4, depth = 2, leaf, []
node 6: parent = 4, depth = 2, leaf, []
node 7: parent = 4, depth = 2, internal node, [8, 9]
node 8: parent = 7, depth = 3, leaf, []
node 9: parent = 7, depth = 3, leaf, []
node 10: parent = 0, depth = 1, internal node, [11, 12]
node 11: parent = 10, depth = 2, leaf, []
node 12: parent = 10, depth = 2, leaf, []

Submission status: Accepted

Solution code:
import sys

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

depthList = []
nodeList = []

def readinput():
    global nodeList
    n=int(input())
    nodeList=[Node() for _ in range(n)]
    for _ in range(n):
        s=list(map(int,input().split()))
        id=s[0]
        deg=s[1]
        child=s[2:]
        if (deg>0):
            nodeList[id].left=child[0]
            for i in range(deg-1):
                nodeList[child[i]].parent=id
                nodeList[child[i]].right=child[i+1]
            nodeList[child[deg-1]].parent=id
    return

def findRoot(nodeList):
    for i, node in enumerate(nodeList):
        if(node.parent==-1):
            return i
    return -1

def setDepth(id,depth):
    #sys.setrecursionlimit(3700)
    global depthList
    global nodeList

    depthList[id]=depth
    r=nodeList[id].right
    #if(r!=-1):
    #    setDepth(r,depth)
    while(r!=-1):
        depthList[r]=depth
        if(nodeList[r].left!=-1):
            setDepth(nodeList[r].left,depth+1)
        r=nodeList[r].right
    l=nodeList[id].left
    if(l!=-1):
        setDepth(l,depth+1)

def nodeType(node):
    if node.parent==-1:
        return 'root'
    elif node.left==-1:
        return 'leaf'
    else:
        return 'internal node'

def childList(p, nodeList):
    child=[]
    c=nodeList[p].left
    while(c!=-1):
        child.append(c)
        c=nodeList[c].right
    return child

def printNodeList(nodeList, depthList):
    for i,node in enumerate(nodeList):
        print('node {}: parent = {}, depth = {}, {}, {}'.format(i,node.parent, depthList[i], nodeType(node), childList(i,nodeList)))

def main():
    global depthList
    global nodeList

    depthList=[0]*len(nodeList)
    root=findRoot(nodeList)
    setDepth(root,0)
    printNodeList(nodeList, depthList)

if __name__=='__main__':
    sys.setrecursionlimit(10000)
    readinput()
    main()

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

def depthcheck(idx, depth):
    global depthlist, childlist
    depthlist[idx]['depth'] = depth + 1
    if childlist[idx] != []:
        for child in childlist[idx]:
            depthcheck(child, depth+1)
    else:
        depthlist[idx]['type'] = 'leaf'

n = int(input())
childlist = [[]]*n
parentlist = [-1]*n
depthlist = [{'depth':0, 'type':'internal node'} for _ in range(n)]
for i in range(n):
    idx, c, *childs = map(int, input().split())
    childlist[idx] = list(childs)
    for childidx in childs:
        parentlist[childidx] = idx

for idx in range(n):
    if parentlist[idx] == -1:
        depthlist[idx]['type'] = 'root'
        for child in childlist[idx]:
            depthcheck(child, 0)
        break
for i in range(n):
    print('node %s: parent = %d, depth = %d, %s, %s'%(i, parentlist[i], depthlist[i]['depth'], depthlist[i]['type'], childlist[i]))

Submission status: Accepted

Solution code:
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 = []
# V個のノードを用意
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("]")

Submission status: Accepted

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

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

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

    r = 0
    tree_list = [Node(-1,-1,-1) for m in range(n)]
    node_list = []
    for i in range(n):
        l = input().split()
        v = int(l[0])
        c_list = [int(l[m]) for m in range(2,len(l))]
        node_list.insert(v,c_list)
        for ci in range(int(l[1])):
            if ci == 0:
                tree_list[v].left = c_list[ci]
            else:
                tree_list[c].right = c_list[ci]
            c = c_list[ci]
            tree_list[c].parent = v

    for i,t in enumerate(tree_list):
        d = get_depth(i,tree_list)
        tree_type = ''
        if tree_list[i].parent == -1:
            tree_type = 'root'
        elif tree_list[i].left == -1:
            tree_type = 'leaf'
        else:
            tree_type = 'internal node'

        n = ', '.join([str(x) for x in node_list[i]])

        print('node {}: parent = {}, depth = {}, {}, [{}]'.format(i,t.parent,d,tree_type,n))

Submission status: Accepted

Solution code:
n = int(input()) # n = จำนวน node ทั้งหมด
rt = {}
cs = [0 for i in range(n)]
for i in range(n):
    #เก็บค่าแต่ละตัวใน list
    #ตนข้อมูลที่ 0 คือ node
    #ตนข้อมูลที่ 1 คือ จำนวน children ของ node นั้นๆ
    #ตนที่2เป็นต้นไปคือ children
    id, k, *c = list(map(int, input().split()))
    for j in c:
    #การ update value ใน key เช่น node 0 มี 1 4 10 เก็บค่าใน dict
        rt[j] = id
        #print(rt)
    cs[id] = c
    
    #วน loop ตามจำนวน node
for i in range(n):
    print("node " + str(i) + ": parent = ", end = "")
    p = [i] # i ตั้งแต่ 0ถึงจนnode
    #check ว่าเป็น root หรือไม่
    while True:
        try:
            #เช่น rt 0 ก็เป็น 1 กับ 2
            #แล้วทำการ append 1 กับ 2
            
            #ถ้าเป็น root จะไม่ทำตรงนี้ เพราะไม่มี key ไหน = 0 จะ break
            #check จากตัวแรกใน dict ว่าถ้าเลขตรงกับ node
            #ก็จะ append แต่ถ้าไม่ ก็ไม่ append ทำให้ len(p)=1
            p.append(rt[p[-1]])
        except:
            break
    #เมื่อเป็น root parent = -1    
    if len(p) == 1:
        print("-1, depth = 0, root, ", end = "")
        print(cs[i])
    
    else:
        print(str(p[1]) + ", depth = " + str(len(p) - 1), end = "")
        #ถ้าไม่ได้เป็น root และกิ่งเป็น null     
        if cs[i] == []:
            print(", leaf, []")
        #ถ้าไม่ได้เป็น root และกิ่งนั้นมี children       
        else:
            print(", internal node, ",end = "")
            print(cs[i])

Submission status: Accepted

Solution code:
def depth(id):
    depth = 0
    target_id = id
    while nodes[target_id][0] !=-1:
        depth += 1
        target_id = nodes[target_id][0]
    return depth

nodes = dict()
n = int(input())
for _ in range(n):
    id,k,*c_list = list(map(int, input().split()))
    if id not in nodes:
        nodes[id] = (-1, list())
    node = nodes[id]
    node = (node[0], c_list)
    nodes[id] = node
    for child_id in c_list:
        if child_id not in nodes:
            nodes[child_id] = (-1, list())
        child_node = nodes[child_id]
        child_node = (id, child_node[1])
        nodes[child_id] = child_node

for id, node in sorted(nodes.items()):
    node_type = "root" if node[0] == -1 else "internal node" if node[1] else "leaf"
    print(f"node {id}: parent = {node[0]}, depth = {depth(id)}, {node_type}, {node[1]}")

Submission status: Accepted

Solution code:
class tree:
    def __init__(self, parts):
        self.num_parts = len(parts)
        self.nodes = []
        for i in range(self.num_parts):
            self.nodes.append(node(parts[i][0],parts[i][1],parts[i][2]))

    def set_parents(self):
        for i in range(self.num_parts):
            for child_id in self.nodes[i].children_id:
                self.nodes[child_id].set_parent(i)

    def set_type(self):
        for i in range(self.num_parts):
            self.nodes[i].check_type()
    def set_depth(self):
        for i in range(self.num_parts):
            if self.nodes[i].type == "root":
                parents = [self.nodes[i]]
                depth = 0
                self.nodes[i].set_depth(depth)
                for j in range(20):
                    depth += 1
                    children = []
                    for parent in parents:
                        for child_id in parent.children_id:
                            self.nodes[child_id].set_depth(depth)
                            children.append(self.nodes[child_id])
                    parents = children
                        
class node:
    def __init__(self, id, k, children):
        self.id = id
        self.k = k
        self.children_id = children
        self.depth = -1
        self.parent_id = -1
        self.type = "leaf"
        
    def set_parent(self,parent_id):
        self.parent_id = parent_id

    def check_type(self):
        if self.parent_id == -1:
            self.type = "root"
        elif self.children_id == []:
            self.type = "leaf"
        else:
            self.type = "internal node"
            
    def set_depth(self,depth):
        self.depth = depth
        
n = int(input())
obj = [[0,0,[]] for i in range(n)]
for i in range(n):
    inp = list(map(int, input().split()))
    obj[inp[0]][0] = inp[0]
    obj[inp[0]][1] = inp[1]
    if inp[1]>0:
        obj[inp[0]][2] = inp[2:]

new_tree = tree(obj)
new_tree.set_parents()
new_tree.set_type()
new_tree.set_depth()

for i in range(n):
    print("node {}: parent = {}, depth = {}, {}, {}".format(i, new_tree.nodes[i].parent_id, new_tree.nodes[i].depth, new_tree.nodes[i].type, new_tree.nodes[i].children_id))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(8388608)
N=int(input())
nodes=[None]*(N+1)
childs=[]
oya=[]
class node_tree:
    def __init__(self,node):
        self.node=node
        self.left=None
        self.right=None
        self.oya=None
for i in range(N):
    node,child_num,*child=list(map(int,input().split()))
    if nodes[node] is not None:
        parent=nodes[node]
    else:
        parent=node_tree(node)
    if child_num>=1:
        if nodes[child[0]] is not None:
            tree=nodes[child[0]]
        else:
            tree=node_tree(child[0])
        parent.left=tree
        tree.oya=parent
        nodes[node]=parent
        nodes[child[0]]=tree
        for j in range(len(child)-1):
            if nodes[child[j]] is not None:
                treesecond=nodes[child[j]]
            else:
                treesecond=node_tree(child[j])
            if nodes[child[j+1]] is not None:
                treenext = nodes[child[j+1]]
            else:
                treenext = node_tree(child[j+1])
            treesecond.oya=parent
            treenext.oya=parent
            treesecond.right=treenext
            nodes[child[j]]=treesecond
            nodes[child[j+1]]=treenext
    else:
        parent.left=nodes[-1]
        nodes[node]=parent
def oyasearch(u):
    if u.oya is not None:
        oyasearch(u.oya)
    else:
        oya.append(u.node)
oyasearch(nodes[0])
dep=[0]*N
parent_list=[None]*N
parent_list[oya[0]]=-1
child_list=[]
def search_depth(u,p):
    dep[u.node]=p
    if u.right is not None:
        parent_list[u.right.node]=parent_list[u.node]
        search_depth(u.right,p)
    if u.left is not None:
        parent_list[u.left.node]=u.node
        search_depth(u.left,p+1)
search_depth(nodes[oya[0]],0)
def child_search(u,c):
    c.append(u.node)
    if u.right is not None:
        child_search(u.right,c)
for i in range(N):
    c=[]
    if nodes[i].left is not None:
        child_search(nodes[i].left,c)
    child_list.append(c)
word_list=["internal node","leaf"]
for i in range(N):
    if i==oya[0]:
        print(("node %d: parent = %d, depth = %d, root," % (nodes[oya[0]].node, parent_list[oya[0]], dep[oya[0]])),
              child_list[oya[0]])
    else:
        if len(child_list[i])!=0:
            word=word_list[0]
        else:word=word_list[1]
        print(("node %d: parent = %d, depth = %d, %s," % (nodes[i].node, parent_list[i], dep[i],word)), child_list[i])

Submission status: Accepted

Solution code:
n = int(input())

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

def cal_depth (node,x):
    node.depth = x

    for children_id in node.children:
        cal_depth(nodes[children_id],x+1)


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

for i in range(n):
    table = list(map(int,input().split()))
    node_id = table[0]
    num = table[1]

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


for node in nodes:
    if node.parent_id == -1:
        cal_depth(node,0)
        break

for i in range(n):

    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("]")

Submission status: Accepted

Solution code:
# 根付き木の表現
class Node:
    def __init__(self):
        self.parent_id = -1
        self.depth = 0
        self.children = []

global nodes

V = int(input())

# 空のノードで初期化
nodes = []
for _ in range(V):
    node = Node()
    nodes.append(node)

# 親子関係を入力
for _ 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

# 根を探して深さを計算
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)

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("]")

Submission status: Accepted

Solution code:
n = int(input())
root = {}
children = [0] * n

for i in range(n):
  id, k, *c = list(map(int, input().split()))
  for j in c:
    root[j] = id
  children[id] = c

for i in range(n):
  print('node {}: parent = '.format(str(i)), end='')
  p = [i]
  while True:
    try:
      p.append(root[p[-1]])
    except:
      break
  if len(p) == 1:
    print('-1, depth = 0, root, {}'.format(children[i]))
  else:
    print('{}, depth = {}'.format(str(p[1]), str(len(p) - 1)), end='')
    if children[i] == []:
      print(', leaf, []')
    else:
      print(', internal node, {}'.format(children[i]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100010)
n=int(input())
childs_list=[[] for _ in range(n)]
for i in range(n):
    tmp=list(map(int, input().split()))
    childs_num=tmp[1]
    node_id=tmp[0]
    childs_list[node_id].extend(tmp[2:])

class Tree:
    def __init__(self,childs_list):
        self.n=len(childs_list)
        self.parent=[-1]*self.n
        self.first_child=[-1]*self.n
        self.next_child=[-1]*self.n
        for i in range(self.n):
            childs_num=len(childs_list[i])
            if childs_num == 0:
                continue
            self.first_child[i]=childs_list[i][0]
            for j in range(childs_num):
                self.parent[childs_list[i][j]]=i
                if j < childs_num-1:
                    self.next_child[childs_list[i][j]]=childs_list[i][j+1]
        self.node_type=[0]*n
        for i in range(self.n):
            if self.parent[i]==-1:
                self.node_type[i]="root"
                self.root=i
            elif self.first_child[i]==-1:
                self.node_type[i]="leaf"
            else:
                self.node_type[i]="internal node"
        self.d=[-1]*self.n

    def parent_of(self,id):
        return self.parent[id]
    
    def childs_of(self,id):
        childs=[]
        if self.first_child[id]==-1:
            return childs
        else:
            now_child=self.first_child[id]
            while 1:
                childs.append(now_child)
                if self.next_child[now_child] == -1:
                    break
                else:
                    now_child=self.next_child[now_child]
        return childs
    
    def set_depth(self,id,d):
        if id != -1:
            self.d[id]=d
            self.set_depth(self.next_child[id],d)
            self.set_depth(self.first_child[id],d+1)


tree=Tree(childs_list)
tree.set_depth(tree.root,0)

for i in range(n):
    print("node {}: ".format(i),end="")
    print("parent = {}, ".format(tree.parent_of(i)),end="")
    print("depth = {}, ".format(tree.d[i]),end="")
    print("{}, ".format(tree.node_type[i]),end="")
    print(tree.childs_of(i))

Submission status: Accepted

Solution code:
n = int(input())
parent = [-1 for i in range(n)]
depth = [-1 for i in range(n)]
G = [[] for i in range(n)]
for _ in range(n):
    cin = input().split()
    id, k = int(cin[0]), int(cin[1])
    children = list(map(int, cin[2:]))
    G[id] = children
    for child in children:
        parent[child] = id
for i in range(n):
    if parent[i] == -1:
        depth[i] = 0
        que = [i]
        while len(que) > 0:
            r = que.pop()
            for child in G[r]:
                depth[child] = depth[r] + 1
                que.append(child)
        break
for i in range(n):
    T = ''
    if parent[i] == -1:
        T = 'root'
    elif len(G[i]) == 0:
        T = 'leaf'
    else:
        T = 'internal node'
    print(f'node {i}: parent = {parent[i]}, depth = {depth[i]}, {T}, {G[i]}')

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, p, l, r):
        self.p, self.l, self.r = p, l, r

N = int(input())
T = [Node(None, None, None) for _ in range(N)]

def get_depth(i):
    depth = 0
    while T[i].p != None:
        depth += 1
        i = T[i].p
    return depth

def get_children(i):
    children = []
    child = T[i].l
    while child != None:
        children.append(child)
        child = T[child].r
    return children

for _ in range(N):
    node, num, *children = map(int, input().split())
    if len(children) > 0:
        T[node].l = children[0]
        for i, child in enumerate(children):
            if len(children) - 1 < i + 1:
                break
            T[child].r = children[i + 1]
        for child in children:
            T[child].p = node

for i, t in enumerate(T):
    parent = t.p if t.p != None else -1
    depth = get_depth(i)
    if t.p == None:
        node = 'root'
    elif t.l == None:
        node = 'leaf'
    else:
        node = 'internal node'
    children = get_children(i)
    print('node {}:'.format(i), end=' ')
    print('parent = {},'.format(parent), end=' ')
    print('depth = {},'.format(depth), end=' ')
    print('{},'.format(node), end=' ')
    print(children)

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, value, parent=None):
        self.value = value
        self.parent = parent
        self.left_child = None
        self.right_sibling = None

    def set_left_child(self, child):
        self.left_child = child

    def set_right_sibling(self, sibling):
        self.right_sibling = sibling

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

    def get_depth(self):
        if self.parent is None:
            return 0

        return self.parent.get_depth() + 1

    def get_childs(self):
        r = []
        child = self.left_child
        while child is not None:
            r.append(child.value)
            child = child.right_sibling
        return r

    def print(self):
        childs = self.get_childs()
        depth = self.get_depth()
        p = str(self.parent.value if self.parent else -1)
        t = 'leaf'
        if self.parent is None:
            t = 'root'
        elif childs and self.parent:
            t = 'internal node'

        print('node ' + str(self.value) + ': parent = ' + p + ', depth = ' + str(depth) + ', ' + t + ', ' + str(childs))


n = int(input())
m = {}
for _ in range(n):
    l = list(map(int, input().split()))
    p = m[l[0]] if m.get(l[0]) else Node(l[0])
    if l[1] >= 1:
        sibling = None
        for i in range(2, 2 + l[1])[::-1]:
            node = m[l[i]] if m.get(l[i]) else Node(l[i])
            node.right_sibling = sibling
            node.parent = p
            sibling = node
            m[node.value] = node
        p.left_child = node
    m[l[0]] = p

for i in range(n):
    m[i].print()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

#存在しないノードにはNILを割り当てる
NIL = -1

n = int(input())

#左子右兄弟表現で根つき木を実装していく
class Node:
    def __init__(self, p, l, r):
        self.p = p
        self.l = l
        self.r = r
        self.d = 0
        self.t = 'undifined'
        self.c = []

#T[i]にはノードiの情報を保持する
T = [Node(NIL, NIL, NIL) for _ in range(n)]

#ノードの情報を受け取りTに保持していく
for _ in range(n):
    data = [int(i) for i in input().split()]
    node_id = data[0]
    node_d = data[1]
    child = data[2:]
    if len(child) > 0:
        T[node_id].l = child[0]
    for i in range(len(child)):
        if i < len(child)-1:
            T[child[i]].r = child[i+1]
        T[child[i]].p = node_id
        T[node_id].c.append(child[i])



#仕様
#ノード番号　親ノードの番号　ノードのふかさ　ノードの種類　子ノードのリスト　をノード0から順に出力する

#ノードの深さを求める関数
def setDepth(root_id, depth):
    T[root_id].d = depth
    l = T[root_id].l
    r = T[root_id].r
    if l != NIL:
        setDepth(l, depth+1)
    if r != NIL:
        setDepth(r, depth)

#rootの番号を求める関数
def getRoot():
    for i in range(n):
        p = T[i].p
        if p == NIL:
            return i

#ノードの種類を求める関数
def setNodeType(node_id):
    #親がNILならばrootで確定する
    if T[node_id].p == NIL:
        T[node_id].t = 'root'
        return
    #親が存在して、子が存在しない場合はleaf
    if T[node_id].l == NIL:
        T[node_id].t = 'leaf'
        return 
    #それ以外はinternal node
    T[node_id].t = 'internal node'

def allSetNodeType():
    for i in range(n):
        setNodeType(i)

def outPutNodeInfo(node_id, p_node_id, depth='nil', node_type='nil', child_list='nil'):
    res = "node {}: parent = {}, depth = {}, {}, {}".format(node_id, p_node_id, depth, node_type, child_list)
    print(res)


#問題の答えを出力するための関数
def outPutAns():
    for i in range(n):
        node_id = i
        p_node_id = T[i].p
        depth = T[i].d
        node_type = T[i].t
        child_list = T[i].c
        outPutNodeInfo(node_id, p_node_id, depth, node_type, child_list)



def main():
    setDepth(getRoot(), 0)
    allSetNodeType()
    outPutAns()
main()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self,parent = -1,childs = []):
        self.p = parent
        self.c = childs


def main():
    n = int(input())
    t = [Node() for _ in range(n)]
    for i in range(n):
        b = list(map(int,input().split()))
        t[b[0]].c = b[2:]
        for d in b[2:]:t[d].p = b[0]

    def depth(i):
        res = 0
        while t[i].p!=-1:
            i = t[i].p
            res+=1
        return res

    for i in range(n):
        print('node %d: parent = %d, '%(i,t[i].p),end='')
        print('depth = %d, '%depth(i),end='')
        if t[i].p==-1      :print ('root,',t[i].c)
        elif len(t[i].c)!=0:print ('internal node,',t[i].c)
        else               :print ('leaf,',t[i].c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
NIL = -1


class Node():
  def __init__(self, nid):
    self.nid = nid
    self.parent = -1
    self.left = self.right = None
    self.depth = None

  def __str__(self):

    template = "node {}: parent = {}, depth = {}, {}, {}"
    if self.parent == -1:
      ntype = "root"
    elif self.left is None:
      ntype = "leaf"
    else:
      ntype = "internal node"

    children = self.get_childs()
    chidlren = ", ".join(map(str,children))
    parend_id = self.parent.nid if self.parent != -1 else -1
    return template.format(
      self.nid, parend_id, self.depth, ntype, children
    )
  
  def get_childs(self):
    c = self.left
    children = []
    while c is not None:
      children.append(c.nid)
      c = c.right
    return children
  
      


def set_depth(node, p):
  node.depth = p
  if node.right is not None:
    set_depth(node.right, p)
  if node.left is not None:
    set_depth(node.left, p+1)

def main():
  n = int(input())
  T = [Node(i) for i in range(n)]
  for i in range(n):
    tmp = list(map(int, input().split()))
    nid = tmp[0]
    k = tmp[1]
    c = tmp[2:]
    if len(c) == 0:
      continue
    T[nid].left = T[c[0]]
    for idx in c:
      T[idx].parent = T[nid]
    for j in range(k-1):
      T[c[j]].right = T[c[j+1]]
  for i in range(n):
    if T[i].parent == -1:
      break
  set_depth(T[i], 0)
  for x in T:
    print(x)



if __name__ == "__main__":
    import io, sys
    sys.setrecursionlimit(200000)
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2 ** 20)

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

    def __repr__(self):
        return '<Node object: parent={}, left={}, right={}>' .format(self.parent, self.left, self.right)


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


def get_children(u):
    res = []
    c = T[u].left
    while c is not None:
        res.append(c)
        c = T[c].right
    return res


def get_type(node):
    if node.parent is None:
        return 'root'
    elif node.left is None:
        return 'leaf'
    else:
        return 'internal node'


def get_parent(node):
    return -1 if node.parent is None else node.parent


n = int(input())
T = [Node() for i in range(n)]
for _ in range(n):
    line = list(map(int, input().split()))
    i, k = line[:2]
    if k:
        T[i].left = line[2]
        prev = None
        for c in line[2:]:
            T[c].parent = i
            if prev:
                T[prev].right = c
            prev = c

D = [0] * n
for i in range(n):
    if T[i].parent is None:
        set_depth(i, 0)
        break

for i in range(n):
    print('node {}: parent = {}, depth = {}, {}, {}'.format(
        i, get_parent(T[i]), D[i], get_type(T[i]), get_children(i)))