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):
import sys
sys.setrecursionlimit(2**20)
n = int(input())
NIL = -1
class node:
    def __init__(self,parent,left,right):
        self.parent = parent
        self.left = left
        self.right = right
T = [node(NIL,NIL,NIL) for _ in range(n)]
D = [0]*n
def setDepth(u,p):
    if u == NIL:
        return
    D[u] = p      
    if T[u].left != NIL:
        setDepth(T[u].left,p+1)
    if T[u].right != NIL:
        setDepth(T[u].right,p+1)
    return D
H = [0]*n
def setHeight(u,H):
    hl = 0
    hr = 0
    if T[u].left != NIL:
        hl = 1 + setHeight(T[u].left,H)
    if T[u].right != NIL:
        hr = 1 + setHeight(T[u].right,H)
    ret = max(hl,hr)
    H[u] = ret
    return ret
def getDegree(u):
    cc = 0
    if T[i].left != NIL:
        cc += 1
    if T[i].right != NIL:
        cc += 1
    return cc
def getDepth(u):
    d = 0
    while T[u].parent != NIL:
        u = T[u].parent
        d += 1
    return d
def getBrother(u):
    if T[u].parent == NIL:
        return NIL
    elif T[T[u].parent].left == u:
        return T[T[u].parent].right
    elif T[T[u].parent].right == u:
        return T[T[u].parent].left
def printChildren(u):
    child = []
    if T[u].left != NIL:
        child.append(T[u].left)
    if T[u].right != NIL:
        child.append(T[u].right)
    return child
def ppp():
	for i in range(n):
  		ccc = T[i]
  		print(i,ccc.parent,ccc.left,ccc.right)
def findroot(u): 
    while T[u].parent != NIL:
        u = T[u].parent
    return u

rl = []
def rootleft(u,rl): 
    if u == NIL:
        return
    rl.append(u)
    rootleft(T[u].left,rl)
    rootleft(T[u].right,rl)
lro = []
def leftroot(u,lro):
    if u == NIL:
        return
    leftroot(T[u].left,lro)
    lro.append(u)
    leftroot(T[u].right,lro)
lri = []
def leftright(u,lri):
    if u == NIL:
        return
    leftright(T[u].left,lri)
    leftright(T[u].right,lri)
    lri.append(u)

firstid = 0
for i in range(n):
    id,left,right = map(int,input().split())
    if n == 0:
        firstid = id
    if left != NIL:
        T[id].left = left
        T[left].parent = id
    if right != NIL:
        T[id].right = right
        T[right].parent = id
r = findroot(firstid)
D = setDepth(r,0)
setHeight(r,H)
leftright(r,lri)
leftroot(r,lro)
rootleft(r,rl)
s0 = " ".join(map(str,rl))
s1 = " ".join(map(str,lro))
s2 = " ".join(map(str,lri))
print("Preorder")
print(" "+s0)
print("Inorder")
print(" "+s1)
print("Postorder")
print(" "+s2)

Solution (Python):
class Node:
    def __init__(self):
        self.p = -1
        self.l = -1
        self.r = -1

n = int(input())
T = [Node() for _ in range(n)]
for _ in range(n):
    i,l,r = map(int,input().split())
    T[i].l = l
    T[i].r = r
    if l != -1: T[l].p = i
    if r != -1: T[r].p = i

preorder = []
inorder = []
postorder = []

def preParse(u):
    if u == -1: return
    preorder.append(u)
    preParse(T[u].l)
    preParse(T[u].r)

def inParse(u):
    if u == -1: return
    inParse(T[u].l)
    inorder.append(u)
    inParse(T[u].r)

def postParse(u):
    if u == -1: return
    postParse(T[u].l)
    postParse(T[u].r)
    postorder.append(u)

r = 0
while T[r].p != -1: r += 1
preParse(r)
inParse(r)
postParse(r)

print("Preorder",end="\n ")
print(*preorder)
print("Inorder",end="\n ")
print(*inorder)
print("Postorder",end="\n ")
print(*postorder)

Solution (Python):



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


def preordertreewalk(u):
    print(" ", u, end="", sep="")
    if T[u].left != -1:
        preordertreewalk(T[u].left)
    if T[u].right != -1:
        preordertreewalk(T[u].right)


