Problem:

Binary Tree

A rooted binary tree is a tree with a root node in which every node has at most two children.

Your task is to write a program which reads a rooted binary tree T and prints the following information for each node u of T:

node ID of u

parent of u

sibling of u

the number of children of u

depth of u

height of u

node type (root, internal node or leaf)

If two nodes have the same parent, they are siblings. Here, if u and v have the same parent, we say u is a sibling of v (vice versa).

The height of a node in a tree is the number of edges on the longest simple downward path from the node to a leaf.

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

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 is given in the following format:

id left right

id is the node ID, left is ID of the left child and right is ID of the right child. If the node does not have the left (right) child, the left(right) is indicated by -1.

Output

Print the information of each node in the following format:

node id: parent = p, sibling = s, degree = deg, depth = dep, height = h, type

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

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

deg, dep and h are the number of children, depth and height of the node respectively.

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.

Please follow the format presented in a sample output below.

Constraints

1 ≤ n ≤ 25

Sample Input 1

9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1

Sample Output 1

node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node
node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf
node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf
node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node
node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node
node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf
node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf
node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf

Reference

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



Sample input:
9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1


Sample output:
node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node
node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf
node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf
node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node
node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node
node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf
node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf
node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf

Submission status: Wrong Answer

Solution code:
class Tree:
    nodes = []
    def __init__(self):
        self.root = None
    def insert(self, nodenum, leftnum, rightnum):
        if leftnum != -1:
            self.nodes[nodenum].left = self.nodes[leftnum]
            self.nodes[leftnum].type_ = "internal node"
            self.nodes[leftnum].parent = self.nodes[nodenum]
            self.nodes[nodenum].degree += 1
        else:
            self.nodes[nodenum].left = -1
        if rightnum != -1:
            self.nodes[nodenum].right = self.nodes[rightnum]
            self.nodes[rightnum].type_ = "internal node"
            self.nodes[rightnum].parent = self.nodes[nodenum]
            self.nodes[nodenum].degree += 1
        else:
            self.nodes[nodenum].right = -1
        if leftnum != -1 and rightnum != -1:
            self.nodes[leftnum].sibling = rightnum
            self.nodes[rightnum].sibling = leftnum
    def depth(self, node):
        if node.left != -1:
            node.left.depth += node.depth + 1
            self.depth(node.left)
        if node.right != -1:
            node.right.depth += node.depth + 1
            self.depth(node.right)
    def height(self, node):
        if node.left == -1 and node.right == -1:
            node.type_ = "leaf"
            return 0
        elif node.left == -1:
            x = self.height(node.right)
            node.height = x
            return x + 1
        elif node.right == -1:
            x = self.height(node.left)
            node.height = x
            return x + 1
        else:
            x = max(self.height(node.left), self.height(node.right)) + 1
            node.height = x
            return x
class Node:
    def __init__(self, label, left = -1, right = -1):
        self.label = label
        self.type_ = "root"
        self.parent = -1
        self.sibling = -1
        self.depth = 0
        self.height = 0
        self.degree = 0
        self.left = left
        self.right = right

tree = Tree()
n = int(input())
for i in range(n):
    tree.nodes.append(Node(i))
for i in range(n):
    num, left, right = map(int, input().split())
    tree.insert(num, left, right)
for i in tree.nodes:
    if i.parent == -1:
        tree.depth(i)
        tree.height(i)
if n == 1:
    tree.nodes[0].type_ = "root"
for i in tree.nodes:
    print("node {0:}: parent = ".format(i.label), end = "")
    if i.parent == -1:
        print(i.parent, end = "")
    else:
        print(i.parent.label, end = "")
    print(", sibling = {0:}, degree = {1:}, depth = {2:}, height = {3:}, {4:}".format(i.sibling, i.degree, i.depth, i.height, i.type_))

Submission status: Wrong Answer

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


