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.

Solution (Python):
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()

Solution (Python):

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)




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

Solution (Python):

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

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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("")

Solution (Python):
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()

Solution (Python):


import sys
sys.setrecursionlimit(2**20)  


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]


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)

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



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("")

Solution (Python):
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)))

Solution (Python):
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("")

Solution (Python):
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)))

Solution (Python):

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

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

nodes = []
for _ in range(n):
    x = list(map(int, input().split()))
    nodes.append(x)
    
class Tree:
    def __init__(self, n):
        
        
        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 = []
    
    childlen.append(t[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()

Solution (Python):
class Node:

    def __init__(self, _id):
        self.id = _id
        self.left = None
        self.right = None
        self.parent = None

    def add_left(self, node):
        node.parent = self
        self.left = node

    def add_right(self, node):
        node.parent = self
        self.right = node

    @property
    def parent_id(self):
        if self.parent is None:
            return -1
        else:
            return self.parent.id

    @property
    def deg(self):
        count = 0
        if self.right is not None:
            count += 1
        if self.left is not None:
            count += 1
        return count

    @property
    def sibling_id(self):
        if self.parent is None or self.parent.deg == 1:
            return -1
        else:
            if self.parent.left == self:
                return self.parent.right.id if self.parent.right is not None else -1
            else:
                return self.parent.left.id if self.parent.left is not None else -1

    @property
    def node_type(self):
        if self.parent is None:
            return 'root'
        if self.left is None and self.right is None:
            return 'leaf'
        return 'internal node'

    @property
    def height(self):
        if self.left is None:
            left = -1
        else:
            left = self.left.height
        if self.right is None:
            right = -1
        else:
            right = self.right.height
        return max(left, right) + 1

    @property
    def depth(self):
        if self.parent is None:
            return 0
        else:
            return self.parent.depth + 1

    def __eq__(self, other):
        return self.id == other.id

    def __repr__(self):
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
            self.id, self.parent_id, self.sibling_id, self.deg, self.depth, self.height, self.node_type)


def pre_parse(node, lst):
    if node is None:
        return
    lst.append(str(node.id))
    pre_parse(node.left, lst)
    pre_parse(node.right, lst)


def in_parse(node, lst):
    if node is None:
        return
    in_parse(node.left, lst)
    lst.append(str(node.id))
    in_parse(node.right, lst)


def post_parse(node, lst):
    if node is None:
        return
    post_parse(node.left, lst)
    post_parse(node.right, lst)
    lst.append(str(node.id))


def main():
    n = int(input())
    nodes = [Node(i) for i in range(n)]
    for _ in range(n):
        ID, left, right = map(int, input().split(' '))
        if left != -1:
            nodes[ID].add_left(nodes[left])
        if right != -1:
            nodes[ID].add_right(nodes[right])
    root = None
    for node in nodes:
        if node.depth == 0:
            root = node
    lst = []
    pre_parse(root, lst)
    print('Preorder')
    print(' ' + ' '.join(lst))
    lst = []
    in_parse(root, lst)
    print('Inorder')
    print(' ' + ' '.join(lst))
    lst = []
    post_parse(root, lst)
    print('Postorder')
    print(' ' + ' '.join(lst))


if __name__ == '__main__':
    main()