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):
N = int(input())

def get_parent(node):
    parent = -1
    if "parent" in node:
        parent = node["parent"]
    return parent

def get_depth(node):
    depth = 0
    while "parent" in node:
        depth += 1
        parent = node["parent"]
        node = rooted_tree[parent]
    return depth

def get_node_type(node):
    if "parent" not in node:
        return "root"
    if "left" not in node:
        return "leaf"
    return "internal node"

def get_children(node):
    if "left" not in node:
        return "[]"
    left = node["left"]
    siblings = []
    siblings.append(str(left))
    while rooted_tree[left]["right"] > -1:
        right = rooted_tree[left]["right"]
        siblings.append(str(right))
        left = right
    return "[{}]".format(", ".join(siblings))

rooted_tree = [{} for i in range(N)]
for _ in range(N):
    row = input()
    id, degree, *children = list(map(int, row.split()))
    if degree > 0:
        rooted_tree[id]["left"] = children[0]
        for i in range(len(children)):
            child_id = children[i]
            right = -1
            if i < len(children)-1:
                right = children[i+1]
            rooted_tree[child_id]["right"] = right
            rooted_tree[child_id]["parent"] = id

for id in range(N):
    node = rooted_tree[id]
    parent = get_parent(node)
    depth = get_depth(node)
    node_type = get_node_type(node)
    children = get_children(node)
    print("node {}: parent = {}, depth = {}, {}, {}".format(id, parent, depth, node_type, children))

Solution (Python):

class Node():
    
    
    
    
    def __init__(self, id, parent, child):
        self.id = id
        self.parent = parent
        self.child = child

    def update(self):
        self.depth = 0
        back = -1
        if self.parent == -1:
            self.Type = "root"
            back = self.id
        elif self.child == []:
            self.Type = "leaf"
        else :
            self.Type = "internal node"
        return back

    def printInfo(self):
        print("node " + str( self.id ), end = ": " )
        print("parent = " + str( self.parent ), end = ", " )
        print("depth = " + str( self.depth ), end = ", " )
        print( self.Type, end = ", " )
        print("[", end="")
        length = len( self.child )
        for i in self.child[0: length - 1]:
            print(str(i), end=", ")
        if length > 0:
            print( str(self.child[length-1]) , end="")
        print("]")


    def calcDepth(self, Tree):
        if self.parent == -1:
            self.depth = 0
        else :
            self.depth = Tree[self.parent].depth + 1
        for i in self.child:
            Tree[i].calcDepth(Tree)


def main():
    
    n = int( input() )
    InputData = []
    Tree = {} 

    tmp = []
    for i in range(n):
        tmp = [int(x) for x in input().split()] 
        InputData.append(tmp)
        
        Tree[tmp[0]] = Node(tmp[0], -1, tmp[2: 2+tmp[1]])

    for val in Tree.values():
        for i in val.child:
            Tree[i].parent = val.id

    for key in Tree.keys():
        tmp = Tree[key].update()
        if tmp != -1:
            root = tmp

    Tree[root].calcDepth(Tree)

    keys = list(Tree.keys())
    keys.sort()

    for key in keys:
        Tree[key].printInfo()

if __name__ == '__main__':
    main()

Solution (Python):
class Tree():
    def __init__(self):
        self.parent = -1
        self.depth = 0
        self.child = []


n = int(input())
tree = [Tree() for i in range(n)]

for i in range(n):
    cmd = list(map(int, input().split()))
    node = tree[cmd[0]]
    node.child.extend(cmd[2:])
    for j in cmd[2:]:
        tree[j].parent = cmd[0]

for j in tree:
    d, p = 0, j.parent
    while p != -1:
        d += 1
        p = tree[p].parent
    j.depth = d

for count in range(n):
    j = tree[count]

    if j.parent == -1:
        state = "root"
    elif j.child:
        state = "internal node"
    else:
        state = "leaf"

    print("node {}: parent = {}".format(count, j.parent), "depth = {}".format(
        j.depth), state, "[{}]".format(", ".join(map(str, j.child))), sep=", ")