n = int(input())
binary_tree = [Node() for i in range(n)]
h, d = [0 for j in range(n)], [0 for k in range(n)]


def set_height(u):
    h1 = h2 = 0
    if binary_tree[u].right != -1:
        h1 = set_height(binary_tree[u].right) + 1
    if binary_tree[u].left != -1:
        h2 = set_height(binary_tree[u].left) + 1

    h[u] = max(h1, h2)
    return h[u]


def set_depth(u, dep):
    d[u] = dep
    if binary_tree[u].right != -1:
        set_depth(binary_tree[u].right, dep+1)
    if binary_tree[u].left != -1:
        set_depth(binary_tree[u].left, dep+1)

    return d[u]


def set_sibling(u):
    if binary_tree[binary_tree[u].parent].left != u:
        return binary_tree[binary_tree[u].parent].left
    else:
        return binary_tree[binary_tree[u].parent].right


def set_degree(u):
    cnt = 0
    if binary_tree[u].left != -1:
        cnt += 1
    if binary_tree[u].right != -1:
        cnt += 1
    return cnt


def set_type(u):
    if binary_tree[u].parent == -1:
        return "root"
    elif binary_tree[u].left == -1 and binary_tree[u].right == -1:
        return "leaf"
    else:
        return "internal node"


def main():
    for i in range(n):
        idx, left, right = map(int, input().split())
        binary_tree[idx].left = left
        binary_tree[idx].right = right
        if left != -1:
            binary_tree[left].parent = idx
        if right != -1:
            binary_tree[right].parent = idx

    # 根の探索
    root_idx = 0
    for i in range(n):
        if binary_tree[i].parent == -1:
            root_idx = i
            break

    # 各ノードの高さを求める
    set_height(root_idx)

    # 各ノードの深さを求める
    set_depth(0, 0)

    for i in range(n):
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, "
              "height = {}, type = {}".format(i, binary_tree[i].parent,
                set_sibling(i), set_degree(i), d[i], h[i], set_type(i)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


n = int(input())
binary_tree = [Node() for i in range(n)]
h, d = [0 for j in range(n)], [0 for k in range(n)]


def set_height(u):
    h1 = h2 = 0
    if binary_tree[u].right != -1:
        h1 = set_height(binary_tree[u].right) + 1
    if binary_tree[u].left != -1:
        h2 = set_height(binary_tree[u].left) + 1

    h[u] = max(h1, h2)
    return h[u]


def set_depth(u, dep):
    d[u] = dep
    if binary_tree[u].right != -1:
        set_depth(binary_tree[u].right, dep+1)
    if binary_tree[u].left != -1:
        set_depth(binary_tree[u].left, dep+1)

    return d[u]


def set_sibling(u):
    if binary_tree[binary_tree[u].parent].left != u:
        return binary_tree[binary_tree[u].parent].left
    else:
        return binary_tree[binary_tree[u].parent].right


def set_degree(u):
    cnt = 0
    if binary_tree[u].left != -1:
        cnt += 1
    if binary_tree[u].right != -1:
        cnt += 1
    return cnt


def set_type(u):
    if binary_tree[u].parent == -1:
        return "root"
    elif binary_tree[u].left == -1 and binary_tree[u].right == -1:
        return "leaf"
    else:
        return "internal node"


def main():
    for i in range(n):
        idx, left, right = map(int, input().split())
        binary_tree[idx].left = left
        binary_tree[idx].right = right
        if left != -1:
            binary_tree[left].parent = idx
        if right != -1:
            binary_tree[right].parent = idx

    # 根の探索
    root_idx = 0
    for i in range(n):
        if binary_tree[i].parent == -1:
            root_idx = i
            break

    # 各ノードの高さを求める
    set_height(root_idx)

    # 各ノードの深さを求める
    set_depth(0, 0)

    for i in range(n):
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, "
              "height = {}, {}".format(i, binary_tree[i].parent,
                set_sibling(i), set_degree(i), d[i], h[i], set_type(i)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class NullNode():
    def __init__(self):
        self.id = -1

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

    def __str__(self):
        return '{} {} {} {} {}'.format(self.id, self.parent.id, self.left.id, self.right.id, self.sibling.id)

    def getHeight(self, height=0):
        if self.left.id != -1:
            height += 1
            height = self.left.getHeight(height)
        elif self.right.id != -1:
            height += 1
            height = self.right.getHeight(height)
        return height

    def getDepth(self, depth=0):
        if self.parent.id != -1:
            depth += 1
            if depth < 5:
                print(self.parent.id, self.id)
            depth = self.parent.getDepth(depth)
        return depth

    def getDegree(self):
        degree = 0
        if self.left.id != -1:
            degree += 1
        if self.right.id != -1:
            degree += 1
        return degree

    def getType(self):
        if self.parent.id == -1:
            return 'root'
        elif self.left.id == -1 and self.right.id == -1:
            return 'leaf'
        else:
            return 'internal node'

n = int(input())
node_list = [Node(id) for id in range(n)]
for i in range(n):
    [id, left, right] = [int(j) for j in input().split()]
    i_node = node_list[id]
    if left != -1:
        i_node.left = node_list[left]
        node_list[left].parent = node_list[id]
        node_list[left].sibling = node_list[right]
    if right != -1:
        i_node.right = node_list[right]
        node_list[right].parent = node_list[id]
        node_list[right].sibling = node_list[left]

for id in range(n):
    i_node = node_list[id]
    parent = i_node.parent.id
    sibling = i_node.sibling.id
    degree = i_node.getDegree()
    depth = i_node.getDepth()
    height = i_node.getHeight()
    type = i_node.getType()
    print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}'.format(id, parent, sibling, degree, depth, height, type))

Submission status: Wrong Answer

Solution code:
class NullNode():
    def __init__(self):
        self.id = -1

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

    def __str__(self):
        return '{} {} {} {} {}'.format(self.id, self.parent.id, self.left.id, self.right.id, self.sibling.id)

    def getHeight(self, height=0):
        if self.left.id != -1:
            height += 1
            height = self.left.getHeight(height)
        elif self.right.id != -1:
            height += 1
            height = self.right.getHeight(height)
        return height

    def getDepth(self, depth=0):
        if self.parent.id != -1:
            depth += 1
            depth = self.parent.getDepth(depth)
        return depth

    def getDegree(self):
        degree = 0
        if self.left.id != -1:
            degree += 1
        if self.right.id != -1:
            degree += 1
        return degree

    def getType(self):
        if self.parent.id == -1:
            return 'root'
        elif self.left.id == -1 and self.right.id == -1:
            return 'leaf'
        else:
            return 'internal node'

n = int(input())
node_list = [Node(id) for id in range(n)]
for i in range(n):
    [id, left, right] = [int(j) for j in input().split()]
    i_node = node_list[id]
    if left != -1:
        i_node.left = node_list[left]
        node_list[left].parent = node_list[id]
        node_list[left].sibling = node_list[right]
    if right != -1:
        i_node.right = node_list[right]
        node_list[right].parent = node_list[id]
        node_list[right].sibling = node_list[left]

for id in range(n):
    i_node = node_list[id]
    parent = i_node.parent.id
    sibling = i_node.sibling.id
    degree = i_node.getDegree()
    depth = i_node.getDepth()
    height = i_node.getHeight()
    type = i_node.getType()
    print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}'.format(id, parent, sibling, degree, depth, height, type))

