Problem:
Rooted Trees A graph G = ( V , E ) is a data structure where V is a finite set of vertices and E is a binary relation on V represented by a set of edges. Fig. 1 illustrates an example of a graph (or graphs).   Fig. 1  A free tree is a connnected, acyclic, undirected graph. A rooted tree is a free tree in which one of the vertices is distinguished from the others. A vertex of a rooted tree is called "node." Your task is to write a program which reports the following information for each node u of a given rooted tree T :  node ID of u  parent of u  depth of u  node type (root, internal node or leaf)  a list of chidlren of u  If the last edge on the path from the root r of a tree T to a node x is ( p , x ), then p is the parent of x , and x is a child of p . The root is the only node in T with no parent. A node with no children is an external node or leaf . A nonleaf node is an internal node  The number of children of a node x in a rooted tree T is called the degree of x . The length of the path from the root r to a node x is the depth of x in T . Here, the given tree consists of n nodes and evey node has a unique ID from 0 to n -1. Fig. 2 shows an example of rooted trees where ID of each node is indicated by a number in a circle (node). The example corresponds to the first sample input.   Fig. 2  Input The first line of the input includes an integer n , the number of nodes of the tree. In the next n lines, the information of each node u is given in the following format:  id  k  c 1  c 2 ... c k  where id is the node ID of u , k is the degree of u , c 1 ... c k are node IDs of 1st, ... k th child of u . If the node does not have a child, the k is 0. Output Print the information of each node in the following format ordered by IDs:  node  id : parent = p , depth = d , type , [ c 1 ... c k ]   p is ID of its parent. If the node does not have a parent, print -1 .  d is depth of the node.  type is a type of nodes represented by a string ( root , internal node or leaf ). If the root can be considered as a leaf or an internal node, print root .  c 1 ... c k is the list of children as a ordered tree. Please follow the format presented in a sample output below. Constraints  1 ≤ n ≤ 100000  Sample Input 1 13
0 3 1 4 10
1 2 2 3
2 0
3 0
4 3 5 6 7
5 0
6 0
7 2 8 9
8 0
9 0
10 2 11 12
11 0
12 0 Sample Output 1 node 0: parent = -1, depth = 0, root, [1, 4, 10]
node 1: parent = 0, depth = 1, internal node, [2, 3]
node 2: parent = 1, depth = 2, leaf, []
node 3: parent = 1, depth = 2, leaf, []
node 4: parent = 0, depth = 1, internal node, [5, 6, 7]
node 5: parent = 4, depth = 2, leaf, []
node 6: parent = 4, depth = 2, leaf, []
node 7: parent = 4, depth = 2, internal node, [8, 9]
node 8: parent = 7, depth = 3, leaf, []
node 9: parent = 7, depth = 3, leaf, []
node 10: parent = 0, depth = 1, internal node, [11, 12]
node 11: parent = 10, depth = 2, leaf, []
node 12: parent = 10, depth = 2, leaf, [] Sample Input 2 4
1 3 3 2 0
0 0
3 0
2 0 Sample Output 2 node 0: parent = 1, depth = 1, leaf, []
node 1: parent = -1, depth = 0, root, [3, 2, 0]
node 2: parent = 1, depth = 1, leaf, []
node 3: parent = 1, depth = 1, leaf, [] Note You can use a left-child, right-sibling representation to implement a tree which has the following data:  the parent of u  the leftmost child of u  the immediate right sibling of u  Reference Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

Solution (Python):


class Node:
    def __init__(self, num, children):
        self.num = num
        self.children = children
        self.parents = -1
        self.type = None
        self.depth = 0

    def output(self):
        print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(self.num,
                                                                      self.parents,
                                                                      self.depth,
                                                                      self.type,
                                                                      self.children))


def set_node(num, children):
    node = Node(num, children)
    T[num] = node
    for n in children:
        T[-1] -= n  


def set_pdt(n_i, parent, depth):
    node = T[n_i]
    node.parents = parent
    node.depth = depth
    if node.children:
        node.type = 'internal node'
        for n in node.children:
            set_pdt(n, n_i, depth + 1)
    else:
        node.type = 'leaf'


