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: Accepted

Solution code:
class Node:
    def __init__(self, data):
        self.data = data #ノードが持つ数値
        self.depth = None
        self.children = None
#解答 dfs…深さ優先探索
class Node:
  def __init__(self):
    self.parent = -1
    self.sibling = -1

def dfs(v, d = 0):
  G[v].depth, G[v].height = d, 0
  if G[v].left != -1:
    G[v].height = max(G[v].height, dfs(G[v].left, d + 1) + 1)
  if G[v].right != -1:
    G[v].height = max(G[v].height, dfs(G[v].right, d + 1) + 1)
  return G[v].height

N = int(input())
G = [Node() for _ in range(N)]
for _ in range(N):
  idx, *children = [int(x) for x in input().split()]
  G[idx].left, G[idx].right = children
  if G[idx].left != -1 and G[idx].right != -1:
    G[G[idx].left].sibling, G[G[idx].right].sibling = G[idx].right, G[idx].left #兄弟を設定
  if G[idx].left != -1 or G[idx].right != -1:
    G[idx].type = 'internal node'
  else:
    G[idx].type = 'leaf'
  for child in children:
    if child != -1:
      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 = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i, node.parent, node.sibling, (node.left != -1) + (node.right != -1), node.depth, node.height, node.type))

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, id):
        self.id = id
        self.parent = -1
        self.left = -1
        self.right = -1
    
    def get_depth(self):
        if self.parent == -1:
            return 0
        else:
            return nodes[self.parent].get_depth() + 1

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

    def get_height(self):
        # if self.parent != -1:
        #     return 0
        max_height = 0
        if self.left != -1:
            max_height = nodes[self.left].get_height() + 1
            # print("left", max_height)
        if self.right != -1:
            max_height = max(max_height, nodes[self.right].get_height() + 1)
            # print("right", max_height)
        return max_height
    
    def get_sibling(self):
        if self.parent == -1:
            return -1
        
        if nodes[self.parent].left == self.id:
            return nodes[self.parent].right
        else:
            return nodes[self.parent].left

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

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


for i in range(n):
    # node
    i, left, right = map(int, input().split())
    nodes[i].left = left
    nodes[i].right = right

    # parent
    if left != -1:
        nodes[left].parent = i
    if right != -1:
        nodes[right].parent = i

    # if i == 4:
    #     print("----------")
    #     print(left, nodes[left].parent, right, nodes[right].parent)
    #     print("----------")
    # for j in range(n):
    #     if j == 8:
    #         print('----------')
    #         print(i, nodes[j].parent)
    #         print('----------')


# 出力
for i in range(n):
    print('node {id}: parent = {p}, sibling = {s}, degree = {degree}, depth = {depth}, height = {height}, {type}'.format(
        id=i,
        p=nodes[i].parent,
        s=nodes[i].get_sibling(),
        degree=nodes[i].get_degree(),
        depth=nodes[i].get_depth(),
        height=nodes[i].get_height(),
        type=nodes[i].get_type(),
    ))

Submission status: Accepted

Solution code:
class Tree(object):
    def __init__(self):
        self.nodes = {}
        self.root = None

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

    def set_depth(self):
        for node in self.nodes.values():
            if node.type == 'root':
                self.root = node
                break
        self.root._set_depth(0)

    def set_height(self):
        # メモ化して再帰する
        self.root._set_height()


class Node(object):
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.children = []
        self.depth = None
        self.height = None
        self.type = 'root'
        self.bro = None

    def add_child(self, child):
        child.bro = len(self.children)
        self.children.append(child)
        child.parent = self
        child.update_nodetype()
        if self.parent:
            self.update_nodetype()

    def update_nodetype(self):
        if self.parent:
            if self.children:
                self.type = 'internal node'
            else:
                self.type = 'leaf'
        else:
            self.type = 'root'

    def _set_depth(self, depth):
        self.depth = depth
        for child in self.children:
            child._set_depth(depth+1)

    def _set_height(self):
        # メモ化再帰
        if not self.children:
            self.height = 0
        else:
            if self.height:
                pass
            else:
                height = 0
                for child in self.children:
                    child._set_height()
                    height = max(child.height, height)
                self.height = height + 1

    def get_sib(self):
        if not self.parent:
            return -1
        else:
            bros = self.parent.children
            if len(bros) == 1:
                return -1
            else:
                if self.bro == 0:
                    return bros[1].id
                else:
                    return bros[0].id

    def __str__(self):
        parent = self.parent.id if self.parent else -1
        sib = self.get_sib()
        deg = len(self.children)
        dep = self.depth
        h = self.height
        str = 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(id, parent, sib, deg, dep, h, self.type)
        return str