def inordertreewalk(u):
    if T[u].left != -1:
        inordertreewalk(T[u].left)
    print(" ", u, end="", sep="")
    if T[u].right != -1:
        inordertreewalk(T[u].right)


def postordertreewalk(u):
    if T[u].left != -1:
        postordertreewalk(T[u].left)
    if T[u].right != -1:
        postordertreewalk(T[u].right)
    print(" ", u, end="", sep="")


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

rootid = -1
for id in range(n):
    if T[id].parent == -1:
        rootid = id

print("Preorder")
preordertreewalk(rootid)

print("\nInorder")
inordertreewalk(rootid)

print("\nPostorder")
postordertreewalk(rootid)
print()

Solution (Python):
global nodes

class Node:
    def _init__(self):
        self.left = -1
        self.right = -1
    def set(self,arg_node_left,arg_node_right):
        self.left =arg_node_left
        self.right =arg_node_right
    
def Preorder(node_id):
    print(" %d"%(node_id),end="")
    if nodes[node_id].left != -1:
        Preorder(nodes[node_id].left)
    if nodes[node_id].right != -1:
        Preorder(nodes[node_id].right)

def Inorder(node_id):
    if nodes[node_id].left != -1:
        Inorder(nodes[node_id].left)
    print(" %d"%(node_id),end="")
    if nodes[node_id].right != -1:
        Inorder(nodes[node_id].right)

def Postorder(node_id):
    if nodes[node_id].left != -1:
        Postorder(nodes[node_id].left)
    if nodes[node_id].right != -1:
        Postorder(nodes[node_id].right)
    print(" %d"%(node_id),end="")

V = int(input())
nodes = [Node() for _ in range(V)]
in_num = [0]*V
for loop in range(V):
    node_id,left,right = map(int,input().split())
    nodes[node_id].set(left,right)
    if left != -1:
        in_num[left] += 1
    if right != -1:
        in_num[right] += 1

root = -1 
for i in range(V): 
    if in_num[i] == 0:
        root = i
        break

print("Preorder")
Preorder(root)
print()

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

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

Solution (Python):
def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    A_list = [[int(item) for item in input().split()] for _ in range(N)]
    A_list.sort(key=lambda x:x[0])

    def is_root(node):
        root_check_que = collections.deque([node])
        foot_print = [False for _ in range(N)]

        while root_check_que:
            temp_node = root_check_que.popleft()
            foot_print[temp_node] = True
            children = A_list[temp_node][1:3]

            for child in children:
                if child >= 0 and foot_print[child] == False:
                    root_check_que.append(child)

        return all(foot_print)


    def preorder(node):
        if node == -1:
            return

        print('',node, end='')
        left = A_list[node][1]
        right = A_list[node][2]
        preorder(left)
        preorder(right)

    for i in range(N):
        if is_root(i):
            root = i
            break

    def inorder(node):
        if node == -1:
            return

        left = A_list[node][1]
        right = A_list[node][2]
        inorder(left)
        print('',node, end='')
        inorder(right)
    
    def postorder(node):
        if node == -1:
            return

        left = A_list[node][1]
        right = A_list[node][2]
        postorder(left)
        postorder(right)
        print('',node, end='')

    for i in range(N):
        if is_root(i):
            root = i
            break
    
    print('Preorder')
    preorder(root)
    print('')


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

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


if __name__ == "__main__":
    resolve()

Solution (Python):



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


class BinaryTree():
    def __init__(self, n):
        self.T = [Node(i) for i in range(n)]
        self.preorder_idx = []
        self.inorder_idx = []
        self.postorder_idx = []

    def set_children(self, idx, l, r):
        node = self.T[idx]
        node.left = l
        node.right = r
        if l != -1:
            self.T[l].parent = idx
        if r != -1:
            self.T[r].parent = idx

    def get_root(self):
        for idx, node in enumerate(self.T):
            if node.parent == -1:
                return idx

    def preorder(self, idx):
        if idx == -1:
            return
        node = self.T[idx]
        self.preorder_idx.append(idx)
        self.preorder(node.left)
        self.preorder(node.right)

    def inorder(self, idx):
        if idx == -1:
            return
        node = self.T[idx]
        self.inorder(node.left)
        self.inorder_idx.append(idx)
        self.inorder(node.right)

    def postorder(self, idx):
        if idx == -1:
            return
        node = self.T[idx]
        self.postorder(node.left)
        self.postorder(node.right)
        self.postorder_idx.append(idx)