n = int(input())
tree = [list(map(int, input().split())) for i in range(n)]
T = [None] * n
T += [n * (n - 1) // 2]
for j in tree:
    set_node(j[0], j[2:])

set_pdt(T[-1], -1, 0)

T[T[-1]].type = 'root'

for n in T[:-1]:
    n.output()

Solution (Python):
import sys

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

def addDepth(id, tree):
    tree[id].depth += 1
    for child in tree[id].children:
        addDepth(child, tree)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    N = int(lines[0])
    del lines[0]

    tree = []
    for i in range(N):
        tree.append(Node())

    for line in lines:
        line = map(int, line.split())
        tree[line[0]].id = line[0]
        tree[line[0]].children = line[2:]

    for node in tree:
        for child in node.children:
            tree[child].parent = node.id
            addDepth(child, tree)
            if tree[child].children:
                tree[child].type = "internal node"
            else:
                tree[child].type = "leaf"

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

Solution (Python):
import sys

class Node:
    def __init__(self):
        self.id = -1
        self.parent = -1
        self.type = "leaf"

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

def setTree(id, tree, depth):
    tree[id].depth = depth
    if not tree[id].children:
        return

    for child in tree[id].children:
        tree[child].parent = id
        setTree(child, tree, depth + 1)
    tree[id].type = "internal node"

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    N = int(lines[0])
    del lines[0]

    tree = []
    for i in range(N):
        tree.append(Node())

    root = N * (N - 1) / 2
    for line in lines:
        info = map(int, line.split())
        tree[info[0]].children = info[2:]
        tree[info[0]].id = info[0]
        for i in tree[info[0]].children:
            root -= i

    setTree(root, tree, 0)
    tree[root].type = "root"

    for node in tree:
        node.printInfo()

Solution (Python):
from collections import namedtuple
Node = namedtuple('Node', ['parent', 'children'])

class my_tree:
    def __init__(self, N=[]):
        self.T = {}
        for ni in N: self.addNode(ni)

    def addNode(self, n):
        p = self.T.get(n[0],Node(-1,[None])).parent
        self.T[n[0]] = Node(p,n[2:])
        for c in n[2:]:
            cc = self.T.get(c,Node(-1,[None])).children
            self.T[c] = Node(n[0],cc)

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

    def getChildren(self, i): return self.T[i].children

    def getDepth(self, i):
        if self.T[i].parent == -1: return 0
        return self.getDepth(self.T[i].parent) + 1

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

    def getIdList(self): return sorted(self.T.keys())

 
if __name__=='__main__':
    n = int(input())
    N = [None]*n
    for i in range(n): N[i] = list(map(int,input().split()))
    tree = my_tree(N)
     
    for i in tree.getIdList():        
        print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(\
                i, tree.getParent(i), tree.getDepth(i), tree.getNodeType(i), tree.getChildren(i)))

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

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

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

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

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

Solution (Python):

import sys
sys.setrecursionlimit(100000)
class Node(object):
    
    
    def __init__(self, N):
        self.p = [-1 for i in range(N)]
        self.l = [-1 for i in range(N)]
        self.r = [-1 for i in range(N)]
        self.D = [0 for i in range(N)]

    def set_depth_rec(self, u, p):
        self.D[u] = p
        if self.r[u] is not -1:
            self.set_depth(self.r[u], p)
        if self.l[u] is not -1:
            self.set_depth(self.l[u], p+1)

    def set_depth(self, u):
        d = 0
        pre_u = u
        while self.p[u] is not -1:
            u = self.p[u]
            d += 1
        self.D[pre_u] = d

    def print_children(self, u):
        children = []
        flag = self.l[u]
        while flag is not -1:
            children.append(flag)
            flag = self.r[flag]
            
        return children
        

N = int(input())
T = Node(N)

for j in range(N):
    A = [int(i) for i in input().split()]
    
    
    if len(A) > 2:
        T.l[A[0]] = A[2]
    else:
        T.l[A[0]] = -1

    
    for index, i in enumerate(A[2:]):
        if(A[-1] == i):
            T.p[i], T.r[i] = A[0], -1
        else:
            T.p[i], T.r[i] = A[0], A[index+3]
    