tree = Tree()
n = int(input())
for i in range(n):
    tmp = list(map(int, input().split()))
    id = tmp[0]
    children = tmp[1:]
    tree.add_node(id)
    for c in children:
        if c != -1:
            tree.add_child(id, c)
tree.set_depth()
tree.set_height()
for id in range(n):
    print(tree.nodes[id])

Submission status: Accepted

Solution code:
n = int(input())
parent = [-1] * n
left   = [-1] * n
right  = [-1] * n
sibling = [-1] * n
degree  =  [0] * n
depth   =  [0] * n
for i in range(n):
    x = list(map(int, input().split()))
    left[x[0]]  = x[1]
    right[x[0]] = x[2]
    children = 0
    if x[1] != -1:
        parent[x[1]] = x[0]
        sibling[x[1]] = x[2]
        children += 1
    if x[2] != -1:
        parent[x[2]] = x[0]
        sibling[x[2]] = x[1]
        children += 1
    degree[x[0]] = children
def setDepth(u, p, d):
    d[u] = p
    if right[u] != -1:
        setDepth(right[u], p + 1, d)
    if left[u] != -1:
        setDepth(left[u], p + 1, d)
    return d
def getHeight(u, p, height):
    height += [p]
    if right[u] != -1:
        getHeight(right[u], p + 1, height)
    if left[u] != -1:
        getHeight(left[u], p + 1, height)
    return max(height)
def howNode(u):
    if parent[u] == -1:
        return 'root'
    elif left[u] == right[u] == -1:
        return 'leaf'
    else:
        return 'internal node'
root = parent.index(-1)
setDepth(root, 0, depth)
for i in range(n):
    print('node '+str(i)+': parent = '+str(parent[i])
    +', sibling = '+str(sibling[i])+', degree = '+
    str(degree[i])+', depth = '+str(depth[i])+', height = '
    +str(getHeight(i, 0, []))+', '+howNode(i))

Submission status: Accepted

Solution code:
n = int(input())

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

    def addChild(self,child):
        self.child = child

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

nodes = {}
for i in range(n):
    line = list(input().split(" "))
    id = int(line[0])
    if not id in nodes:
        nodes[id] = Node(id)
    child = []
    for j in range(1,3):
        if not int(line[j]) == -1:
            child.append(int(line[j]))
    nodes[id].addChild(child)

    for ele in child:
        if not ele in nodes:
            nodes[ele] = Node(ele)
        nodes[ele].setParent(id)

def culcHeight(nodes,id,counter):
    objNode = nodes[id]
    children = objNode.child
    if children == []:
        return counter
    else:
        counter += 1
        results = []
        for chili in children:
            a = culcHeight(nodes,chili,counter)
            results.append(a)
        return max(results)

for i in sorted(nodes):
    node = nodes[i]
    ans = ''
    ans += 'node ' + str(i) + ': parent = '
    ans += str(node.parent) + ', sibling = '


    if node.parent == -1:
        ans += str(-1)
        children = []
    else:
        children = nodes[node.parent].child
        if children == [node.id]:
            ans += str(-1)
        else:
            for k in children:
                if not k == i:
                    ans += str(k)



    ans += ', degree = ' + str(len(node.child))


    ans += ', depth = '


    startnode = node
    count = 0
    while not startnode.parent == -1:
        startnode = nodes[startnode.parent]
        count += 1
    ans += str(count)


    ans += ', height = '
    ans += str(culcHeight(nodes,i,0))
    ans += ', '
    if node.parent == -1:
        type = 'root'
    else:
        if node.child == []:
            type = 'leaf'
        else:
            type = 'internal node'
    ans += type
    print(ans)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self):
        self.id = -1
        self.parent = None
        self.childs = [None, None]
        self.sibling = -1
        self.depth = -1
        self.height = -1

    def parentId(self):
        return -1 if self.parent == None else self.parent.id

    def type(self):
        if self.parent == None:
            return "root"
        elif self.childs[0] != None or self.childs[1] != None:
            return "internal node"
        return "leaf"

    def degree(self):
        r = 0
        for c in self.childs:
            r += 1 if c != None else 0
        return r