N = int(input())
tree = BinaryTree(N)

for _ in range(N):
    idx, l, r = map(int, input().split())
    tree.set_children(idx, l, r)

root = tree.get_root()
tree.preorder(root)
tree.inorder(root)
tree.postorder(root)

print('Preorder')
print('', *(tree.preorder_idx))
print('Inorder')
print('', *(tree.inorder_idx))
print('Postorder')
print('', *(tree.postorder_idx))

Solution (Python):
class node(object):
    def __init__(self):
        self.value = None
        self.left = None
        self.right = None
        self.parent = None

def preorder(nodes,root):
    stacked = [nodes[root]]
    visited = []
    while(len(stacked)>0):
        node = stacked.pop()
        value = node.value
        left = node.left
        right = node.right
        visited.append(value)
        
        if (right not in visited) and (right != None):
            stacked.append(nodes[right])
        if (left not in visited) and (left != None):
            stacked.append(nodes[left])
    out = ""
    for i in visited:
        out += " "+str(i)
    return out

def inorder_search(cur,nodes,out_list):
    value,left,right = nodes[cur].value,nodes[cur].left,nodes[cur].right
    if left != None:
        inorder_search(left,nodes,out_list)
    out_list.append(value)
    if right != None:
        inorder_search(right,nodes,out_list)

def inorder(nodes,root):
    out_list = []
    cur = root
    inorder_search(cur,nodes,out_list)
    out = ""
    for i in out_list:
        out += " "+str(i)
    return out

def postorder_search(cur,nodes,out_list):
    value,left,right = nodes[cur].value,nodes[cur].left,nodes[cur].right

    if left != None:
        postorder_search(left,nodes,out_list)
    if right != None:
        postorder_search(right,nodes,out_list)
    out_list.append(value)

def postorder(nodes,root):
    out_list = []
    cur = root

    postorder_search(cur,nodes,out_list)
    out = ""
    for i in out_list:
        out += " "+str(i)
    return out

if __name__ == "__main__":
    n = int(input())
    nodes = [node() for _ in range(n)]
    for i in range(n):
        value,left,right = map(int,input().split())
        nodes[value].value = value
        if right != -1:
            nodes[value].right = right
            nodes[right].parent = value
        if left != -1:
            nodes[value].left = left
            nodes[left].parent = value
    root = 0
    for i in range(n):
        if nodes[i].parent is None:
            root = i

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

Solution (Python):
import sys
n = int(input())
class Node:
  def __init__(self):
    self.p = -1 
    self.l = -1 
    self.r = -1 

T = [Node() for _ in range(n)]
sys.setrecursionlimit(1500)

for i in range(n):
    v,l,r = map(int,input().split())
    T[v].r = r
    if r != -1:
      T[r].p = v
    T[v].l = l
    if l != -1:
      T[l].p = v

for i in range(n):
  
  if T[i].p == -1 : r = i

ret = []
def preorder(v):
  if v == -1: return
  ret.append(v)
  preorder(T[v].l)
  preorder(T[v].r)

def inorder(v):
  if v == -1: return
  inorder(T[v].l)
  ret.append(v)
  inorder(T[v].r)

def postorder(v):
  if v == -1: return
  postorder(T[v].l)
  postorder(T[v].r)
  ret.append(v)

ret = []
preorder(r)
print("Preorder")
print(""," ".join(map(str,ret)))
ret = []
inorder(r)
print("Inorder")
print(""," ".join(map(str,ret)))
ret = []
postorder(r)
print("Postorder")
print(""," ".join(map(str,ret)))

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

def Preorder_Tree_Walk(T, u):    
    if u == -1:
        return
    
    print(" " + str(u), end="")
    Preorder_Tree_Walk(T, T[u].left)
    Preorder_Tree_Walk(T, T[u].right)

def Inorder_Tree_Walk(T, u):   
    if u == -1:
        return

    Inorder_Tree_Walk(T, T[u].left)
    print(" " + str(u), end="")
    Inorder_Tree_Walk(T, T[u].right)