for i in range(N):
    T.set_depth(i)

for i in range(N):
    if T.p[i] is -1:
        node = "root"
    elif T.l[i] is -1:
        node = "leaf"
    else:
        node = "internal node"
        
    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(i, T.p[i], T.D[i], node, T.print_children(i)))

Solution (Python):

class RootedTree:
    def __init__(self):
        self.id = None
        self.child = []
        self.parent = -1
        self.node_type = "root"
        self.depth = 0

    def show(self):
        print("node {}: parent = {}, depth = {}, {}, {}".format(self.id, self.parent, self.depth, self.node_type, self.child))

def cal_depth(tree, node, cur_depth):
    node.depth += cur_depth
    
    for index in node.child:
        cal_depth(tree, tree[index], cur_depth + 1)
        
def make_tree(tree_data):
    tree = [RootedTree() for i in range(len(tree_data))]
    
    for data in tree_data:
        focus = tree[data[0]]
        focus.id = data[0]
        
        if data[2:]:
            focus.child = data[2:]
            
            for child_index in data[2:]:
                tree[child_index].parent = data[0]
                
                if tree_data[[a[0] for a in tree_data].index(child_index)][2:]:
                    tree[child_index].node_type = "internal node"
                else:
                    tree[child_index].node_type = "leaf"
            
    root_index = [n.node_type for n in tree].index("root")
    cal_depth(tree, tree[root_index], 0)
    return tree

def set_tree_data(tree, target, parent, depth):
    tree[target]["depth"] += depth
    tree[target]["parent"] = parent

    for c in tree[target]["child"]:
        set_tree_data(tree, c, target, depth + 1)

def make_tree_revision(tree_data, n_tree):
    tree = [{"parent": None, "depth":0, "child" : None} for i in range(n_tree)]
    root = sum(range(n_tree))
    
    for node_data in tree_data:
        tree[node_data[0]]["child"] = node_data[2:]
        root -= sum(node_data[2:])

    set_tree_data(tree, root, -1, 0)
    return tree
def main():
    n_tree = int(input())
    tree_data = [[int(a) for a in input().split()] for i in range(n_tree)]
    
    for i, node in enumerate(make_tree_revision(tree_data, n_tree)):
        category = "root"
        if (not node["parent"] == -1) and node["child"]:
            category = "internal node"
        elif not node["parent"] == -1:
            category = "leaf"

        print("node {}: parent = {}, depth = {}, {}, {}".format(i, node["parent"], node["depth"], category, node["child"]))
if __name__ == "__main__":
    main()

Solution (Python):

"""
class RootedTree:
    def __init__(self):
        self.id = None
        self.child = []
        self.parent = -1
        self.node_type = "root"
        self.depth = 0

    def show(self):
        print("node {}: parent = {}, depth = {}, {}, {}".format(self.id, self.parent, self.depth, self.node_type, self.child))

def cal_depth(tree, node, cur_depth):
    node.depth += cur_depth
    
    for index in node.child:
        cal_depth(tree, tree[index], cur_depth + 1)
        
def make_tree(tree_data):
    tree = [RootedTree() for i in range(len(tree_data))]
    
    for data in tree_data:
        focus = tree[data[0]]
        focus.id = data[0]
        
        if data[2:]:
            focus.child = data[2:]
            
            for child_index in data[2:]:
                tree[child_index].parent = data[0]
                
                if tree_data[[a[0] for a in tree_data].index(child_index)][2:]:
                    tree[child_index].node_type = "internal node"
                else:
                    tree[child_index].node_type = "leaf"
            
    root_index = [n.node_type for n in tree].index("root")
    cal_depth(tree, tree[root_index], 0)
    return tree
"""
def set_tree_data(tree, target, parent, depth):
    tree[target]["depth"] += depth
    tree[target]["parent"] = parent

    for c in tree[target]["child"]:
        set_tree_data(tree, c, target, depth + 1)