def setDepthAndHeight(node, d):
    h = 0
    node.depth = d
    for i in range(2):
        if node.childs[i] != None:
            h = max(h, setDepthAndHeight(node.childs[i], d+1)+1)
    node.height = h
    return h


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

for i in range(n):
    id, l, r = map(int, input().split())
    p = nodes[id]
    p.id = id
    if l >= 0:
        nodes[l].parent = p
        nodes[l].sibling = r
        p.childs[0] = nodes[l]
    if r >= 0:
        nodes[r].parent = p
        nodes[r].sibling = l
        p.childs[1] = nodes[r]

root = None
for node in nodes:
    if node.type() == "root":
        root = node
        break

setDepthAndHeight(root, 0)

for node in nodes:
    s = f"node {node.id}: "
    s += f"parent = {node.parentId()}, "
    s += f"sibling = {node.sibling}, "
    s += f"degree = {node.degree()}, "
    s += f"depth = {node.depth}, "
    s += f"height = {node.height}, "
    s += f"{node.type()}"
    print(s)

Submission status: Accepted

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

    @property
    def depth(self):
        count = 0
        p = self.parent
        while p is not None:
            count += 1
            p = p.parent
        return count

    @property
    def height(self):
        if self.left is None and self.right is None:
            return 0
        elif self.left is None:
            return 1 + self.right.height
        elif self.right is None:
            return 1 + self.left.height
        else:
            left_h = 1 + self.left.height
            right_h = 1 + self.right.height
            return max(left_h, right_h)

    @property
    def sibling(self):
        if self.parent is None:
            return -1
        for node in [self.parent.right, self.parent.left]:
            if node is None:
                return -1
            if node.n != self.n:
                return node.n

    @property
    def degree(self):
        count = 0
        if self.right:
            count += 1
        if self.left:
            count += 1
        return count

    @property
    def type(self):
        if self.parent is None:
            return "root"
        elif self.left is None and self.right is None:
            return "leaf"
        else:
            return "internal node"

    def __str__(self):
        if self.parent is None:
            parent = -1
        else:
            parent = self.parent.n

        return "node {}: parent = {}, sibling = {}, degree = {}, " \
               "depth = {}, height = {}, {}".format(
            self.n, parent, self.sibling, self.degree,
            self.depth, self.height, self.type
        )


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

for _ in range(n):
    x, y, z = map(int, input().split())
    node = nodes[x]

    if y == -1:
        node.left = None
    else:
        nodes[y].parent = node
        node.left = nodes[y]

    if z == -1:
        node.right = None
    else:
        nodes[z].parent = node
        node.right = nodes[z]

for n in nodes:
    print(n)

Submission status: Accepted

Solution code:
# coding: utf-8
import queue

class Node:
    def __init__(self, myNum, left, right):
        self.myNum = myNum
        self.left = left
        self.right = right
        self.parent = -1
        self.bs = -1
        self.nodeType = ""
        self.degree = -1
        self.depth = -1
        self.height = -1

        
nodes = []
n = int(input().rstrip())
for i in range(n):
    line = [int(j) for j in input().rstrip().split()]
    nodes.append(Node(line[0],line[1],line[2]))

nodes = sorted(nodes, key = lambda x: x.myNum)

# 親ノード、degreeを設定する
for node in nodes:
    dg = 0
    if node.left != -1:
        nodes[node.left].parent = node.myNum
        dg += 1
    if node.right != -1:
        nodes[node.right].parent = node.myNum
        dg += 1
    node.degree = dg

# 兄弟ノードを設定する
for node in nodes:
    if node.left != -1 and node.right != -1:
        nodes[node.left].bs = nodes[node.right].myNum
        nodes[node.right].bs = nodes[node.left].myNum

# nodeTypeを設定する
for node in nodes:
    if node.parent == -1:
        node.nodeType = "root"
        node.depth = 0
        rootNum = node.myNum
    elif node.left == -1 and node.right == -1:
        node.nodeType = "leaf"
    else:
        node.nodeType = "internal node"