Submission status: Wrong Answer

Solution code:
class NullNode():
    def __init__(self):
        self.id = -1

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

    def __str__(self):
        return '{} {} {} {} {}'.format(self.id, self.parent.id, self.left.id, self.right.id, self.sibling.id)

    def getHeight(self, right_height=0, left_height=0):
        if self.left.id != -1:
            left_height += 1
            left_height = self.left.getHeight(left_height, left_height)
        if self.right.id != -1:
            right_height += 1
            right_height = self.right.getHeight(right_height, right_height)
        return max(left_height, right_height)

    def getDepth(self, depth=0):
        if self.parent.id != -1:
            depth += 1
            depth = self.parent.getDepth(depth)
        return depth

    def getDegree(self):
        degree = 0
        if self.left.id != -1:
            degree += 1
        if self.right.id != -1:
            degree += 1
        return degree

    def getType(self):
        if self.parent.id == -1:
            return 'root'
        elif self.left.id == -1 and self.right.id == -1:
            return 'leaf'
        else:
            return 'internal node'

n = int(input())
node_list = [Node(id) for id in range(n)]
for i in range(n):
    [id, left, right] = [int(j) for j in input().split()]
    i_node = node_list[id]
    if left != -1:
        i_node.left = node_list[left]
        node_list[left].parent = node_list[id]
        node_list[left].sibling = node_list[right]
    if right != -1:
        i_node.right = node_list[right]
        node_list[right].parent = node_list[id]
        node_list[right].sibling = node_list[left]

