Problem:


Tree Walk

Binary trees are defined recursively. A binary tree T is a structure defined on a finite set of nodes that either

contains no nodes, or

is composed of three disjoint sets of nodes:

- a root node.

- a binary tree called its left subtree.

- a binary tree called its right subtree.

Your task is to write a program which perform tree walks (systematically traverse all nodes in a tree) based on the following algorithms:

Print the root, the left subtree and right subtree (preorder).

Print the left subtree, the root and right subtree (inorder).

Print the left subtree, right subtree and the root (postorder).

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 linen, 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

In the 1st line, print "Preorder", and in the 2nd line print a list of node IDs obtained by the preorder tree walk.

In the 3rd line, print "Inorder", and in the 4th line print a list of node IDs obtained by the inorder tree walk.

In the 5th line, print "Postorder", and in the 6th line print a list of node IDs obtained by the postorder tree walk.

Print a space character before each node ID.

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

Preorder
 0 1 2 3 4 5 6 7 8
Inorder
 2 1 3 0 6 5 7 4 8
Postorder
 2 3 1 6 7 5 8 4 0

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:
Preorder
 0 1 2 3 4 5 6 7 8
Inorder
 2 1 3 0 6 5 7 4 8
Postorder
 2 3 1 6 7 5 8 4 0

Submission status: Accepted

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

def preParse(node):
  if node == None:
    return
  print(" {}".format(node.id), end="")
  preParse(node.left)
  preParse(node.right)

def inParse(node):
  if node == None:
    return
  inParse(node.left)
  print(" {}".format(node.id), end="")
  inParse(node.right)

def postParse(node):
  if node == None:
    return
  postParse(node.left)
  postParse(node.right)
  print(" {}".format(node.id), end="")

num = int(input())
nodes = [None] * num
for i in range(num):
  id, left, right = map(int, input().split())
  node = nodes[id] if nodes[id] else Node(id)
  nodes[id] = node

  if left != -1:
    if nodes[left]:
      nodes[left].parent = node
      node.left = nodes[left]
    else:
      l = Node(left)
      l.parent = node
      node.left = l
      nodes[left] = l

  if right != -1:
    if nodes[right]:
      nodes[right].parent = node
      node.right = nodes[right]
    else:
      r = Node(right)
      r.parent = node
      node.right = r
      nodes[right] = r

def getParent(node):
  if node.parent == None:
    return node
  return getParent(node.parent)

print("Preorder")
preParse(getParent(nodes[0]))
print()
print("Inorder")
inParse(getParent(nodes[0]))
print()
print("Postorder")
postParse(getParent(nodes[0]))
print()

Submission status: Accepted

Solution code:

class Node:
    id = None
    parent = None
    left = None
    right = None
    sibling = -1
    depth = None
    height = None

    def __str__(self):
        degree = None
        _type = None

        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(self.id, self.parent, self.sibling, self.get_degree(), self.depth, self.height, self.get_type())

    def get_degree(self):
        degree = 0
        if self.left is not None:
            degree += 1
        if self.right is not None:
            degree += 1
        return degree

    def get_type(self):
        if self.parent == -1:
            return 'root'
        if self.get_degree() == 0:
            return 'leaf'
        else:
            return 'internal node'


def set_depth(node_id, depth):
    if node_id is None:
        return

    global T
    T[node_id].depth = depth
    set_depth(T[node_id].left, depth + 1)
    set_depth(T[node_id].right, depth + 1)


def set_height(node_id):
    global T

    h1, h2 = 0, 0
    if T[node_id].left is not None:
        h1 = set_height(T[node_id].left) + 1
    if T[node_id].right is not None:
        h2 = set_height(T[node_id].right) + 1

    T[node_id].height = max(h1, h2)

    return max(h1, h2)


def pre_order(node_id, _order):
    if node_id is None:
        return

    global T
    _order.append(node_id)
    pre_order(T[node_id].left, _order)
    pre_order(T[node_id].right, _order)


def in_order(node_id, _order):
    if node_id is None:
        return

    global T
    in_order(T[node_id].left, _order)
    _order.append(node_id)
    in_order(T[node_id].right, _order)


def post_order(node_id, _order):
    if node_id is None:
        return

    global T
    post_order(T[node_id].left, _order)
    post_order(T[node_id].right, _order)
    _order.append(node_id)