# depthを設定する
q = queue.Queue()
q.put(nodes[rootNum])
while not q.empty():
    nd = q.get()
    if nd.left != -1:
        nodes[nd.left].depth = nd.depth + 1
        q.put(nodes[nd.left])
    if nd.right != -1:
        nodes[nd.right].depth = nd.depth + 1
        q.put(nodes[nd.right])

# heightを設定する
for node in nodes:
    if node.parent == -1 or node.nodeType == "leaf":
        node.height = 0
        q.put(node)
while not q.empty():
    nd = q.get()
    if nd.parent != -1:
        nodes[nd.parent].height = max(nodes[nd.parent].height, nd.height + 1)
        q.put(nodes[nd.parent])

# 出力！
for node in nodes:
    print("node {0}: parent = {1}, sibling = {2}, degree = {3}, depth = {4}, height = {5}, {6}"
          .format(node.myNum, node.parent, node.bs, node.degree, node.depth, node.height, node.nodeType))

Submission status: Accepted

Solution code:
from sys import stdin

class Node:
    def __init__(self):
        self.parent = -1
        self.sibling = -1
        self.depth = -1
        self.height = -1
        self.children = [-1, -1]

class Tree:
    def __init__(self, nodes):
        self.nodes = nodes
        for i in range(self.size()):
            n = self.nodes[i]
            n.depth = self.depth(i)
            n.height = self.height(i)

    def depth(self, i):
        node = self.nodes[i]
        if self.isRoot(i):
            return 0
        else:
            return self.depth(node.parent)+1

    def height(self, i):
        node = self.nodes[i]
        if i == -1:
            return -1
        else:
            return max([self.height(c) for c in node.children])+1

    def size(self):
        return len(self.nodes)

    def isLeaf(self, i):
        return self.nodes[i].children == [-1, -1]

    def isRoot(self, i):
        return self.nodes[i].parent == -1

n = int(stdin.readline().rstrip())
nodes = [Node() for _ in range(n)]
for i in range(n):
    l = [int(x) for x in stdin.readline().rstrip().split()]
    nodes[l[0]].children = l[1:3]
    if l[1] != -1:
        nodes[l[1]].parent = l[0]
        nodes[l[1]].sibling = l[2]
    if l[2] != -1:
        nodes[l[2]].parent = l[0]
        nodes[l[2]].sibling = l[1]

t = Tree(nodes)
for i in range(t.size()):
    node = t.nodes[i]
    l = ["node ", i, ": parent = ", node.parent, ", sibling = ", node.sibling, ", degree = ", len([c for c in node.children if c != -1]), ", depth = ", node.depth, ", height = ", node.height, ", "]

    if t.isRoot(i):
        l.append("root")
    elif t.isLeaf(i):
        l.append("leaf")
    else:
        l.append("internal node")

    print(*l, sep="")

Submission status: Accepted

Solution code:
class node:
    parent = None
    depth = 0
    degree = 0
    height = 0

    def __init__(self, no, l, r,sib):
        self.no = no
        self.left = l
        self.right = r
        self.sibling = sib
    
    def setsibdepth(self, nodes, d):
        if self.left is None:
            return
        self.depth = d
        self.left.sibling = self.right
        self.right.sibling = self.left
        self.left.setsibdepth(nodes, d+1)
        self.right.setsibdepth(nodes, d+1)

    def setheight(self, nodes, h):
        if self.left is None:
            return h-1
        return max(self.left.setheight(nodes, h+1), self.right.setheight(nodes, h+1))

#葉はNULL, 根の親はNone

NULL = node(-1, None, None, None)
head = None
nodes = []
n = int(input())
for i in range(n):
    temp = node(i, None, None, NULL)
    nodes.append(temp)

for i in range(n):
    temp = list(map(int,input().split()))
    if temp[1] == -1:
        nodes[temp[0]].left = NULL
    else:
        nodes[temp[0]].left = nodes[temp[1]]
        nodes[nodes[temp[0]].left.no].parent = nodes[temp[0]]

    if temp[2] == -1:
        nodes[temp[0]].right = NULL
    else:
        nodes[temp[0]].right = nodes[temp[2]]
        nodes[nodes[temp[0]].right.no].parent = nodes[temp[0]]

    if temp[1] == -1 and temp[2] == -1:
        nodes[temp[0]].degree = 0
    elif temp[1] != -1 and temp[2] != -1:
        nodes[temp[0]].degree = 2
    else:
        nodes[temp[0]].degree = 1