def Postorder_Tree_Walk(T, u):    
    if u == -1:
        return

    Postorder_Tree_Walk(T, T[u].left)
    Postorder_Tree_Walk(T, T[u].right)
    print(" " + str(u), end="")

def Main():

    n = int(input())
    T = [Node(-1, -1, -1) for i in range(n)]

    for i in range(n):
        node_id, left, right = map(int, input().split())

        T[node_id].left = left
        T[node_id].right = right

        if left != -1:
            T[left].parent = node_id
        if right != -1:
            T[right].parent = node_id

    r = 0
    for i in range(len(T)):
        if T[i].parent == -1:
            r = i
            
    print("Preorder")
    Preorder_Tree_Walk(T, r)
    print()
    print("Inorder")
    Inorder_Tree_Walk(T, r)
    print()
    print("Postorder")
    Postorder_Tree_Walk(T, r)
    print()

Main()

Solution (Python):
from collections import defaultdict

class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None
    self.parent = -1


preorder, inorder, postorder = [], [], []

def preorder_dfs(root):
  if root is None: return

  preorder.append(root.val)

  preorder_dfs(root.left)
  preorder_dfs(root.right)

def inorder_dfs(root):
  if root is None: return

  inorder_dfs(root.left)

  inorder.append(root.val)

  inorder_dfs(root.right)


def postorder_dfs(root):
  if root is None: return 
  
  postorder_dfs(root.left)
  postorder_dfs(root.right)

  postorder.append(root.val) 


num = int(input())
nodes = defaultdict(int)

for i in range(num):
  val, left, right = list(map(int, input().split()))

  if nodes[val] == 0:
    nodes[val] = TreeNode(val)
  n = nodes[val]
  
  if left != -1:
    
    if nodes[left] == 0:
      nodes[left] = TreeNode(left)

    
    n.left = nodes[left]
    n.left.parent = n.val

  if right != -1:
    if nodes[right] == 0:
      nodes[right] = TreeNode(right)

    n.right = nodes[right]
    n.right.parent = n.val

root = [node for node in nodes.values() if node.parent == -1][0]

preorder_dfs(root)
inorder_dfs(root)
postorder_dfs(root)

print("Preorder")
print(" " + " ".join([ str(i) for i in preorder]))
print("Inorder")
print(" " + " ".join([ str(i) for i in inorder]))
print("Postorder")
print(" " + " ".join([ str(i) for i in postorder]))

Solution (Python):
class Node:
    def __init__(self, num=None, parent=None, left=None, right=None, type=None):
        self.num = num
        self.parent = parent
        self.left = left
        self.right = right
        self.type = type

    def __str__(self):
        return str(self.num)

def getType(node):
    if node.parent is None:
        return 'root'
    elif node.left is None and node.right is None:
        return 'leaf'
    else:
        return 'internal node'

def addNodeNumToResult (node, result):
    """
    Add node number to a list (converted to string)
    :param node: a node
    :param result: a list that stores result
    :return: Nothing
    """
    result.append(str(node.num))

def preParse(node, result):
    if node is None:
        return
    addNodeNumToResult(node, result)
    preParse(node.left, result)
    preParse(node.right, result)

def inParse(node, result):
    if node is None:
        return
    inParse(node.left, result)
    addNodeNumToResult(node, result)
    inParse(node.right, result)

def postParse(node, result):
    if node is None:
        return
    postParse(node.left, result)
    postParse(node.right, result)
    addNodeNumToResult(node, result)




n = int(input())
nodes = []


for i in range(n):
    node = Node(i)
    nodes.append(node)


for i in range(n):
    num, leftNum, rightNum = map(int, input().split())
    node = nodes[num]
    if leftNum != -1:
        node.left = nodes[leftNum]
        node.left.parent = node
    if rightNum != -1:
        node.right = nodes[rightNum]
        node.right.parent = node


for node in nodes:
    node.type = getType(node)
    if node.type == 'root':
        root = node

result = []
preParse(root, result)
print('Preorder')
print('', end=' ')
print(' '.join(result))

result = []
inParse(root, result)
print('Inorder')
print('', end=' ')
print(' '.join(result))