Solution (Python):
n = int(input())
rt = {}
clist = [0 for i in range(n)]
for i in range(n):
    id, k, *c = list(map(int, input().split()))
    for j in c:
        rt[j] = id
    clist[id] = c
for i in range(n):
    print("node %d: parent = "%i, end = "")
    p = [i]
    while 1:
        try:
            p.append(rt[p[-1]])
        except:
            break
    if len(p) == 1:
        print("-1, depth = 0, root,",clist[i])
    else:
        print("%d, depth ="%p[1] ,len(p) - 1, end = "")
        if clist[i] == []:
            print(", leaf, []")
        else:
            print(", internal node,",clist[i])

Solution (Python):
class Node:
	def __init__(self, id):
		self.id = id
		self.parent_id = -1
		self.depth = 0
		self.children = None
	def get_type(self):
		if self.parent_id == -1:
			return 'root'
		elif self.children == None or len(self.children) == 0:
			return 'leaf'
		return 'internal node'
	def __str__(self):
		ret = 'node ' + str(self.id) + ': '
		ret += 'parent = ' + str(self.parent_id) + ', '
		ret += 'depth = ' + str(self.depth) + ', '
		ret += self.get_type() + ', '
		ret += '['
		for i in range(len(self.children)):
			ret += str(self.children[i])
			if i != len(self.children) - 1:
				ret += ', '
		ret += ']'
		return ret

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
	a = list(map(int, input().split()))
	id = a[0]
	node = nodes[id]
	if node.parent_id != -1:
		node.depth = nodes[node.parent_id].depth + 1

	m = a[1]
	children = []
	for j in range(m):
		child_id = a[j + 2]
		children.append(child_id)
		nodes[child_id].parent_id = id
		nodes[child_id].depth = node.depth + 1
	node.children = children

for i in range(n):
	print(nodes[i])

Solution (Python):
class Node:
	def __init__(self, id):
		self.id = id
		self.parent_id = -1
		self.depth = 0
		self.children = None
	def get_type(self):
		if self.parent_id == -1:
			return 'root'
		elif self.children == None or len(self.children) == 0:
			return 'leaf'
		return 'internal node'
	def __str__(self):
		ret = 'node ' + str(self.id) + ': '
		ret += 'parent = ' + str(self.parent_id) + ', '
		ret += 'depth = ' + str(self.depth) + ', '
		ret += self.get_type() + ', '
		ret += '['
		for i in range(len(self.children)):
			ret += str(self.children[i])
			if i != len(self.children) - 1:
				ret += ', '
		ret += ']'
		return ret

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
	a = list(map(int, input().split()))
	id = a[0]
	node = nodes[id]
	if node.parent_id != -1:
		node.depth = nodes[node.parent_id].depth + 1

	m = a[1]
	children = [0] * m
	for j in range(m):
		child_id = a[j + 2]
		children[j] = child_id
		nodes[child_id].parent_id = id
		nodes[child_id].depth = node.depth + 1
	node.children = children

for i in range(n):
	print(nodes[i])

Solution (Python):
class Node:
	def __init__(self, id):
		self.id = id
		self.parent_id = -1
		self.depth = -1
		self.children = None
	def get_type(self):
		if self.parent_id == -1:
			return 'root'
		elif self.children == None or len(self.children) == 0:
			return 'leaf'
		return 'internal node'
	def __str__(self):
		strNode = 'node ' + str(self.id) + ': '
		strNode += 'parent = ' + str(self.parent_id) + ', '
		strNode += 'depth = ' + str(self.depth) + ', '
		strNode += self.get_type() + ', ['
		if len(self.children) > 0:
			strNode += str(self.children[0])
			for i in range(1, len(self.children)):
				strNode +=  ', ' + str(self.children[i])
		strNode += ']'
		return strNode