n = int(input())
T = []
root = 0

for i in range(n):
    T.append(Node())

for i in range(n):
    _ = list(map(int, input().split()))
    _id = _[0]
    left = _[1]
    right = _[2]
    if left == -1:
        left = None
    if right == -1:
        right = None

    T[_id].id = _id
    T[_id].left = left
    T[_id].right = right

    if left is not None:
        T[left].parent = _id
    if right is not None:
        T[right].parent = _id

    if left is not None and right is not None:
        T[left].sibling = right
        T[right].sibling = left

for i in range(n):
    if T[i].parent is None:
        T[i].parent = -1
        root = i
        break

set_depth(root, 0)
set_height(root)

# for i in range(n):
#     print(T[i])

order = []
print('Preorder')
pre_order(root, order)
print(' ' + ' '.join(map(str, order)))

order = []
print('Inorder')
in_order(root, order)
print(' ' + ' '.join(map(str, order)))

order = []
print('Postorder')
post_order(root, order)
print(' ' + ' '.join(map(str, order)))

Submission status: Accepted

Solution code:
#7-C tree walk
class node():
    def __init__(self):
        self.left=-1
        self.right=-1
        self.parent=-1

def preorder(i):
    print(' '+str(i),end='')
    if nodes[i].left!=-1:
        preorder(nodes[i].left)
    if nodes[i].right!=-1:
        preorder(nodes[i].right)
    
def inorder(i):
    if nodes[i].left!=-1:
        inorder(nodes[i].left)
    print(' '+str(i),end='')
    if nodes[i].right!=-1:
        inorder(nodes[i].right)
        
def postorder(i):
    if nodes[i].left!=-1:
        postorder(nodes[i].left)
    if nodes[i].right!=-1:
        postorder(nodes[i].right)
    print(' '+str(i),end='')
  

n=int(input())
nodes=[node() for i in range(n)]
for i in range(n):
    p,l,r=[int(i) for i in input().split()]
    nodes[p].left=l
    nodes[p].right=r
    if l!=-1:nodes[l].parent=p
    if r!=-1:nodes[r].parent=p

root=-1
for i in range(n):
    if nodes[i].parent==-1:
        root=i
        break

print('Preorder')
preorder(root)
print()

print('Inorder')
inorder(root)
print()

print('Postorder')
postorder(root)
print()

Submission status: Accepted

Solution code:
n=int(input())
p_list=[-1]*n
s_list=[-1]*n
c_list=[0]*n
degree=[0]*n
depth=[0]*n
height=[0]*n
type=[0]*n
for _ in range(n):
    id,l,r=map(int,input().split())
    c_list[id]=[l,r]
    if l!=-1 and r!=-1:
        degree[id]=2
        type[id]="internal node"
        p_list[l]=id
        p_list[r]=id
        s_list[l]=r
        s_list[r]=l
    elif r!=-1:
        degree[id]=1
        type[id]="internal node"
        p_list[r]=id
        s_list[r]=l
    elif l!=-1:
        degree[id]=1
        type[id]="internal node"
        p_list[l]=id
        s_list[l]=r
    else:
        degree[id]=0
        type[id]="leaf"
root=p_list.index(-1)
type[root]="root"

pre=[]
def dsf1(v):
    pre.append(v)
    if c_list[v]!=[-1,-1]:
        if c_list[v][0]==-1:
            dsf1(c_list[v][1])
        elif c_list[v][1]==-1:
            dsf1(c_list[v][0])
        else:
            dsf1(c_list[v][0])
            dsf1(c_list[v][1])
dsf1(root)

inn=[]
def dsf2(v):
    if c_list[v][0]!=-1:
        dsf2(c_list[v][0])
    inn.append(v)
    if c_list[v][1]!=-1:
        dsf2(c_list[v][1])    
dsf2(root)

post=[]
def dsf3(v):
    if c_list[v]!=[-1,-1]:
        if c_list[v][0]==-1:
            dsf3(c_list[v][1])
        elif c_list[v][1]==-1:
            dsf3(c_list[v][0])
        else:
            dsf3(c_list[v][0])
            dsf3(c_list[v][1])
    post.append(v)
dsf3(root)
print("Preorder")
print("",*pre)
print("Inorder")
print("",*inn)
print("Postorder")
print("",*post)