result = []
postParse(root, result)
print('Postorder')
print('', end=' ')
print(' '.join(result))

Solution (Python):



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


def preorder(nodes, cur_id, result):
    node = nodes[cur_id]
    result.append(node.id)
    if node.left >= 0:
        preorder(nodes, node.left, result)
    if node.right >= 0:
        preorder(nodes, node.right, result)
    
    return


def inorder(nodes, cur_id, result):
    node = nodes[cur_id]
    if node.left >= 0:
        inorder(nodes, node.left, result)
    result.append(node.id)
    if node.right >= 0:
        inorder(nodes, node.right, result)
    
    
def postorder(nodes, cur_id, result):
    node = nodes[cur_id]
    if node.left >= 0:
        postorder(nodes, node.left, result)
    if node.right >= 0:
        postorder(nodes, node.right, result)
    result.append(node.id)


N = int(input())
nodes = [Node(i) for i in range(N)]
for i in range(N):
    id, left, right = [int(i) for i in input().split()]
    nodes[id].left, nodes[id].right = left, right
    if left >= 0:
        nodes[left].parent = id
    if right >= 0:
        nodes[right].parent = right

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

print('Preorder')
result = []
preorder(nodes, root, result)
print('', *result)

print('Inorder')
result = []
inorder(nodes, root, result)
print('', *result)

print('Postorder')
result = []    
postorder(nodes, root, result)
print('', *result)

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
HUGE_NUM = 9999999999999999
MOD = 1000000007
EPS = 0.000000001


global nodes

class Node:
    def __init__(self):
        self.left = -1
        self.right = -1
    def set(self,arg_node_left,arg_node_right):
        self.left = arg_node_left
        self.right = arg_node_right


def Preorder(node_id):
    print(" %d"%(node_id),end = "")

    if nodes[node_id].left != -1:
        Preorder(nodes[node_id].left)

    if nodes[node_id].right != -1:
        Preorder(nodes[node_id].right)


def Inorder(node_id):

    if nodes[node_id].left != -1:
        Inorder(nodes[node_id].left)

    print(" %d"%(node_id),end = "")

    if nodes[node_id].right != -1:
        Inorder(nodes[node_id].right)


def Postorder(node_id):

    if nodes[node_id].left != -1:
        Postorder(nodes[node_id].left)

    if nodes[node_id].right != -1:
        Postorder(nodes[node_id].right)

    print(" %d"%(node_id),end = "")




V = int(input())
nodes = [Node() for _ in range(V)]
in_num = [0]*V


for loop in range(V):
    node_id,left,right = map(int,input().split())
    nodes[node_id].set(left,right)
    if left != -1:
        in_num[left] += 1
    if right != -1:
        in_num[right] += 1

root = -1

for i in range(V):
    if in_num[i] == 0:
        root = i
        break

print("Preorder")
Preorder(root)
print()

print("Inorder")
Inorder(root)
print()

print("Postorder")
Postorder(root)
print()

Solution (Python):
from collections.abc import Iterable

n = int(input())
nodes = {}
for _ in range(n):
    key, left, right = map(int, input().split())
    nodes[key] = (left, right)
keys = set(nodes.keys())
for left, right in nodes.values():
    keys -= {left, right}
root = keys.pop()


def flatten(arr):
    for a in arr:
        if isinstance(a, Iterable) and not isinstance(a, (str, bytes)):
            yield from flatten(a)
        else:
            yield a


def pre_tw(key):
    left, right = nodes[key]
    if left == -1 and right == -1:
        return [key]
    elif left == -1:
        return [key, pre_tw(right)]
    elif right == -1:
        return [key, pre_tw(left)]
    else:
        return [key, pre_tw(left), pre_tw(right)]


def in_tw(key):
    left, right = nodes[key]
    if left == -1 and right == -1:
        return [key]
    elif left == -1:
        return [key, in_tw(right)]
    elif right == -1:
        return [in_tw(left), key]
    else:
        return [in_tw(left), key, in_tw(right)]


def post_tw(key):
    left, right = nodes[key]
    if left == -1 and right == -1:
        return [key]
    elif left == -1:
        return [post_tw(right), key]
    elif right == -1:
        return [post_tw(left), key]
    else:
        return [post_tw(left), post_tw(right), key]