def make_tree_revision(tree_data, n_tree):
    tree = [{"parent": None, "depth":0, "child" : None} for i in range(n_tree)]
    root = sum(range(n_tree))
    
    for node_data in tree_data:
        tree[node_data[0]]["child"] = node_data[2:]
        root -= sum(node_data[2:])

    set_tree_data(tree, root, -1, 0)
    return tree

def main():
    n_tree = int(input())
    tree_data = [[int(a) for a in input().split()] for i in range(n_tree)]
    
    for i, node in enumerate(make_tree_revision(tree_data, n_tree)):
        category = "root"
        if (not node["parent"] == -1) and node["child"]:
            category = "internal node"
        elif not node["parent"] == -1:
            category = "leaf"

        print("node {}: parent = {}, depth = {}, {}, {}".format(i, node["parent"], node["depth"], category, node["child"]))
if __name__ == "__main__":
    main()

Solution (Python):




import sys


class Node(object):
    __slots__ = ('parent', 'depth', 'type', 'children')

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


def dfs(node_idx, node_list, d=0):
    node_list[node_idx].depth = d
    for child in node_list[node_idx].children:
        dfs(child, node_list, d=d + 1)
    return None


def print_result(_node):
    print('parent = ' + str(_node.parent) + ',', end=' ')
    print('depth = ' + str(_node.depth) + ',', end=' ')
    print(_node.type + ',', end=' ')
    print(_node.children)
    return None


def generate_tree(_array, node_list):
    for each in _array:
        idx, k, *children = [x for x in each]
        node_list[idx].children = children
        if k:
            node_list[idx].type = 'internal node'
        else:
            node_list[idx].type = 'leaf'
        for child in children:
            node_list[child].parent = idx
    root_idx = [i for i, x in enumerate(node_list) if x.parent == -1][0]
    node_list[root_idx].type = 'root'
    dfs(node_idx=root_idx, node_list=node_list)
    return node_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(lambda x: list(map(int, x.split())), _input[1:]))
    assert len(array) == array_length

    init_node_list = [Node() for _ in range(array_length)]
    ans = generate_tree(_array=array, node_list=init_node_list)
    for key, node in enumerate(ans):
        print('node ' + str(key) + ':', end=' ')
        print_result(_node=node)

Solution (Python):




import sys


class Node(object):
    __slots__ = ('parent', 'depth', 'type', 'children')

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


def dfs(node_idx, node_list, d=0):
    node_list[node_idx].depth = d
    for child in node_list[node_idx].children:
        dfs(child, node_list, d=d + 1)
    return None


def print_result(_node):
    print('parent = ' + str(_node.parent) + ',', end=' ')
    print('depth = ' + str(_node.depth) + ',', end=' ')
    print(_node.type + ',', end=' ')
    print(_node.children)
    return None


def generate_tree(_array, node_list):
    for each in _array:
        idx, k, *children = [x for x in each]
        node_list[idx].children = children
        if k:
            node_list[idx].type = 'internal node'
        else:
            node_list[idx].type = 'leaf'
        for child_idx in children:
            node_list[child_idx].parent = idx
    root_idx = [i for i, x in enumerate(node_list) if x.parent == -1][0]
    node_list[root_idx].type = 'root'
    dfs(node_idx=root_idx, node_list=node_list)
    return node_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(lambda x: list(map(int, x.split())), _input[1:]))
    

    init_node_list = [Node() for _ in range(array_length)]
    ans = generate_tree(_array=array, node_list=init_node_list)
    for key, node in enumerate(ans):
        print('node ' + str(key) + ':', end=' ')
        print_result(_node=node)

Solution (Python):




import sys


class Node(object):
    __slots__ = ('parent', 'depth', 'type', 'children')

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


def dfs(node_idx, node_list, depth=0):
    node_list[node_idx].depth = depth
    for child in node_list[node_idx].children:
        dfs(child, node_list, depth=depth + 1)
    return None


def print_result(_node):
    print('parent = ' + str(_node.parent) + ',', end=' ')
    print('depth = ' + str(_node.depth) + ',', end=' ')
    print(_node.type + ',', end=' ')
    print(_node.children)
    return None