Submission status: Accepted

Solution code:
n = int(input())
lst = [list(map(int,input().split())) for i in range(n)]
lst_num = [lst[i][0] for i in range(n)]
A = []
B = []
C = []

def Insertion_Sort(arg_lst, arg_lst_num, arg_n):
    for i in range(1,arg_n):
        v = arg_lst_num[i]
        w = arg_lst[i]
        j = i-1
        while j>=0 and arg_lst_num[j]>v:
            arg_lst_num[j+1]=arg_lst_num[j]
            arg_lst[j+1]=arg_lst[j]
            j-=1
        arg_lst_num[j+1]=v
        arg_lst[j+1]=w

def find_root(arg_lst):
    TMP = []
    for i in range(n):
        TMP.extend(arg_lst[i][1:])
    for i in range(n):
        if not i in TMP:
            return i

def Preorder(arg_Q, arg_lst, arg_num):
    arg_Q.append(arg_num)
    if lst[arg_num][1] != -1:
        Preorder(arg_Q, arg_lst, lst[arg_num][1])
    if lst[arg_num][2] != -1:
        Preorder(arg_Q, arg_lst, lst[arg_num][2])

def Inorder(arg_Q, arg_lst, arg_num):
    if lst[arg_num][1] != -1:
        Inorder(arg_Q, arg_lst, lst[arg_num][1])
    arg_Q.append(arg_num)
    if lst[arg_num][2] != -1:
        Inorder(arg_Q, arg_lst, lst[arg_num][2])

def Postorder(arg_Q, arg_lst, arg_num):
    if lst[arg_num][1] != -1:
        Postorder(arg_Q, arg_lst, lst[arg_num][1])
    if lst[arg_num][2] != -1:
        Postorder(arg_Q, arg_lst, lst[arg_num][2])
    arg_Q.append(arg_num)

Insertion_Sort(lst, lst_num, n)
root = find_root(lst)
Preorder(A, lst, root)
print("Preorder")
for i in A:
    print(f" {i}",end="")
print()
Inorder(B, lst, root)
print("Inorder")
for i in B:
    print(f" {i}",end="")
print()
Postorder(C, lst, root)
print("Postorder")
for i in C:
    print(f" {i}",end="")
print()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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


N = int(input())
btree = [Node(-1, -1, -1) for i in range(N)]
root_cand_list = [i for i in range(N)]


def main():
    for i in range(N):
        num, left, right = map(int, input().split())

        if left != -1:
            btree[num].left = left
            btree[left].parent = num
            root_cand_list.remove(left)
        if right != -1:
            btree[num].right = right
            btree[right].parent = num
            root_cand_list.remove(right)

    print("Preorder")
    showPreorder(root_cand_list[0])
    print()
    print("Inorder")
    showInorder(root_cand_list[0])
    print()
    print("Postorder")
    showPostorder(root_cand_list[0])
    print()


def showPreorder(num):
    print(" ", end="")
    print(num, end="")
    if btree[num].left != -1:
        showPreorder(btree[num].left)
    if btree[num].right != -1:
        showPreorder(btree[num].right)


def showInorder(num):
    if btree[num].left != -1:
        showInorder(btree[num].left)
    print(" ", end="")
    print(num, end="")
    if btree[num].right != -1:
        showInorder(btree[num].right)


def showPostorder(num):
    if btree[num].left != -1:
        showPostorder(btree[num].left)
    if btree[num].right != -1:
        showPostorder(btree[num].right)
    print(" ", end="")
    print(num, end="")



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class node:
    def __init__(self, parent, left, right):
        self.p = parent
        self.l = left
        self.r = right

def preParse(u):
    if u == -1:
        return
    print(" " + str(u), end = '')
    preParse(T[u].l)
    preParse(T[u].r)

def inParse(u):
    if u == -1:
        return
    inParse(T[u].l)
    print(" " + str(u), end = '')
    inParse(T[u].r)

def postParse(u):
    if u == -1:
        return
    postParse(T[u].l)
    postParse(T[u].r)
    print(" " + str(u), end = '')

n = int(input())
T = [node(-1, -1, -1) for _ in range(n)]
for _ in range(n):
    info = list(map(int, input().split(" ")))
    T[info[0]].l = info[1]
    T[info[0]].r = info[2]
    if info[1] != -1:
        T[info[1]].p = info[0]
    if info[2] != -1:
        T[info[2]].p = info[0]