for i in range(n):
    if nodes[i].parent is None:
        head = nodes[i]
        break

head.setsibdepth(nodes, 0)

for i in range(n):
    nodes[i].height = nodes[i].setheight(nodes, 0)

for i in range(n):
    if nodes[i].parent is None:
        print("node " + str(i) + ": parent = -1, sibling = "                              + str(nodes[i].sibling.no) + ", degree = " + str(nodes[i].degree) + ", depth = " + str(nodes[i].depth) + ", height = " + str(nodes[i].height) + ", root")
    elif nodes[i].left == NULL and nodes[i].right == NULL:
        print("node " + str(i) + ": parent = " + str(nodes[i].parent.no) + ", sibling = " + str(nodes[i].sibling.no) + ", degree = " + str(nodes[i].degree) + ", depth = " + str(nodes[i].depth) + ", height = " + str(nodes[i].height) + ", leaf")
    else:
        print("node " + str(i) + ": parent = " + str(nodes[i].parent.no) + ", sibling = " + str(nodes[i].sibling.no) + ", degree = " + str(nodes[i].degree) + ", depth = " + str(nodes[i].depth) + ", height = " + str(nodes[i].height) + ", internal node")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

def upd_dpth(node, depth):
    par, sib, deg, dep, hei, l, r = nodes[node]
    height = 0
    if l != -1:
        height = max(height, upd_dpth(l, depth+1))
    if r != -1:
        height = max(height, upd_dpth(r, depth+1))
    nodes[node][3] = depth
    nodes[node][4] = height
    return height+1

N = INT()

# node: [parent, sibing, degree, depth, height, l, r]
nodes = [[-1, -1, 0, 0, 0, -1, -1] for i in range(N)]

for i in range(N):
    node, l, r = MAP()
    if l != -1:
        # 次数の更新
        nodes[node][2] += 1
        # 親の更新
        nodes[l][0] = node
        # 兄弟の更新
        nodes[l][1] = r
        # 左の子の更新
        nodes[node][5] = l
    if r != -1:
        nodes[node][2] += 1
        nodes[r][0] = node
        nodes[r][1] = l
        nodes[node][6] = r


for i in range(N):
    # 深さと高さの更新
    if nodes[i][0] == -1:
        upd_dpth(i, 0)

for i in range(N):
    par, sib, deg, dep, hei, l, r = nodes[i]
    if par == -1:
        _type = 'root'
    elif deg == 0:
        _type = 'leaf'
    else:
        _type = 'internal node'
    print('node {node}: parent = {parent}, sibling = {sibling}, \
degree = {degree}, depth = {depth}, height = {height}, {type}'.format(
        node=i, parent=par, sibling=sib, degree=deg, depth=dep, height=hei, type=_type))

Submission status: Accepted

Solution code:
class Node():
    def __init__(self,node_id,left,right):
        self.node_id = node_id
        self.parent = -1
        self.left = left
        self.right = right
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = 'leaf'

    def set_attr(self,node_id,parent,sibling,depth):
        if node_id == -1:
            return -1
        self.parent = parent
        self.sibling = sibling
        self.depth = depth
        self.degree = (self.left != -1)+(self.right != -1)
        if self.degree:
            self.type = 'internal node'
        if self.parent == -1:
            self.type = 'root'
        self.height = max(
            tree[self.left].set_attr(
            self.left,
            self.node_id,
            self.right,
            self.depth+1
            ),
            tree[self.right].set_attr(
            self.right,
            self.node_id,
            self.left,
            self.depth+1
            )
        )+1
        return self.height

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

for _ in range(n):
    node_id,left,right = map(int,input().split())
    tree[node_id] = Node(node_id,left,right)
    root -= set([left,right])

root_id = root.pop()
tree[root_id].set_attr(root_id,-1,-1,0)
for node in tree:
    print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(node.node_id, node.parent, node.sibling, node.degree, node.depth, node.height, node.type))

Submission status: Accepted

Solution code:
from typing import List


class Node:
    parent = -1  # 親。親を持たない場合は-1
    sibling = -1  # 兄弟。兄弟を持たない場合は、-1
    degree = -99  # 子の数
    depth = -99  # 深さ
    height = -99  # 高さ
    node_type = 'Not set'  # 根(root)、内部節点(internal node)、葉(leaf)
    left = -99
    right = -99