def calc_depth(nodes):
	stack = []
	for i in range(len(nodes)):
		if nodes[i].parent_id == -1:
			nodes[i].depth = 0
			stack.append(nodes[i].id)
			break
	while len(stack) != 0:
		node = nodes[stack.pop()]
		for i in range(len(node.children)):
			child_id = node.children[i]
			nodes[child_id].depth = node.depth + 1
			stack.append(child_id)

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
	a = list(map(int, input().split()))
	id = a[0]
	node = nodes[id]
	m = a[1]
	children = [0] * m
	for j in range(m):
		child_id = a[2 + j]
		child = nodes[child_id]
		child.parent_id = id
		children[j] = child_id
	node.children = children

calc_depth(nodes)

for i in range(n):
	print(nodes[i])

Solution (Python):
class Node:
	def __init__(self, id):
		self.id = id
		self.parent_id = -1
		self.depth = -1
		self.children = None
	def get_type(self):
		if self.parent_id == -1:
			return 'root'
		elif self.children == None or len(self.children) == 0:
			return 'leaf'
		return 'internal node'
	def __str__(self):
		strNode = 'node ' + str(self.id) + ': '
		strNode += 'parent = ' + str(self.parent_id) + ', '
		strNode += 'depth = ' + str(self.depth) + ', '
		strNode += self.get_type() + ', ['
		if len(self.children) > 0:
			strNode += str(self.children[0])
			for i in range(1, len(self.children)):
				strNode +=  ', ' + str(self.children[i])
		strNode += ']'
		return strNode

def calc_depth(nodes):
	stack = []
	for i in range(len(nodes)):
		if nodes[i].parent_id == -1:
			nodes[i].depth = 0
			stack.append(nodes[i].id)
			break
	while len(stack) != 0:
		node = nodes[stack.pop()]
		for i in range(len(node.children)):
			child_id = node.children[i]
			nodes[child_id].depth = node.depth + 1
			stack.append(child_id)

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
	a = list(map(int, input().split()))
	id = a[0]
	m = a[1]
	children = [0] * m
	for j in range(m):
		child_id = a[2 + j]
		child = nodes[child_id]
		child.parent_id = id
		children[j] = child_id
	nodes[id].children = children

calc_depth(nodes)

for i in range(n):
	print(nodes[i])

Solution (Python):
from sys import stdin

class Node(object):
    def __init__(self, parent=None, children=None, name=None, depth=None):
        self.parent = parent
        self.children = children
        self.name = name

class Node(object):
    def __init__(self, parent=None, children=None, name=None, depth=None):
        self.parent = parent
        self.children = children
        self.name = name

def print_nodes(nodes, n):
    def get_depth(nodes, u):
        p = nodes[u].parent
        nonlocal d
        if p != None and p != -1:
            get_depth(nodes, p)
            d += 1
        return d

    for i in range(n):
        d = 0
        if nodes[i].parent == None:
            nodes[i].parent = -1
            nodes[i].name = "root"
        print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(
               i, nodes[i].parent, get_depth(nodes, i), nodes[i].name, nodes[i].children))

def read_rooted_tree(nodes, n):
    for _ in range(n):
        i = [int(i) for i in stdin.readline().strip().split()]
        c = i[2:len(i)]
        nodes[i[0]].children = c
        if c:
            nodes[i[0]].name = "internal node"
        else:
            nodes[i[0]].name = "leaf"
        for j in nodes[i[0]].children:
            nodes[j].parent = i[0]

n = int(input())
nodes = [Node() for _ in range(n)]
read_rooted_tree(nodes, n)
print_nodes(nodes, n)

Solution (Python):
from sys import stdin

class Node(object):
    def __init__(self, parent=None, children=None, name=None):
        self.parent = parent
        self.children = children
        self.name = name