print("Preorder")
for i in range(n):
    if T[i].p == -1:
        preParse(i)

print("\n" + "Inorder")
for i in range(n):
    if T[i].p == -1:
        inParse(i)

print("\n" + "Postorder")
for i in range(n):
    if T[i].p == -1:
        postParse(i)

print("")

Submission status: Accepted

Solution code:
n = int(input())
NIL = -1
MAX = 10000

class Node():
    def __init__(self):
        self.parent = [0] * MAX
        self.left = [0] * MAX
        self.right = [0] * MAX
        self.Pr = []
        self.I = []
        self.Po = []
        
    def preparse(self, u):
        if u == NIL:
            return
        self.Pr.append(u)
        self.preparse(self.left[u])
        self.preparse(self.right[u])
        return self
    
    def inoparse(self, u):
        if u == NIL:
            return
        self.inoparse(self.left[u])
        self.I.append(u)
        self.inoparse(self.right[u])
        return self
    
    def postparse(self, u):
        if u == NIL:
            return
        self.postparse(self.left[u])
        self.postparse(self.right[u])
        self.Po.append(u)
        return self
        
def main():
    T = Node()
    for i in range(n):
        T.parent[i] = NIL
    
    for i in range(n):
        v, l, r = (int(x) for x in input().split())
        T.left[v] = l
        T.right[v] = r
        if l != NIL:
            T.parent[l] = v
        if r != NIL:
            T.parent[r] = v
    
    for i in range(n):
        if T.parent[i] == NIL:
            root = i
    
    T.preparse(root)
    T.inoparse(root)
    T.postparse(root)
    pr = [str(i) for i in T.Pr]
    ino = [str(i) for i in T.I]
    po = [str(i) for i in T.Po]
    
    print('Preorder')
    print(' ' + ' '.join(pr))
    print('Inorder')
    print(' ' + ' '.join(ino))
    print('Postorder')
    print(' ' + ' '.join(po))

main()

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7/ALDS1_7_C

import sys
sys.setrecursionlimit(2**20)  # 再帰回数上限の向上 かなり多くしないとREになる


class Node:
    def __init__(self,
                 parent,
                 left,
                 right):
        self.parent = parent
        self.left = left  # 左の子ノード
        self.right = right  # 右の**子**


def pre_parse(T: dict, u: int, pre_ls: list):
    # 深さ優先探索特有の即時終了条件
    if u == None:
        return
    pre_ls.append(u)
    pre_parse(T, T[u].left, pre_ls)  # より左の方から深さ優先探索
    pre_parse(T, T[u].right, pre_ls)


def in_parse(T, u, in_ls):
    if u == None:
        return
    # 左→中→右っていうちょっと気持ち悪い順番
    in_parse(T, T[u].left, in_ls)
    in_ls.append(u)
    in_parse(T, T[u].right, in_ls)


def post_parse(T, u, post_ls):
    if u == None:
        return
    post_parse(T, T[u].left, post_ls)
    post_parse(T, T[u].right, post_ls)
    post_ls.append(u)


# データの読み込み
n = int(input())
T = {key: Node(None, None, None) for key in range(n)}
for _ in range(n):
    tmp = [x if x != -1 else None for x in map(int, input().split())]
    T[tmp[0]].left = tmp[1]
    T[tmp[0]].right = tmp[2]
    if tmp[1] is not None:
        T[tmp[1]].parent = tmp[0]
    if tmp[2] is not None:
        T[tmp[2]].parent = tmp[0]

# parentがないのが特徴のROOTを探す
for id, node in T.items():
    if node.parent is None:
        ROOT = id

# リストに答えを格納していく
pre_ls, in_ls, post_ls = [], [], []
pre_parse(T, ROOT, pre_ls)
in_parse(T, ROOT, in_ls)
post_parse(T, ROOT, post_ls)

print('Preorder')
print('', *pre_ls)
print('Inorder')
print('', *in_ls)
print('Postorder')
print('', *post_ls)

Submission status: Accepted

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

# T : List[Node]

def preOrder(id: int):
	left_id = T[id].left
	right_id = T[id].right
	print(" " + str(id), end="")
	if left_id != -1:
		preOrder(left_id)
	if right_id != -1:
		preOrder(right_id)