print("Preorder")
for a in flatten(pre_tw(root)):
    print(" {}".format(a), end="")
print()

print("Inorder")
for a in flatten(in_tw(root)):
    print(" {}".format(a), end="")
print()

print("Postorder")
for a in flatten(post_tw(root)):
    print(" {}".format(a), end="")
print()

Solution (Python):
n= int(input())
a = [list(map(int, input().split())) for _ in range(n)]

p = [-1]*n
r = [-1]*n
l = [-1]*n

for i in range(n):
    ind = a[i][0]
    r[ind] = a[i][2]
    l[ind] = a[i][1]
    if r[ind]>=0:
        p[r[ind]] = ind
    if l[ind]>=0:
        p[l[ind]] = ind

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

def preorder(ind):
    print(' %i'%ind, end='')
    if l[ind]!=-1:
        preorder(l[ind])
    if r[ind]!=-1:
        preorder(r[ind])
        
def inorder(ind):
    if l[ind]!=-1:
        inorder(l[ind])
    print(' %i'%ind, end='')
    if r[ind]!=-1:
        inorder(r[ind])
        
def postorder(ind):
    if l[ind]!=-1:
        postorder(l[ind])
    if r[ind]!=-1:
        postorder(r[ind])
    print(' %i'%ind, end='')
    
print('Preorder')
preorder(root)
print()
print('Inorder')
inorder(root)
print()
print('Postorder')
postorder(root)
print()

Solution (Python):
N = int(input())
T = [list(map(int,input().split())) for _ in range(N)]

T.sort(key = lambda x:x[0])

class Node:
    def __init__(self,data,l_child,r_child):
        self.data = data
        self.l_child = l_child
        self.r_child = r_child

T = [Node(T[i][0],T[i][1],T[i][2]) for i in range(N)]

P = [-1 for _ in range(N)]
for i in range(N):
    if T[i].l_child != -1:
        P[T[i].l_child] = T[i].data
    if T[i].r_child != -1:
        P[T[i].r_child] =T[i].data
for i in range(N):
    if P[i] == -1:
        root = i

def Pre_patrol(node,List):
    if node.data != -1:
        List.append(node.data)
        if node.l_child != -1:
            Pre_patrol(T[node.l_child],List)
        if node.r_child != -1:
            Pre_patrol(T[node.r_child],List)
    return List

def In_patrol(node,List):
    if node.data != -1:
        if node.l_child != -1:
            In_patrol(T[node.l_child],List)
        List.append(node.data)
        if node.r_child != -1:
            In_patrol(T[node.r_child],List)
    return List

def Pos_patrol(node,List):
    if node.data != -1:
        if node.l_child != -1:
            Pos_patrol(T[node.l_child],List)
        if node.r_child != -1:
            Pos_patrol(T[node.r_child],List)
        List.append(node.data)
    return List

print("Preorder")
for i in range(N):
    print(" "+str(Pre_patrol(T[root],[])[i]),end="")
print()
print("Inorder")
for i in range(N):
    print(" "+str(In_patrol(T[root],[])[i]),end="")
print()
print("Postorder")
for i in range(N):
    print(" "+str(Pos_patrol(T[root],[])[i]),end="")
print()

Solution (Python):
N = int(input())
tree = [{'parent': -1, 'left': -1, 'right': -1, 'sibling': -1} for _ in range(N)]
parent = set(n for n in range(N))

for _ in range(N):
    inp = [int(n) for n in input().split()]
    tree[inp[0]]['left'] = inp[1]
    tree[inp[0]]['right'] = inp[2]

    if inp[1] != -1:
        tree[inp[1]]['parent'] = inp[0]
        tree[inp[1]]['sibling'] = inp[2]
    if inp[2] != -1:
        tree[inp[2]]['parent'] = inp[0]
        tree[inp[2]]['sibling'] = inp[1]
    parent = parent.difference(inp[1:])

root = parent.pop()

def preParse(u):
    if u == -1:
        return 
    print(f' {u}', end = '')
    preParse(tree[u]['left'])
    preParse(tree[u]['right'])

def inParse(u):
    if u == -1:
        return 
    inParse(tree[u]['left'])
    print(f' {u}', end = '')
    inParse(tree[u]['right'])