def print_nodes(nodes, n):
    def get_depth(nodes, u):
        p = nodes[u].parent
        nonlocal d
        if p != None and p != -1:
            get_depth(nodes, p)
            d += 1
        return d

    for i in range(n):
        d = 0
        if nodes[i].parent == None:
            nodes[i].parent = -1
            nodes[i].name = "root"
        print("node {0}: parent = {1}, depth = {2}, {3}, {4}".format(
               i, nodes[i].parent, get_depth(nodes, i), nodes[i].name, nodes[i].children))

def read_rooted_tree(nodes, n):
    for _ in range(n):
        i = [int(i) for i in stdin.readline().strip().split()]
        c = i[2:len(i)]
        nodes[i[0]].children = c
        if c:
            nodes[i[0]].name = "internal node"
        else:
            nodes[i[0]].name = "leaf"
        for j in nodes[i[0]].children:
            nodes[j].parent = i[0]

n = int(input())
nodes = [Node() for _ in range(n)]
read_rooted_tree(nodes, n)
print_nodes(nodes, n)

Solution (Python):



from sys import setrecursionlimit

setrecursionlimit(21)


class Node():
    def __init__(self, parent=-1, child=[]):
        self.parent = parent
        self.child = child


def node_depth(u, id):
    if u[id].parent == -1:
        return 0
    else:
        return node_depth(u, u[id].parent) + 1


def node_type(u, id):
    if u[id].parent == -1:
        return "root"
    elif u[id].child == []:
        return "leaf"
    else:
        return "internal node"


def main():
    n = int(input())
    u = [Node() for _ in range(n)]

    for _ in range(n):
        id, _, *child = (int(x) for x in input().split())
        u[id].child = child
        for c in child:
            u[c].parent = id

    for id in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(id, u[id].parent,
                     node_depth(u, id), node_type(u, id),
                     u[id].child))


if __name__ == '__main__':
    main()

Solution (Python):
class Node():
    def __init__(self, parent=-1, child=[]):
        self.parent = parent
        self.child = child


def node_depth(u, id):
    if u[id].parent == -1:
        return 0
    else:
        return node_depth(u, u[id].parent) + 1


def node_type(u, id):
    if u[id].parent == -1:
        return "root"
    elif u[id].child == []:
        return "leaf"
    else:
        return "internal node"


def main():
    n = int(input())
    u = [Node() for _ in range(n)]

    for _ in range(n):
        id, _, *child = (int(x) for x in input().split())
        u[id].child = child
        for c in child:
            u[c].parent = id

    for id in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(id, u[id].parent,
                     node_depth(u, id), node_type(u, id),
                     u[id].child))


main()

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

def dfs(v, d=0):
    G[v].depth = d
    for child in G[v].children:
        dfs(child,d+1)

N = int(input())
G = [Node() for _ in range(N)]
for _ in range(N):
    idx,k,*children = [int(x) for x in input().split()]
    G[idx].children = children
    if k:
        G[idx].type = 'internal node'
    else:
        G[idx].type = 'leaf'
    for child in children:
        G[child].parent = idx

root = [i for i,x in enumerate(G) if x.parent == -1][0]
G[root].type = 'root'
dfs(root)
for i,node in enumerate(G):
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(
        i,
        node.parent,
        node.depth,
        node.type,
        ', '.join(map(str,node.children))
        )
    )

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

def dfs(v, d=0):
    G[v].depth = d
    for child in G[v].children:
        dfs(child,d+1)

N = int(input())
G = [Node() for _ in range(N)]
for _ in range(N):
    idx,k,*children = [int(x) for x in input().split()]
    G[idx].children = children
    if k:
        G[idx].type = 'internal node'
    else:
        G[idx].type = 'leaf'
    for child in children:
        G[child].parent = idx

root = [i for i,x in enumerate(G) if x.parent == -1][0]
G[root].type = 'root'
dfs(root)
for i,node in enumerate(G):
    print('node {}: parent = {}, depth = {}, {}, [{}]'.format(
        i,
        node.parent,
        node.depth,
        node.type,
        ', '.join(map(str,node.children))
        )
    )