def inOrder(id: int):
	left_id = T[id].left
	right_id = T[id].right
	if left_id != -1:
		inOrder(left_id)
	print(" " + str(id), end="")
	if right_id != -1:
		inOrder(right_id)

def postOrder(id: int):
	left_id = T[id].left
	right_id = T[id].right
	if left_id != -1:
		postOrder(left_id)
	if right_id != -1:
		postOrder(right_id)
	print(" " + str(id), end="")


if __name__ == "__main__":
	n = int(input())
	T = []
	for i in range(n):
		T.append(Node())
	for i in range(n):
		id, left, right = map(int, input().split())
		T[id].left = left
		T[id].right = right
		if left != -1:
			T[left].parent = id
		if right != -1:
			T[right].parent = id

	for i in range(n):
		if T[i].parent == -1:
			root_id = i
	print("Preorder")
	preOrder(root_id)
	print("")
	print("Inorder")
	inOrder(root_id)
	print("")
	print("Postorder")
	postOrder(root_id)
	print("")

Submission status: Accepted

Solution code:
class node():
    def __init__(self, id, parent, child, depth, type_t, sibling, height=0):
        self.id = id
        self.parent = parent
        self.child = child
        self.depth = depth
        self.type_t = type_t
        self.sibling = sibling
        self.height = height


def add(t, d, i, parent, depth, sibling):
    type_t = 'internal node'
    if d[i][1] == -1 and d[i][2] == -1:
        type_t = 'leaf'
    if depth == 0:
        type_t = 'root'
    child = d[i][1:]
    new_node = node(i, parent, child, depth, type_t, sibling)
    t.append(new_node)
    if child[0] >= 0:
        sib = child[1] if child[1] >= 0 else -1
        add(t, d, child[0], i, depth + 1, sib)
    if child[1] >= 0:
        sib = child[0] if child[0] >= 0 else -1
        add(t, d, child[1], i, depth + 1, sib)


def calc_height(t, i):
    if t[i].child[0] == -1 and t[i].child[1] == -1:
        return 0
    max_h = -1
    if t[i].child[0] >= 0:
        max_h = max(max_h, calc_height(t, t[i].child[0]))
    if t[i].child[1] >= 0:
        max_h = max(max_h, calc_height(t, t[i].child[1]))
    return max_h + 1

def preorder(t, a, i):
    l, r = -1, -1
    l = t[i].child[0]
    r = t[i].child[1]
    a.append(i)
    if not l == -1:
        preorder(t, a, l)
    if not r == -1:
        preorder(t, a, r)


def inorder(t, a, i):
    l, r = -1, -1
    l = t[i].child[0]
    r = t[i].child[1]
    if not l == -1:
        inorder(t, a, l)
    a.append(i)
    if not r == -1:
        inorder(t, a, r)


def postorder(t, a, i):
    l, r = -1, -1
    l = t[i].child[0]
    r = t[i].child[1]
    if not l == -1:
        postorder(t, a, l)
    if not r == -1:
        postorder(t, a, r)
    a.append(i)

N = int(input())
tree = []
data = [[] for i in range(N)]
for i in range(N):
    data[i] = [int(i) for i in input().split()]

data.sort(key=lambda x: x[0])
root = [True for i in range(N)]
for d in data:
    for c in d[1:]:
        if c == -1:
            continue
        root[c] = False

root_index = root.index(True)
add(tree, data, root_index, -1, 0, -1)

tree.sort(key=lambda x: x.id)

for i in range(N):
    h = calc_height(tree, i)
    tree[i].height = h

a = []
preorder(tree, a, root_index)
print('Preorder')
print('', ' '.join(map(str, a)))
a = []
inorder(tree, a, root_index)
print('Inorder')
print('', ' '.join(map(str, a)))
a = []
postorder(tree, a, root_index)
print('Postorder')
print('', ' '.join(map(str, a)))

Submission status: Accepted

Solution code:
def preorder(tree, index):
    print(" " + str(index), end="")
    if tree[index][1] != -1:
        preorder(tree, tree[index][1])
    if tree[index][2] != -1:
        preorder(tree, tree[index][2])


def inorder(tree, index):
    if tree[index][1] != -1:
        inorder(tree, tree[index][1])
    print(" " + str(index), end="")
    if tree[index][2] != -1:
        inorder(tree, tree[index][2])