def generate_tree(_array, node_list):
    for each in _array:
        idx, k, *children = [int(x) for x in each]
        node_list[idx].children = children
        if k:
            node_list[idx].type = 'internal node'
        else:
            node_list[idx].type = 'leaf'
        for child_idx in children:
            node_list[child_idx].parent = idx
    root_idx = [i for i, x in enumerate(node_list) if x.parent == -1][0]
    node_list[root_idx].type = 'root'
    dfs(node_idx=root_idx, node_list=node_list)
    return node_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(lambda x: x.split(), _input[1:]))
    

    init_node_list = [Node() for _ in range(array_length)]
    ans = generate_tree(_array=array, node_list=init_node_list)
    for key, node in enumerate(ans):
        print('node ' + str(key) + ':', end=' ')
        print_result(_node=node)

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

    def get_depth(self):
        if self.parent == -1:
            return 0
        else:
            depth = 1
            t = Nodes[self.parent]
            while t.parent != -1:
                t = Nodes[t.parent]
                depth += 1
            return depth

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


def decode_node_data(n):
    global Nodes
    num_of_elem = len(n)
    if num_of_elem < 2:
        raise ValueError
    elif num_of_elem == 2:  
        pass
    else:
        id, num_of_children = int(n[0]), int(n[1])
        children = n[2:]
        Nodes[id].left = int(children[0])
        prev_child = None
        for c in children:
            Nodes[int(c)].parent = id
            if prev_child != None:
                Nodes[prev_child].right = int(c)
            prev_child = int(c)


MAX_NODES = 100001
Nodes = [Node(-1, None, None) for _ in range(MAX_NODES)]
if __name__ == '__main__':
    
    num_of_nodes = int(input())
    node_data = []
    for _ in range(num_of_nodes):
        node_data.append(input().split(' '))

    
    for n in node_data:
        decode_node_data(n)


    
    for node_id in range(num_of_nodes):
        type = Nodes[node_id].get_type()
        children = []
        if type != 'leaf':
            if Nodes[node_id].left != None:
                c = Nodes[node_id].left
                children.append(c)
                while Nodes[c].right != None:
                    c = Nodes[c].right
                    children.append(c)
        print('node {0}: parent = {1}, depth = {2}, {3}, [{4}]'.format(node_id, Nodes[node_id].parent, Nodes[node_id].get_depth(), type,
                                                                       ', '.join(map(str, children))))

Solution (Python):
import sys

nil = -1

def set_depth(v, depth):
    tree[v][2] = depth

    for child in tree[v][1]:
        set_depth(child, depth + 1)

n = int(input())

tree = [[nil, [], 0, 'leaf'] for i in range(n)]

for i in range(n):
    line = [int(i) for i in sys.stdin.readline().split()]
    t_id = line[0]
    children = line[2:]

    tree[t_id][1] = children

    if children:
        tree[t_id][3] = 'internal node'

    for child in children:
        tree[child][0] = t_id

for t_id in range(n):
    if tree[t_id][0] == nil:
        tree[t_id][3] = 'root'
        r = t_id
        break



set_depth(r, 0)

for t_id in range(n):
    parent = tree[t_id][0]
    depth = tree[t_id][2]
    children = tree[t_id][1]
    type_t = tree[t_id][3]

    print('node {}: parent = {}, depth = {}, {}, {}'.format(
            t_id, parent, depth, type_t, children))

Solution (Python):


def main():
    N = int(input())
    A = [0] * N
    node_info = [[-1, 0, 'internal node', None] for _ in range(int(1E5 + 1))]
    for i in range(N):
        A[i] = [int(i) for i in input().strip().split()]
    for line in A:
        if line[1] != 0:
            node_info[line[0]][3] = line[2:]
            for c in line[2:]:
                node_info[c][0] = line[0]

    for line in A:
        pid = node_info[line[0]][0]
        if pid == -1:
            node_info[line[0]][2] = 'root'
        else:
            if node_info[line[0]][3] is None:
                node_info[line[0]][2] = 'leaf'
        if node_info[line[0]][3] is None:
            node_info[line[0]][3] = ['']

        depth = 0
        while pid != -1:
            depth += 1
            pid = node_info[pid][0]
        node_info[line[0]][1] = depth

    for line in sorted(A, key=lambda a: a[0]):
        print('node {}: parent = {}, depth = {}, {}, [{}]'.format(
            line[0], node_info[line[0]][0],
            node_info[line[0]][1], node_info[line[0]][2], ', '.join([str(i) for i in node_info[line[0]][3]]))
        )