for id in range(n):
    i_node = node_list[id]
    parent = i_node.parent.id
    sibling = i_node.sibling.id
    degree = i_node.getDegree()
    depth = i_node.getDepth()
    height = i_node.getHeight()
    type = i_node.getType()
    print('node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}'.format(id, parent, sibling, degree, depth, height, type))

Submission status: Wrong Answer

Solution code:
#coding:utf-8

n = int(input())
T = [list(map(int, input().split())) for i in range(n)]
A = []

class binaryTree:
    def __init__(self, x, y, z):
        self.data = x
        self.par = y
        self.depth = z
        
    def makeTree(self,tree):
        parID = tree.data[0]
        t = T[parID]
        depth = tree.depth
        
        if tree.par == -1:
            tree.kind = "root"
        elif t[1] == -1 and t[2] == -1:
            tree.kind = "leaf"
        else:
            tree.kind = "international node"

        if t[1] == -1 and t[2] == -1:
            tree.deg = 0
            tree.l = None
            tree.r = None

        if t[1] != -1:
            tree.l = binaryTree(T[t[1]], parID, depth+1)
            l_tree = tree.l
            if t[2] != -1:
                tree.deg = 2
                l_tree.sib = t[2]
            else:
                tree.deg = 1
                l_tree.sib = -1
            self.makeTree(self, l_tree)
        
        else:
            tree.l = None

        if t[2] != -1:
            tree.r = binaryTree(T[t[2]], parID, depth+1)
            r_tree = tree.r
            if t[1] != -1:
                tree.deg = 2
                r_tree.sib = t[1]
            else:
                tree.deg = 1
                r_tree.sib = -1
            self.makeTree(self, r_tree)
        else:
            tree.r = None


def setHeight(tree):
    h1 = h2 = 0
    if tree.l != None:
        h1 = setHeight(tree.l) + 1
    if tree.r != None:
        h2 = setHeight(tree.r) + 1
    if tree.r == None and tree.l == None:
        tree.hei = 0
        return 0
    tree.hei = max(h1,h2)
    return max(h1, h2)


par = -1
depth = 0
tree = binaryTree(T[0], par,depth)
tree.sib = -1

binaryTree.makeTree(binaryTree, tree)
setHeight(tree)
  

ID = tree.data[0]
parent = tree.par
sibling = tree.sib
degree = tree.deg
depth = tree.depth
height = tree.hei
kind = tree.kind


def printer(tree):
        ID = tree.data[0]
        parent = tree.par
        sibling = tree.sib
        degree = tree.deg
        depth = tree.depth
        height = tree.hei
        kind = tree.kind
        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"\
              .format(ID, parent, sibling, degree, depth, height, kind))

        if tree.l != None:
            l_tree = tree.l
            printer(l_tree)

        if tree.r != None:
            r_tree = tree.r
            printer(r_tree)
        