def postorder(tree, index):
    if tree[index][1] != -1:
        postorder(tree, tree[index][1])
    if tree[index][2] != -1:
        postorder(tree, tree[index][2])
    print(" " + str(index), end="")



n = int(input())
a = [[-1 for i in range(3)] for j in range(n)]
for _ in range(n):
    i, l, r = [int(x) for x in input().split()]
    a[i][1] = l
    a[i][2] = r
    a[l][0] = i
    a[r][0] = i

root = 0
for i, v in enumerate(a):
    if v[0] == -1:
        root = i
        break

print("Preorder")
preorder(a, root)
print("")
print("Inorder")
inorder(a, root)
print("")
print("Postorder")
postorder(a, root)
print("")

Submission status: Accepted

Solution code:
class Tree:
    def __init__(self, node, children):
        self.node = node
       
        if children[0] == -1 and children[1] == -1:
            self.left = None
            self.right = None
            self.children = []
        elif children[0] != -1 and children[1] == -1:
            self.left = children[0]
            self.right = None
            self.children = [self.left, None]
        elif children[0] == -1 and children[1] != -1:
            self.left = None
            self.right = children[1]
            self.children =[None, children[1]]
        else:
            self.left = children[0]
            self.right = children[1]
            self.children = [self.left, self.right]

n = int(input())
NODES = {}
ROOT_SEARCH = [True]*n

for _ in range(n):
    datum = list(map(int, input().split()))
    tmp = Tree(datum[0], datum[1:])
    NODES[datum[0]] = tmp
    for element in tmp.children:
        try:
            ROOT_SEARCH[element] = False
        except:
            pass
        
for node in range(len(ROOT_SEARCH)):
    if ROOT_SEARCH[node]:
        root = node

        
In_result = []
def Inorder(NODES, root):
    global In_result
    
    if NODES[root].left != None and NODES[root].right != None:
        Inorder(NODES, NODES[root].left)
        In_result.append(root)
        Inorder(NODES, NODES[root].right)
    
    elif NODES[root].left !=None and NODES[root].right == None:
        Inorder(NODES, NODES[root].left)
        In_result.append(root)
    
    elif NODES[root].left == None and NODES[root].right != None:
        In_result.append(root)
        Inorder(NODES, NODES[root].right)
    
    else:
        In_result.append(root)

Post_result = []
def Postorder(NODES, root):
    global Post_result
    
    if NODES[root].left != None and NODES[root].right != None:
        Postorder(NODES, NODES[root].left)
        Postorder(NODES, NODES[root].right)
        Post_result.append(root)
    
    elif NODES[root].left !=None and NODES[root].right == None:
        Postorder(NODES, NODES[root].left)
        Post_result.append(root)
    
    elif NODES[root].left == None and NODES[root].right != None:
        Postorder(NODES, NODES[root].right)
        Post_result.append(root)
    
    else:
        Post_result.append(root)

Pre_result=[]
def Preorder(NODES, root):
    global Pre_result
    
    if NODES[root].left != None and NODES[root].right != None:
        Pre_result.append(root)
        Preorder(NODES, NODES[root].left)
        Preorder(NODES, NODES[root].right)
    
    elif NODES[root].left !=None and NODES[root].right == None:
        Pre_result.append(root)
        Preorder(NODES, NODES[root].left)
    
    elif NODES[root].left == None and NODES[root].right != None:
        Pre_result.append(root)
        Preorder(NODES, NODES[root].right)
    
    else:
        Pre_result.append(root)

Pre_result_str  = list(map(str, Pre_result))
Post_result_str = list(map(str, Post_result))
In_result_str   = list(map(str, In_result))

print("Preorder")
Preorder(NODES, root)
print(" "+" ".join(map(str, Pre_result)))

print("Inorder")
Inorder(NODES, root)
print(" "+" ".join(map(str, In_result)))

print("Postorder")
Postorder(NODES, root)
print(" "+" ".join(map(str, Post_result)))

Submission status: Accepted

Solution code:
# ALDS1_7_C Tree Walk
import sys


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


def preorder(A, i, B):
    B.append(i)
    if A[i].left != -1:
        preorder(A, A[i].left, B)
    if A[i].right != -1:
        preorder(A, A[i].right, B)
    return