if __name__ == '__main__':
    main()

Solution (Python):
NIL = -1

class Node:
    parent = NIL
    left = NIL
    right = NIL

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

def getChildren(u):
    c = T[u].left
    result = []
    while c != NIL:
        result.append(c)
        c = T[c].right
    return result

n = int(input())
T = [0]*n
for i in range(n):
    T[i] = Node()
    
for i in range(n):
    tmp = list(map(int,input().split()))
    id = tmp.pop(0)
    k = tmp.pop(0)
    c = tmp
    if k != 0:
        for j in range(len(c)):
            T[c[j]].parent = id
        T[id].left = c[0]
        for j in range(len(c)-1):
            T[c[j]].right = c[j+1]
            
for i in range(n):
    d = getDepth(i)
    c = getChildren(i)
    if d == 0:
        t = 'root'
    elif c == []:
        t = 'leaf'
    else:
        t = 'internal node'
    print('node ',i,': ','parent = ',T[i].parent,', depth = ',d,', ',t,', ',c,sep = '')

Solution (Python):
class Tree:
    def __init__(self,parent,left,right):
        self.parent = parent
        self.left = left
        self.right = right

def getdepth(u):
    for i in range(N):
        depth = 0
        j = i
        while trees[j].parent != -1:
            j = trees[j].parent
            depth += 1
        depths[i] = depth


N = int(input())

trees = [Tree(-1,-1,-1) for i in range(N)]
for i in range(N):
    l = list(map(int, input().split()))
    no = l[0]
    jisu = l[1]
    
    childs = l[2:]
    for j in range(jisu):
        child = childs[j]
        if j == 0:
            trees[no].left = child

        if j != len(childs)-1:
            trees[child].right = childs[j+1]

        trees[child].parent = no

r = 0
for i in range(N):
    if trees[i].parent == -1:
        r = i

depths = [-1] * N
getdepth(r)

for i in range(N):
    type = ""
    if trees[i].parent == -1: type = "root"
    elif trees[i].left == -1: type = "leaf"
    else: type = "internal node"
    childs = "["
    child = trees[i].left
    while child != -1:
        childs += str(child)
        child = trees[child].right
        if child != -1: childs += ", "
    childs += "]"

    print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(i, trees[i].parent, depths[i], type, childs))

Solution (Python):
class Node:
  def __init__(self, id, children):
    self.id = id
    self.children = children
    self.type = "root"
    self.parent = None
    self.depth = 0

  def set_parent(self, parent):
    self.parent = parent
    self.type = "leaf" if len(self.children) == 0 else "internal node"

  def get_depth(self):
    if self.depth: return self.depth
    if self.type == "root": return 0
    self.depth = self.parent.get_depth() + 1
    return self.depth

  def display(self):
    print("node {}: parent = {}, depth = {}, {}, {}".format(
      self.id,
      self.parent.id if self.parent else -1,
      self.get_depth(),
      self.type,
      self.children
      )
    )

nodelist = {}
for i in range(int(input())):
  p = input().split()
  id = int(p[0])
  nodelist[id] = Node(id, list(map(int, p[2:])) if len(p) >= 3 else [])

for i in nodelist:
  n = nodelist[i]
  for cid in n.children:
    nodelist[cid].set_parent(n)

for i in sorted(nodelist): nodelist[i].display()

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

tree = [{'p': -1, 'c': list(), 'd': 0} for _ in range(N)]

for _ in range(N):
    l = list(map(int, input().split()))
    tree[l[0]]['c'] = l[2:]
    for i in l[2:]:
        tree[i]['p'] = l[0]


def calcDepth(tree, root, curDepth=0):
    tree[root]['d'] = curDepth
    [calcDepth(tree, c, curDepth + 1) for c in tree[root]['c']]