def postParse(u):
    if u == -1:
        return 
    postParse(tree[u]['left'])
    postParse(tree[u]['right'])
    print(f' {u}', end = '')

print('Preorder')
preParse(root)
print()

print('Inorder')
inParse(root)
print()

print('Postorder')
postParse(root)
print()

Solution (Python):
class Node():
    def __init__(self, id):
        self.id = id
        self.left = None
        self.right = None
        self.parent = None
        self.marked = 0
    def setLeft(self, left):
        left.parent = self
        self.left = left
    def setRight(self, right):
        right.parent = self
        self.right = right
    def __str__(self):
        return str(self.id)


def preorder(arr, root, res):
    if root == None:
        return
    res.append(root)
    preorder(arr, root.left, res)
    preorder(arr, root.right, res)

def inorder(arr, root, res):
    if root == None:
        return
    inorder(arr, root.left, res)
    res.append(root)
    inorder(arr, root.right, res)

def postorder(arr, root, res):
    if root == None:
        return
    postorder(arr, root.left, res)
    postorder(arr, root.right, res)
    res.append(root)


def main():
    n = int(input())
    array = [Node(i) for i in range(n)]
    for node in array:
        i, l, r = list(map(int, input().split()))
        array[i].setLeft(array[l]) if l != -1 else None
        array[i].setRight(array[r]) if r != -1 else None
    
    root = None
    for node in array:
        if node.parent == None:
            root = node
            break

    res = []
    preorder(array, root, res)
    print("Preorder\n ", end="")
    print(*res) 
    res = [] 
    inorder(array, root, res)
    print("Inorder\n ", end="")
    print(*res)
    res = []
    postorder(array, root, res)
    print("Postorder\n ", end="")
    print(*res)
    
if __name__ == "__main__":
    main()

Solution (Python):
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    from collections import defaultdict

    NIL = -1

    n = int(input())

    
    T = defaultdict(lambda: {'l':NIL, 'r':NIL, 'p':NIL})

    for _ in range(n):
        u, l, r = map(int, input().split())
        T[u]['l'] = l
        T[u]['r'] = r
        if l != NIL:
            T[l]['p'] = u
        if r != NIL:
            T[r]['p'] = u

    for u, info in T.items():
        if info['p'] == NIL:
            root = u
            break

    
    def pre_parse(u):
        if u == NIL:
            return
        print(' ' + str(u), end='')
        pre_parse(T[u]['l'])
        pre_parse(T[u]['r'])

    
    def in_parse(u):
        if u == NIL:
            return
        in_parse(T[u]['l'])
        print(' ' + str(u), end='')
        in_parse(T[u]['r'])

    
    def post_parse(u):
        if u == NIL:
            return
        post_parse(T[u]['l'])
        post_parse(T[u]['r'])
        print(' ' + str(u), end='')

    print('Preorder')
    pre_parse(root)
    print('')

    print('Inorder')
    in_parse(root)
    print('')

    print('Postorder')
    post_parse(root)
    print('')

Solution (Python):
if __name__ == "__main__":
    parent, children = {}, {}
    preorder, inorder, postorder = [], [], []
    n = int(input())
    for _ in range(n):
        i, left, right = input().split()
        children[i] = dict(right=right, left=left)
        for child in children[i].values():
            if child != "-1":
                parent[child] = i
    
    root = (set(children) - set(parent)).pop()
    parent[root] = "-1"
    
    def set_preorder(i):
        if i == "-1":
            return
        preorder.append(i)
        set_preorder(children[i]["left"])
        set_preorder(children[i]["right"])
    
    def set_inorder(i):
        if i == "-1":
            return
        set_inorder(children[i]["left"])
        inorder.append(i)
        set_inorder(children[i]["right"])

    def set_postorder(i):
        if i == "-1":
            return
        set_postorder(children[i]["left"])
        set_postorder(children[i]["right"])
        postorder.append(i)
                
    set_preorder(root)
    set_inorder(root)
    set_postorder(root)

    print("Preorder")
    print(" " + " ".join(preorder))
    print("Inorder")
    print(" " + " ".join(inorder))
    print("Postorder")
    print(" " + " ".join(postorder))