Solution (Python):
n = int(input())
child = {}
parent = {}

for i in range(n):
    a = list(map(int, input().split()))
    child[a[0]] = a[2:]
    for i in child[a[0]]:
        parent[i] = a[0] 

root = (set(child)-set(parent)).pop()
depth = [None]*n
depth[root] = 0
parent[root] = -1

    
def dfs(s):
    for i in child[s]:
            depth[i]=depth[s]+1
            dfs(i)
    
dfs(root)
    
for i in range(n):
    node_type = "root" if parent[i] == -1 else "leaf" if len(child[i]) == 0 else "internal node"
    print(f'node {i}: parent = {parent[i]}, depth = {depth[i]}, {node_type}, {child[i]}')

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

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


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)


N = int(input())
T = [Node(-1, -1, -1) for _ in range(N)]
D = [-1] * N
for i in range(N):
    i, k, *cs = map(int, input().split())
    for j, c in enumerate(cs):
        if j == 0:
            T[i].l = c
        else:
            T[l].r = c
        l = c
        T[c].p = i
for i, t in enumerate(T):
    if t.p == -1:
        r = i
rec(r, 0)
for i, t in enumerate(T):
    cs = []
    c = t.l
    while c != -1:
        cs.append(c)
        c = T[c].r
    if t.p == -1:
        print('node {}: parent = {}, depth = {}, root, {}'
              .format(i, t.p, D[i], cs))
    elif t.l == -1:
        print('node {}: parent = {}, depth = {}, leaf, {}'
              .format(i, t.p, D[i], cs))
    else:
        print('node {}: parent = {}, depth = {}, internal node, {}'
              .format(i, t.p, D[i], cs))

Solution (Python):
def f(n,e,a):
    d[n].extend([a,e,"root" if a<0 else "internal node" if len(d[n][1]) else "leaf"])
    for i in d[n][1]:f(i,e+1,n)
n=input()
c=[0]*n
d=sorted([map(int,raw_input().split()) for _ in range(n)])
for i in d:
    i[1:]=[i[2:]]
    for j in i[1]:c[j]=1
f(c.index(0),0,-1)
for i in d:print "node {0}: parent = {2}, depth = {3}, {4}, {1}".format(*i)

Solution (Python):
class Tree():
    def __init__(self):
        self.nodes = {}
    def add_node(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)        
    def add_child(self, parent_id, child_id):
        self.add_node(parent_id)
        self.add_node(child_id)
        self.nodes[parent_id].add_child(self.nodes[child_id])
    
class Node():
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.children = []
        self.depth = 0
        self.nodetype = 'root'

    def add_child(self, child):
        self.children.append(child)
        child.parent = self
        child.update_depth()
        child.update_nodetype()
        self.update_nodetype()
        if self.parent:
            self.parent.update_nodetype()
            
    def update_depth(self):
        depth = self.depth
        if self.parent:
            self.depth = self.parent.depth + 1
        if depth != self.depth:
            for child in self.children:
                child.update_depth()
                
    def update_nodetype(self):
        if self.parent:
            if len(self.children):
                self.nodetype = 'internal node'
            else:
                self.nodetype = 'leaf'
        else:
            self.nodetype = 'root'
        
            
    def walk(self):
        yield self
        for child in self.children:
            for node in child.walk():
                yield node

    def __str__(self):
        parent = self.parent.id if self.parent else -1
        children = ', '.join([str(node.id) for node in self.children])
        return 'node {}: parent = {}, depth = {}, {}, [{}]'.format(self.id, parent, self.depth, self.nodetype, children)

    
tree = Tree()

n = int(input())
for i in range(n):
    line = input().split()
    id = int(line[0])
    tree.add_node(id)
    for ci in map(int, line[2:]):
        tree.add_child(id, ci)

for id in tree.nodes:
    print( tree.nodes[id])

Solution (Python):



import sys