def inorder(A, i, B):
    if A[i].left != -1:
        inorder(A, A[i].left, B)
    B.append(i)
    if A[i].right != -1:
        inorder(A, A[i].right, B)
    return


def postorder(A, i, B):
    if A[i].left != -1:
        postorder(A, A[i].left, B)
    if A[i].right != -1:
        postorder(A, A[i].right, B)
    B.append(i)
    return


n = int(input())

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

root = [i for i in range(n)]
for i in range(n):
    A = list(map(int, sys.stdin.readline().strip().split()))
    tree[A[0]].left = A[1]
    tree[A[0]].right = A[2]

    if A[1] != -1:
        tree[A[1]].parent = A[0]
        root.remove(A[1])
    if A[2] != -1:
        tree[A[2]].parent = A[0]
        root.remove(A[2])

print('Preorder')
ans = []
preorder(tree, root[0], ans)
print('', ' '.join(map(str, ans)))

print('Inorder')
ans = []
inorder(tree, root[0], ans)
print('', ' '.join(map(str, ans)))

print('Postorder')
ans = []
postorder(tree, root[0], ans)
print('', ' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
n = int(input())

nodes = []
for _ in range(n):
    x = list(map(int, input().split()))
    nodes.append(x)
    
class Tree:
    def __init__(self, n):
        # n : ノード数
        # sibling : 兄弟
        self.nodes = {node: {'parent': None, 'children': [], 'depth': None, 'height': None, 'sibling': None} for node in range(n)}
        self.root = None
        
    def get_root(self):
        if self.root != None:
            return self.root
        else:
            for k, v in self.nodes.items():
                if v['parent'] == None:
                    self.root = k
                    return self.root
        
    def add_node_with_child(self, node, childlen):
        for c in childlen:
            self.nodes[node]['children'].append(c)
            if c == -1:
                continue
            self.nodes[c]['parent'] = node
    
    def get_parent(self, node):
        return self.nodes[node]['parent']
    
    def get_children(self, node):
        return self.nodes[node]['children']
        
    def get_depth(self, node):
        if self.nodes[node]['depth'] != None:
            return self.nodes[node]['depth']
        elif self.nodes[node]['parent'] == None:
            self.nodes[node]['depth'] = 0
            return 0
        else:
            depth = self.get_depth(self.nodes[node]['parent']) + 1
            self.nodes[node]['depth'] = depth
            return depth
        
    def get_height(self, node):
        if self.nodes[node]['height'] != None:
            return self.nodes[node]['height']
        elif len(self.nodes[node]['children']) == 0:
            self.nodes[node]['height'] = 0
            return 0
        elif self.nodes[node]['height'] == None:
            children = self.nodes[node]['children']
            children_h = [self.get_height(c)+1 for c in children]
            self.nodes[node]['height'] = max(children_h)
            return self.nodes[node]['height']
        
    def get_sibling(self, node):
        if self.nodes[node]['sibling'] != None:
            return self.nodes[node]['sibling']
        elif self.nodes[node]['parent'] == None:
            self.nodes[node]['sibling'] = []
            return self.nodes[node]['sibling']
        else:
            p = self.nodes[node]['parent']
            sibling = set(self.get_children(p))
            sibling.remove(node)
            self.nodes[node]['sibling'] = list(sibling)
            return self.nodes[node]['sibling']
        
RootedTree = Tree(n)
for t in nodes:
    node = t[0]
    childlen = []
    #if t[1] != -1:
    childlen.append(t[1])
    #if t[2] != -1:
    childlen.append(t[2])
    RootedTree.add_node_with_child(node, childlen)
    
root = RootedTree.get_root()

def Preorder(node):
    print('', node, end="")
    for c in RootedTree.get_children(node):
        if c == -1:
            continue
        Preorder(c)

print('Preorder')
Preorder(root)


def Inorder(node):
    c = RootedTree.get_children(node)
    if c[0] != -1:
        Inorder(c[0])
    print('', node, end="")
    
    if c[1] != -1:
        Inorder(c[1])
    
print()    
print('Inorder')
Inorder(root)


def Postorder(node):
    for c in RootedTree.get_children(node):
        if c == -1:
            continue
        Postorder(c)
    print('', node, end="")
print()    
print('Postorder')
Postorder(root)
print()