num_of_node = int(input())
nodes = [Node() for i in range(num_of_node)]
for _i in range(num_of_node):
    node_id, left, right = map(int, input().split())
    # 子を持たない場合は、leftやrightは-1
    nodes[node_id].left = left
    nodes[node_id].right = right

    degree = 0
    if left != -1:
        degree += 1
    if right != -1:
        degree += 1
    nodes[node_id].degree = degree

# 親を設定
for i in range(num_of_node):
    if nodes[i].left != -1:
        nodes[nodes[i].left].parent = i
    if nodes[i].right != -1:
        nodes[nodes[i].right].parent = i

# 兄弟を設定
for i in range(num_of_node):
    if nodes[i].parent == -1:
        continue
    # 自分が左の場合
    if nodes[nodes[i].parent].left == i and nodes[nodes[i].parent].right != -1:
        nodes[i].sibling = nodes[nodes[i].parent].right
    # 自分が右の場合
    if nodes[nodes[i].parent].right == i and nodes[nodes[i].parent].left != -1:
        nodes[i].sibling = nodes[nodes[i].parent].left


def set_depth(node_id: int, depth: int):
    nodes[node_id].depth = depth
    if nodes[node_id].left != -1:
        set_depth(nodes[node_id].left, depth + 1)
    if nodes[node_id].right != -1:
        set_depth(nodes[node_id].right, depth + 1)


# 深さを設定
for i in range(num_of_node):
    if nodes[i].parent == -1:
        set_depth(i, 0)
        break


def set_height(node_id: int, height: int):
    if nodes[node_id].height < height:
        nodes[node_id].height = height
    if nodes[node_id].parent != -1:
        set_height(nodes[node_id].parent, height + 1)


# 高さを設定
for i in range(num_of_node):
    if nodes[i].degree == 0:
        set_height(i, 0)

# タイプを設定
for i in range(num_of_node):
    if nodes[i].parent == -1:
        nodes[i].node_type = 'root'
    elif nodes[i].degree != 0:
        nodes[i].node_type = 'internal node'
    else:
        nodes[i].node_type = 'leaf'


for i in range(num_of_node):
    out = f'node {i}: parent = {nodes[i].parent}, sibling = {nodes[i].sibling}'
    out += f', degree = {nodes[i].degree}, depth = {nodes[i].depth}'
    out += f', height = {nodes[i].height}, {nodes[i].node_type}'
    print(out)

Submission status: Accepted

Solution code:
def parent(s):
    sib[ch[s][0]] = ch[s][1]
    sib[ch[s][1]] = ch[s][0]
    if ch[s][0] != -1:
        par[ch[s][0]] = s
        dep[ch[s][0]] = dep[s]+1
        parent(ch[s][0])
    if ch[s][1] != -1:
        par[ch[s][1]] = s
        dep[ch[s][1]] = dep[s]+1
        parent(ch[s][1])


def setheight(t):
    h1 = h2 = 0
    if ch[t][0] != -1:
        h1 = setheight(ch[t][0]) + 1
    if ch[t][1] != -1:
        h2 = setheight(ch[t][1]) + 1
    high[t] = (h1 if h1 > h2 else h2)
    return high[t]
n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]

ch = {}
par = {}
sib = {}
dep = {}
deg = {}
high = {}
kara = []
for i in range(n):
    kara.append(i)

for i in data:
    tmp = 0
    if i[1] != -1:
        tmp += 1
    if i[2] != -1:
        tmp += 1
    deg[i[0]] = tmp
    ch[i[0]] = i[1:]
    try:
        kara.remove(i[1])
    except:
        pass
    try:
        kara.remove(i[2])
    except:
        pass
r = kara[0]
#print(r)
par[r] = -1
sib[r] = -1
dep[r] = 0
parent(r)
setheight(r)

for i in range(n):
    if par[i] == -1:
        tmp = 'root'
    elif ch[i][0] == -1 & ch[i][1] == -1:
        tmp = 'leaf'
    else:
        tmp = 'internal node'
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i, par[i], sib[i], deg[i], dep[i], high[i], tmp))

#print(ch)
#print(par)
#print(sib)
#print(deg)
#print(dep)
#print(high)