class Node(object):
    def __init__(self, id_):
        super(Node, self).__init__()
        self.id_ = id_
        self.parent = -1
        self.depth = 0
        self.children = []

    def add_child(self, child_):
        self.children.append(child_)

    def set_parent(self, parent):
        assert self.parent == -1
        self.parent = parent

    def __str__(self):
        str_ = 'node %d: ' % (self.id_)
        str_ += 'parent = %d, ' % (self.parent)
        str_ += 'depth = %d, ' % (self.depth)
        if self.parent == -1:
            str_ += 'root, '
        elif len(self.children) > 0:
            str_ += 'internal node, '
        else:
            str_ += 'leaf, '
        str_ += '[%s]' % (', '.join([str(x) for x in self.children]))
        return str_

def set_depth(nodes_, node_id_):
    for child_id_ in nodes_[node_id_].children:
        nodes_[child_id_].depth = nodes_[node_id_].depth + 1
        set_depth(nodes_, child_id_)


nnodes = int(sys.stdin.readline())
nodes = []
for i in range(0, nnodes):
    nodes.append(Node(i))


for _ in range(0, nnodes):
    vals = sys.stdin.readline().rstrip().split(' ')
    node_id = int(vals[0])
    node = nodes[node_id]
    nchild = int(vals[1])
    for i in range(0, nchild):
        child_id = int(vals[2+i])
        node.add_child(child_id)
        child = nodes[child_id]
        child.set_parent(node_id)

root = 0

if nodes[root].parent != -1:
    for node in nodes:
        if node.parent == -1:
            root = node.id_
            break
    assert root != 0


set_depth(nodes, root)

for n in nodes:
    print n

Solution (Python):


from collections import deque 

class Node:
    def __init__(self):
        self.id = -1
        self.k = -1
        self.depth = -1
        self.parent = -1
        self.type = 'root'
        self.end = False
        self.children = []
        
def find_root_id(nodes):
    i = 0
    rootid = -1
    while nodes[i].parent != -1:
        nodes[i]
        i += 1
    else:
        rootid = nodes[i].id
        return rootid
        
def set_depth(rootid, nodes):
    que = deque()
    depth = 0
    node = nodes[rootid]
    que = deque(node.children)
    for i in que:
        nodes[i].depth = depth + 1
    depth += 1
    
    while que:
        for i in range(len(que)):
            for child in nodes[que.popleft()].children:
                que.append(child)
        for j in que:
            nodes[j].depth = depth + 1
        depth += 1

n = int(raw_input())
nodes = []
for i in range(n):
    node = Node()
    ls =  map(int, raw_input().split())
    node.id = ls[0]
    node.k = ls[1]
    if node.k == 0:
        pass
    else:
        node.children = ls[2:]
    nodes.append(node)
    
nodes = sorted(nodes, key=lambda node:node.id)
for node in nodes:
    for child in node.children:
        nodes[child].parent = node.id
        
for node in nodes:
    if node.children == []:
        if node.parent != -1:
            node.type = 'leaf'
    else:
        if node.parent != -1:
            node.type = 'internal node'

rootid = find_root_id(nodes)
nodes[rootid].depth = 0

def set_depth(rootid, nodes):
    que = deque()
    depth = 0
    node = nodes[rootid]
    que = deque(node.children)
    for i in que:
        nodes[i].depth = depth + 1
    depth += 1
    
    while que:
        for i in range(len(que)):
            for child in nodes[que.popleft()].children:
                que.append(child)
        for j in que:
            nodes[j].depth = depth + 1
        depth += 1

set_depth(rootid, nodes)
for node in nodes:
    print 'node %s: parent = %s, depth = %s, %s, %s'%(node.id,
    node.parent, node.depth, node.type, node.children)

Solution (Python):

from collections import deque 

class Node:
    def __init__(self):
        self.id = -1
        self.k = -1
        self.depth = -1
        self.parent = -1
        self.type = 'root'
        self.end = False
        self.children = []
        