r = 0
for i, t in enumerate(tree):
    if t['p'] == -1:
        r = i
        break
calcDepth(tree, r)

for i in range(N):
    state = 'leaf'
    if tree[i]['p'] == -1:
        state = 'root'
    elif len(tree[i]['c']):
        state = 'internal node'
    print('node {i}: parent = {p}, depth = {d}, {state}, {ch}'.format(
        i=i, p=tree[i]['p'], d=tree[i]['d'], state=state, ch=tree[i]['c']
    ))

Solution (Python):
import operator

class Tree:
    """??¨????????????"""

    def __init__(self, node_num):
        self.node_num = node_num
        self.node_list = list()
        self.root_node = -1

    def set_tree(self):
        for _ in range(self.node_num):
            input_str = [int(i) for i in input().split()]
            node_tmp = Node(input_str[0], input_str[1], input_str[2:])
            self.node_list.append(node_tmp)
        self.node_list.sort(key=operator.attrgetter('id'))

    def set_node_element(self):
        for tn in self.node_list:
            if tn.children is not None:
                for child in tn.children:
                    self.node_list[child].parent = tn.id
                    if self.node_list[child].degree == 0:
                        self.node_list[child].type = 'leaf'
                    else:
                        self.node_list[child].type = 'internal node'
        self.set_root()
        self.set_depth(self.node_list[self.root_node])

    def set_depth(self, node, dep = -1):
        node.depth = dep + 1
        for child in node.children:
            self.set_depth(self.node_list[child], node.depth)

    def set_root(self):
        for tn in self.node_list:
            if tn.type == 'root':
                self.root_node = tn.id
                break

    def show_tree(self):
        for tn in self.node_list:
            print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(tn.id, tn.parent, tn.depth, tn.type, tn.children))


class Node:
    """?????????????????????"""

    def __init__(self, id, degree, children):
        self.id = id
        self.degree = degree
        self.children = children
        self.parent = -1
        self.depth = 0
        self.type = 'root'

if __name__ == '__main__':
    n = int(input())
    tree = Tree(n)
    tree.set_tree()
    tree.set_node_element()
    tree.show_tree()

Solution (Python):
NIL = -1


class Node:
    parent = NIL
    left = NIL
    right = NIL


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


def getChildren(u):
    c = T[u].left
    result = []
    while c != NIL:
        result.append(c)
        c = T[c].right
    return result


n = int(input())
T = [0] * n
for i in range(n):
    T[i] = Node()

for i in range(n):
    tmp = list(map(int, input().split()))
    id = tmp.pop(0)
    k = tmp.pop(0)
    c = tmp
    if k != 0:
        for j in range(len(c)):
            T[c[j]].parent = id
        T[id].left = c[0]
        for j in range(len(c) - 1):
            T[c[j]].right = c[j + 1]

for i in range(n):
    d = getDepth(i)
    c = getChildren(i)
    if d == 0:
        t = 'root'
    elif c == []:
        t = 'leaf'
    else:
        t = 'internal node'
    print('node ', i, ': ', 'parent = ', T[i].parent, ', depth = ', d, ', ', t, ', ', c, sep='')

Solution (Python):
NIL = -1


class Node:
    parent = NIL
    left = NIL
    right = NIL


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


def getChildren(u):
    c = T[u].left
    result = []
    while c != NIL:
        result.append(c)
        c = T[c].right
    return result


n = int(input())
T = [0] * n
for i in range(n):
    T[i] = Node()

for i in range(n):
    tmp = list(map(int, input().split()))
    id = tmp.pop(0)
    k = tmp.pop(0)
    c = tmp
    if k != 0:
        for j in range(len(c)):
            T[c[j]].parent = id
        T[id].left = c[0]
        for j in range(len(c) - 1):
            T[c[j]].right = c[j + 1]

for i in range(n):
    d = getDepth(i)
    c = getChildren(i)
    if d == 0:
        t = 'root'
    elif c == []:
        t = 'leaf'
    else:
        t = 'internal node'
    print('node ', i, ': ', 'parent = ', T[i].parent, ', depth = ', d, ', ', t, ', ', c, sep='')