printer(tree)

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
n = int(input())
node_list = [{
    'left_child': -1,
    'right_child': -1,
    'parent': -1,
    'sibling': -1,
    'degree': 0,
    'depth': 0,
    'height': 0,
    'type': 'root',
} for i in range(n)]

for i in range(n):
    id, left, right = map(int, input().split())
    if left != -1:
        node_list[id]['left_child'] = left
        node_list[left]['parent'] = id
        node_list[left]['sibling'] = right
    if right != -1:
        node_list[id]['right_child'] = right
        node_list[right]['parent'] = id
        node_list[right]['sibling'] = left
    node_list[id]['degree'] = 2 - [left, right].count(-1)

def know_depth(id):
    if node_list[id]['parent'] == -1:
        return 0
    else:
        return 1 + know_depth(node_list[id]['parent'])

def know_height(id):
    if node_list[id]['left_child'] == -1 and node_list[id]['right_child'] == -1:
        return 0
    else:
        height_left = 0
        height_right = 0
        if node_list[id]['left_child'] != -1:
            height_left = know_height(node_list[id]['left_child'])
        if node_list[id]['right_child'] != -1:
            height_right = know_height(node_list[id]['right_child'])
        return 1 + max(height_left, height_right)

for id, node in enumerate(node_list):
    node['depth'] = know_depth(id)
    node['height'] = know_height(id)
    if node['parent'] != -1:
        node['type'] = 'internal node'
    if node['left_child'] == -1 and node['right_child'] == -1:
        node['type'] = 'leaf'
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
        id,
        node['parent'],
        node['sibling'],
        node['degree'],
        node['depth'],
        node['height'],
        node['type']
    ))

Submission status: Time Limit Exceeded

Solution code:
NIL = -1

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

n = int(input())
t = [Node() for i in range(n)]

for i in range(n):
    a = list(map(int, input().split()))
    if a[1] != -1:
        t[i].left = a[1]
        t[a[1]].parent = i
    if a[2] != -1:
        t[i].right = a[2]
        t[a[2]].parent = i

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

d = []
for i in range(i):
    b = getdepth(i)
    d.append(b)



for i in range(n):
    c = 0
    if t[i].left != NIL:
        c += 1
    if t[i].right != NIL:
        c += 1

    if t[i].parent == NIL:
        cond = "root"
    elif t[i].left == NIL and t[i].right == NIL:
        cond = "leaf"
    else:
        cond = "internal node"

    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
          .format(i, t[i].parent, d.count(d[i]), c, d[i], max(d)-d[i], cond))

Submission status: Time Limit Exceeded

Solution code:
NIL = -1

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

n = int(input())
t = [Node() for i in range(n)]

for i in range(n):
    a = list(map(int, input().split()))
    if a[1] != -1:
        t[i].left = a[1]
        t[a[1]].parent = i
    if a[2] != -1:
        t[i].right = a[2]
        t[a[2]].parent = i

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

d = []
for i in range(i):
    b = getdepth(i)
    d.append(b)

m = max(d)


for i in range(n):
    c = 0
    if t[i].left != NIL:
        c += 1
    if t[i].right != NIL:
        c += 1

    if t[i].parent == NIL:
        cond = "root"
    elif t[i].left == NIL and t[i].right == NIL:
        cond = "leaf"
    else:
        cond = "internal node"

    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
          .format(i, t[i].parent, d.count(d[i]), c, d[i], m-d[i], cond))

Submission status: Time Limit Exceeded

Solution code:
NIL = -1

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

n = int(input())
t = [Node() for i in range(n)]

for i in range(n):
    a = list(map(int, input().split()))
    if a[1] != -1:
        t[i].left = a[1]
        t[a[1]].parent = i
    if a[2] != -1:
        t[i].right = a[2]
        t[a[2]].parent = i

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