def find_root_id(nodes):
    i = 0
    rootid = -1
    while nodes[i].parent != -1:
        nodes[i]
        i += 1
    else:
        rootid = nodes[i].id
        return rootid
        
def set_depth(rootid, nodes):
    que = deque()
    depth = 0
    node = nodes[rootid]
    que = deque(node.children)
    for i in que:
        nodes[i].depth = depth + 1
    depth += 1
    
    while que:
        for i in xrange(len(que)):
            for child in nodes[que.popleft()].children:
                que.append(child)
        for j in que:
            nodes[j].depth = depth + 1
        depth += 1

n = int(raw_input())
nodes = []
for i in xrange(n):
    node = Node()
    ls =  map(int, raw_input().split())
    node.id = ls[0]
    node.k = ls[1]
    if node.k == 0:
        pass
    else:
        node.children = ls[2:]
    nodes.append(node)
    
nodes = sorted(nodes, key=lambda node:node.id)
for node in nodes:
    for child in node.children:
        nodes[child].parent = node.id
        
for node in nodes:
    if node.children == []:
        if node.parent != -1:
            node.type = 'leaf'
    else:
        if node.parent != -1:
            node.type = 'internal node'

rootid = find_root_id(nodes)
nodes[rootid].depth = 0
set_depth(rootid, nodes)
for node in nodes:
    print 'node %s: parent = %s, depth = %s, %s, %s'%(node.id, node.parent, node.depth, node.type, node.children)

Solution (Python):
from operator import attrgetter
class Node:
    def __init__(self, id, children):
        self.id = id
        self.children = children
        self.childNode = []
        self.parent = -1
        self.depth = -1
        self.nodeType = ''

    def setChildNode(self, node):
        self.childNode.append(node)

    def __repr__(self):
        return self.__str__()

    def __str__(self):
        return 'node ' + str(self.id) + ': parent = ' + str(self.parent) + ', depth = ' + str(self.depth) + ', '\
                + self.nodeType + ', ' + self.children.__str__()

    def setNodeType(self):
        if self.parent == -1:
            self.nodeType = 'root'
        elif len(self.children) == 0:
            self.nodeType = 'leaf'
        else:
            self.nodeType = 'internal node'

def setDepth(node, depth):
    node.depth = depth
    for child in node.childNode:
        setDepth(child, depth + 1)

n = int(raw_input())
T = []
P = [-1] * n
for i in xrange(n):
    L = map(int, raw_input().split())
    id = L[0]
    T.append(Node(id, L[2:]))
    for child in T[i].children:
        P[child] = id
T.sort(key=attrgetter('id'))
root = P.index(-1)
for i, x in enumerate(P):
    T[i].parent = P[i]
    for cid in T[i].children:
        T[i].setChildNode(T[cid])

setDepth(T[root], 0)
for x in T:
    x.setNodeType()
    print x

Solution (Python):


import sys


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

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    node_list = [None] * int(lines[0])  
    child_parent_map = [None] * int(lines[0])

    
    for line in lines[1:]:
        node_id, _, *children = [int(x) for x in line.strip().split(" ")]
        node_list[node_id] = Node(children=children)
        for child in children:
            child_parent_map[child] = node_id

    
    for node_id, node in enumerate(node_list):
        if child_parent_map[node_id] is not None:
            node.parent_id = child_parent_map[node_id]

    
    for node_id, node in enumerate(node_list):
        current_id = node_id
        current_depth = 0
        while True:
            
            if node_list[current_id].parent_id == -1:
                node.depth = current_depth
                break
            else:
                current_id = node_list[current_id].parent_id
                current_depth += 1

    
    for node_id, node in enumerate(node_list):
        if node.parent_id == -1:
            node_type = "root"
        elif len(node.children) == 0:
            node_type = "leaf"
        else:
            node_type = "internal node"

        print("node %d: parent = %d, depth = %d, %s, %s" % (node_id, node.parent_id, node.depth, node_type, node.children))