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
sys.setrecursionlimit(2**20)
n = int(input())
NIL = -1
class node:
    def __init__(self,parent,left,right):
        self.parent = parent
        self.left = left
        self.right = right
T = [node(NIL,NIL,NIL) for _ in range(n)]
firstid = 0
for _ in range(n):#入力の一例
    A = list(map(int,input().split()))
    id = A[0]
    if n == 1:
        firstid = id
    k = A[1]
    if k != 0:
        chil = A[2:2+k]
        T[id].left = chil[0]
        for i in range(k):
            if i != k-1:
                T[chil[i]].right = chil[i+1]
                T[chil[i]].parent = id
            else:
                T[chil[i]].parent = id            
D = [0]*n
def setDepth(u,p):#uはノードの番号、pはノードpの深さ。
    D[u] = p      #uより右下にあるノードの深さをDに保存し、かえす
    if T[u].right != NIL:
        setDepth(T[u].right,p)
    if T[u].left != NIL:
        setDepth(T[u].left,p+1)
    return D
def getDepth(u):
    d = 0
    while T[u].parent != NIL:
        u = T[u].parent
        d += 1
    return d
def findroot(u): #根をみつける
    while T[u].parent != NIL:
        u = T[u].parent
    return u
def printChildren(u):#番号uのノードの子供をlistでかえす
    child = []
    if T[u].left != NIL:
        c = T[u].left
        while c != NIL:
            child.append(c)
            c = T[c].right
    return child
def ppp():
	for i in range(n):
  		ccc = T[i]
  		print(i,ccc.parent,ccc.left,ccc.right)
#ここからもんだいによってかわる
r = findroot(firstid)
D = setDepth(r,0)
for i in range(n):
    nod = T[i]
    d = getDepth(i)
    s = "internal node"
    if nod.parent == NIL:
        s = "root"
    elif nod.left == NIL:
        s = "leaf"
    child = printChildren(i)
    print(f'node {i}: parent = {nod.parent}, depth = {d}, {s}, {child}')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

class Node:
    def __init__(self):
        self.p = -1
        self.l = -1
        self.r = -1

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

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

def printinfo(u):
    clst = []
    c = T[u].l
    while c != -1:
        clst.append(c)
        c = T[c].r
    if T[u].p == -1: ntype = "root"
    elif T[u].l == -1: ntype = "leaf"
    else: ntype = "internal node"
    print("node {}: parent = {}, depth = {}, {}, {}".format(u,T[u].p,D[u],ntype,clst))

for i in range(n):
    inp = [int(i) for i in input().split()]
    v = inp[0]
    d = inp[1]
    C = inp[2:]
    for j in range(d):
        c = C[j]
        if j == 0: T[v].l = c
        else: T[l].r = c
        l = c
        T[c].p = v
for i in range(n):
    if T[i].p == -1: r = i

rec(r,0)
for i in range(n): printinfo(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 =[]
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:
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}')

Submission status: Accepted

Solution code:
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)] # [node, parent, depth, [*child_node], foot print]
    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):
        # print(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

    # print(node_attr_list)

    for i in range(N):
        # print('dfs',i)
        # print(tree)
        for j in range(N):
            tree[j][4] = False
        dfs(i, 0, -1, tree[i][3])
        # print(tree)
        # print(all(tree))
        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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
class Node:
  def __init__(self):
    self.p = -1 # parent
    self.l = None # left most child
    self.r = None # right sibling

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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 = []
#あらかじめ、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: 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 = [] # list of ids of children
    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())
    # id がすでにあれば既存 node, なければ新規 node 作成
    if id not in nodesDic.keys():
        node = Node()
        nodesDic[id] = node
        node.id = id
    else:
        node = nodesDic[id]

    # c が empty (children なし) のとき
    if not c:
        pass
    else:
        # c の id の node が存在しなければ作成, right, parent を設定
        for j in range(len(c)-1, -1, -1): # c を末尾から読む (right の設定がこの for loop 内で可能(
            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: # c が要素 1 つのみのとき or 最も右側の node のとき
                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)

Submission status: Accepted

Solution code:
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
#print(dicPar)
#print(dicChild)

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"

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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)

Submission status: Accepted

Solution code:
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

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

# depth, type
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("]")

Submission status: Accepted

Solution code:
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)

# print(T.ver)
# print(T.par)

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)

Submission status: Accepted

Solution code:
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"]]),
        )
    )

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# Left-child right-sibling representation
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))

Submission status: Accepted

Solution code:
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))