d = []
for i in range(n):
    b = getdepth(i)
    d.append(b)

m = max(d)


for i in range(n):
    c = 0
    if t[i].left != NIL:
        c += 1
    if t[i].right != NIL:
        c += 1

    if t[i].parent == NIL:
        cond = "root"
    elif t[i].left == NIL and t[i].right == NIL:
        cond = "leaf"
    else:
        cond = "internal node"

    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
          .format(i, t[i].parent, d.count(d[i]), c, d[i], m-d[i], cond))

Submission status: Time Limit Exceeded

Solution code:
NIL = -1

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

n = int(input())
t = [Node() for i in range(n)]

for i in range(n):
    a = list(map(int, input().split()))
    if a[1] != -1:
        t[i].left = a[1]
        t[a[1]].parent = i
    if a[2] != -1:
        t[i].right = a[2]
        t[a[2]].parent = i

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

d = []
for i in range(n):
    b = getdepth(i)
    d.append(b)

m = max(d)

posi = [0 for i in range(n)]
for i in range(n):
    posi[d[i]] += 1

for i in range(n):
    c = 0
    if t[i].left != NIL:
        c += 1
    if t[i].right != NIL:
        c += 1

    if t[i].parent == NIL:
        cond = "root"
    elif t[i].left == NIL and t[i].right == NIL:
        cond = "leaf"
    else:
        cond = "internal node"

    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
          .format(i, t[i].parent, posi[d[i]], c, d[i], m-d[i], cond))

Submission status: Time Limit Exceeded

Solution code:
NIL = -1

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

n = int(input())
t = [Node() for i in range(n)]

for i in range(n):
    a = list(map(int, input().split()))
    if a[1] != -1:
        t[i].left = a[1]
        t[a[1]].parent = i
    if a[2] != -1:
        t[i].right = a[2]
        t[a[2]].parent = i

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

d = []
for i in range(n):
    b = getdepth(i)
    d.append(b)

def setheight(u):
    h1 = 0
    h2 = 0
    if t[u].right != NIL:
        h1 = setheight(t[u].right) + 1
    if t[u].left != NIL:
        h2 = setheight(t[u].left) + 1
    h = max(h1, h2)
    return h


for i in range(n):
    c = 0
    if t[i].left != NIL:
        c += 1
    if t[i].right != NIL:
        c += 1

    if t[i].parent == NIL:
        cond = "root"
    elif t[i].left == NIL and t[i].right == NIL:
        cond = "leaf"
    else:
        cond = "internal node"

    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
          .format(i, t[i].parent, d.count(d[i]), c, d[i], setheight(i), cond))

Submission status: Time Limit Exceeded

Solution code:
NIL = -1

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

n = int(input())
t = [Node() for i in range(n)]

for i in range(n):
    a = list(map(int, input().split()))
    if a[1] != -1:
        t[i].left = a[1]
        t[a[1]].parent = i
    if a[2] != -1:
        t[i].right = a[2]
        t[a[2]].parent = i

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

d = []
for i in range(n):
    b = getdepth(i)
    d.append(b)

def setheight(u):
    h1 = 0
    h2 = 0
    if t[u].right != NIL:
        h1 = setheight(t[u].right) + 1
    if t[u].left != NIL:
        h2 = setheight(t[u].left) + 1
    h = max(h1, h2)
    return h

def sibling(u):
    if t[u].parent == NIL:
        return NIL
    if t[t[u].parent].left != NIL:
        return t[t[u].parent].left
    if t[t[u].parent].right != NIL:
        return t[t[u].parent].right
    else:
        return NIL
        
for i in range(n):
    c = 0
    if t[i].left != NIL:
        c += 1
    if t[i].right != NIL:
        c += 1

    if t[i].parent == NIL:
        cond = "root"
    elif t[i].left == NIL and t[i].right == NIL:
        cond = "leaf"
    else:
        cond = "internal node"

    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
          .format(i, t[i].parent, sibling(i), c, d[i], setheight(i), cond))

Submission status: Time Limit Exceeded

Solution code:
NIL = -1

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

n = int(input())
t = [Node() for i in range(n)]

for i in range(n):
    a = list(map(int, input().split()))
    if a[1] != -1:
        t[i].left = a[1]
        t[a[1]].parent = i
    if a[2] != -1:
        t[i].right = a[2]
        t[a[2]].parent = i

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

d = []
for i in range(n):
    b = getdepth(i)
    d.append(b)

def setheight(u):
    h1 = 0
    h2 = 0
    if t[u].right != NIL:
        h1 = setheight(t[u].right) + 1
    if t[u].left != NIL:
        h2 = setheight(t[u].left) + 1
    h = max(h1, h2)
    return h

def sibling(u):
    if t[u].parent == NIL:
        return NIL
    if t[t[u].parent].left != NIL and t[t[u].parent].left != u:
        return t[t[u].parent].left
    if t[t[u].parent].right != NIL and t[t[u].parent].right != u:
        return t[t[u].parent].right
    else:
        return NIL

for i in range(n):
    c = 0
    if t[i].left != NIL:
        c += 1
    if t[i].right != NIL:
        c += 1

    if t[i].parent == NIL:
        cond = "root"
    elif t[i].left == NIL and t[i].right == NIL:
        cond = "leaf"
    else:
        cond = "internal node"

    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}"
          .format(i, t[i].parent, sibling(i), c, d[i], setheight(i), cond))

Submission status: Accepted

Solution code:
def search(ps, id):
    if ps[id] == -1:
        return 0
    else:
        return 1 + search(ps, ps[id])


def search_part2(tree, id):
    if tree[id][0] == -1:
        left = -1
    else:
        left = search_part2(tree, tree[id][0])

    if tree[id][1] == -1:
        right = -1
    else:
        right = search_part2(tree, tree[id][1])

    return 1 + max(left, right)


n = int(input())
tree = [[] for _ in range(n)]
ps = [-1 for _ in range(n)]
ss = [-1 for _ in range(n)]

for _ in range(n):
    s = input().split()
    id = int(s[0])
    left = int(s[1])
    right = int(s[2])
    tree[id] = [left, right]
    if left >= 0:
        ps[left] = id
        ss[left] = right
    if right >= 0:
        ps[right] = id
        ss[right] = left

for id in range(n):
    p = ps[id]
    s = ss[id]
    deg = int(tree[id][0] >= 0) + int(tree[id][1] >= 0)
    d = search(ps, id)
    h = search_part2(tree, id)

    if p == -1:
        type = "root"
    elif tree[id][0] == -1 and tree[id][1] == -1:
        type = "leaf"
    else:
        type = "internal node"

    print("node " + str(id) + ": parent = " + str(p) + ", sibling = " + str(s) + ", degree = " + str(
        deg) + ", depth = " + str(d) + ", height = " + str(h) + ", " + type)

Submission status: Accepted

Solution code:
n = int(input())
tree = [0] * n
root = set(range(n))
def type(i, parent, sibling, depth):
    if i == -1:
        return -1
    node = tree[i]
    l, r = node[0], node[1]
    node[2], node[3], node[5] = parent, sibling, depth
    node[4] = (l != -1) + (r != -1)
    h = node[6] = max(type(l, i, r, depth + 1), type(r, i, l, depth + 1)) + 1
    return h
 
while n:
    i, l, r = list(map(int, input().split()))
    tree[i] = [l, r] + [0] * 5
    root -= {l, r}
    n -= 1
type(root.pop(), -1, -1, 0)
for i, node in enumerate(tree):
    l, r, p, s, deg, dep, h = node
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i, p, s, deg, dep, h, 'root' if not dep else 'internal node' if deg else 'leaf'))