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):
N = int(input())
nodes = [[-1,-1,-1] for i in range(N)]

for k in range(N):
    i,l,r = map(int,input().split())
    nodes[i][1] = l
    nodes[i][2] = r
    if l != -1:
        nodes[l][0] = i
    if r != -1:
        nodes[r][0] = i



def preParse(u):
    if u == -1:
        return
    print(' {}'.format(u), end='')
    preParse(nodes[u][1])
    preParse(nodes[u][2])

def inParse(u):
    if u == -1:
        return
    inParse(nodes[u][1])
    print(' {}'.format(u), end='')
    inParse(nodes[u][2])

def postParse(u):
    if u == -1:
        return
    postParse(nodes[u][1])
    postParse(nodes[u][2])
    print(' {}'.format(u), end='')

root = 0
while nodes[root][0] != -1:
    root = nodes[root][0]

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

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

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

Solution (Python):


import sys
sys.setrecursionlimit(10**9)  

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

n = int(input())
prt = [-1 for i in range(n)]
chd = [[] for i in range(n)]
root = -1

def preOrder(num):
    if num == -1:
        return
    print(f' {num}', end = '')
    preOrder(chd[num][0])
    preOrder(chd[num][1])

def inOrder(num):
    if num == -1:
        return
    inOrder(chd[num][0])
    print(f' {num}', end = '')
    inOrder(chd[num][1])

def postOrder(num):
    if num == -1:
        return
    postOrder(chd[num][0])
    postOrder(chd[num][1])
    print(f' {num}', end = '')
    
for i in range(n):
    idx, left, right = map(int, input().split())
    chd[idx].append(left)
    chd[idx].append(right)
    if left >= 0:
        prt[left] = idx
    if right >= 0:
        prt[right] = idx

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

print('Preorder')
preOrder(root)
print('\nInorder')
inOrder(root)
print('\nPostorder')
postOrder(root)
print('')

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

pre = []
def preorder(t, n):
    pre.append(n)
    if t[n].left is not None:
        preorder(t, t[n].left)
    if t[n].right is not None:
        preorder(t, t[n].right)

ino = []
def inorder(t, n):
    if t[n].left is not None:
        inorder(t, t[n].left)
        ino.append(n)
    else:
        ino.append(n)
    if t[n].right is not None:
        inorder(t, t[n].right)
    if n not in ino:
        ino.append(n)

post = []
def postorder(t, n):
    if t[n].left is not None:
        postorder(t, t[n].left)
    if t[n].right is not None:
        postorder(t, t[n].right)
    post.append(n)

n = int(input())
t = {k: Node(None, None, None) for k in range(n)}
for _ in range(n):
    tmp = list(map(int, input().split()))
    if tmp[1] != -1:
        t[tmp[1]].parent = tmp[0] 
        t[tmp[0]].left = tmp[1] 
    if tmp[2] != -1:
        t[tmp[2]].parent = tmp[0] 
        t[tmp[0]].right = tmp[2] 

for node in range(n):
    if t[node].parent is None:
        preorder(t, node)
        inorder(t, node)
        postorder(t, node)

print("Preorder")
print(" " + " ".join([str(k) for k in pre]))
print("Inorder")
print(" " + " ".join([str(k) for k in ino]))
print("Postorder")
print(" " + " ".join([str(k) for k in post]))

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

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

for _ in range(n):
    idx,left,right=map(int,input().split())
    nodes[idx].val=idx
    nodes[idx].left=left
    nodes[idx].right=right
    if(left!=-1):
        nodes[left].parent=idx
    if(right!=-1):
        nodes[right].parent=idx

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

preorder_idx=[]
def preOrder(idx):
    preorder_idx.append(idx)
    if(nodes[idx].left!=-1):
        preOrder(nodes[idx].left)
    if(nodes[idx].right!=-1):
        preOrder(nodes[idx].right)

inorder_idx=[]
def inOrder(idx):
    if(nodes[idx].left!=-1):
        inOrder(nodes[idx].left)
    inorder_idx.append(idx)
    if(nodes[idx].right!=-1):
        inOrder(nodes[idx].right)

postorder_idx=[]
def postOrder(idx):
    if(nodes[idx].left!=-1):
        postOrder(nodes[idx].left)
    if(nodes[idx].right!=-1):
        postOrder(nodes[idx].right)
    postorder_idx.append(idx)


preOrder(root_idx)
inOrder(root_idx)
postOrder(root_idx)

print("Preorder")
print(" ",end="")
print(*preorder_idx)

print("Inorder")
print(" ",end="")
print(*inorder_idx)

print("Postorder")
print(" ",end="")
print(*postorder_idx)

Solution (Python):
class Node:
    def __init__(self, id):
        self.id = id
        self.left = -1
        self.right = -1
def walk_preorder(node, order_list):
    if node == None:
        return 0
    order_list.append(node.id)
    walk_preorder(nodes.get(node.left), order_list)
    walk_preorder(nodes.get(node.right), order_list)
def walk_inorder(node, order_list):
    if node == None:
        return 0
    walk_inorder(nodes.get(node.left), order_list)
    order_list.append(node.id)
    walk_inorder(nodes.get(node.right), order_list)
def walk_postorder(node, order_list):
    if node == None:
        return 0
    walk_postorder(nodes.get(node.left), order_list)
    walk_postorder(nodes.get(node.right), order_list)
    order_list.append(node.id)

n = int(input())
nodes = {}
for _ in range(n):
    id, left, right = [int(x) for x in input().split(' ')]
    node = Node(id)
    node.left = left
    node.right = right
    nodes[id] = node
is_child_table = {node_id:False for node_id in range(n)}
for id in nodes:
    if nodes[id].left > -1:
        is_child_table[nodes[id].left] = True
    if nodes[id].right > -1:
        is_child_table[nodes[id].right] = True
root_id = [node_id for node_id in is_child_table.keys() if is_child_table[node_id] == False][0]
root_node = nodes[root_id]

preorder_list = []
inorder_list = []
postorder_list = []
walk_preorder(root_node, preorder_list)
walk_inorder(root_node, inorder_list)
walk_postorder(root_node, postorder_list)
print('Preorder')
preorder_str = ' '.join(map(str, preorder_list))
print(' {}'.format(preorder_str))
print('Inorder')
inorder_str = ' '.join(map(str, inorder_list))
print(' {}'.format(inorder_str))
print('Postorder')
postorder_str = ' '.join(map(str, postorder_list))
print(' {}'.format(postorder_str))

Solution (Python):
class Tree:
  def __init__(self):
    self.parent = -1
    self.brother = -1
    self.lchild = -1
    self.rchild = -1

n = int(input())

A = [Tree() for _ in range(n)]

for i in range(n):
  id, *children = [int(x) for x in input().split()]
  A[id].lchild, A[id].rchild = children
  if A[id].lchild != -1 and A[id].rchild != -1:
    A[A[id].lchild].brother = A[id].rchild
  for child in children:
    if child != -1:
      A[child].parent = id

root = [i for i, x in enumerate(A) if x.parent == -1][0]

def preorder(A,C,a):
  C.append(a)
  F = []
  if A[a].lchild != -1:
    preorder(A,C,A[a].lchild)
    if A[a].rchild != -1:
      F.append(A[a].rchild)
  elif A[a].rchild != -1:
    preorder(A,C,A[a].rchild)
  elif A[a].brother != -1:
    preorder(A,C,A[a].brother)
  while F != []:
    f = F.pop()
    if not f in C:
      preorder(A,C,f)
  return C

def start(A,a):
  global b
  b = A[a].lchild
  if b != -1:
    start(A,b)
  else:
    b = a
  return b

def inorder(A,D,a):
  if A[a].lchild == -1:
    D.append(a)
    if A[a].rchild != -1:
      inorder(A,D,start(A,A[a].rchild))
  if A[a].parent != -1:
    c = A[a].parent
    if a == A[c].lchild and A[c].rchild != -1:
      D.append(c)
      inorder(A,D,start(A,A[c].rchild))
    elif a == A[c].lchild and A[c].rchild == -1:
      D.append(c)
      inorder(A,D,c)
    elif a == A[c].rchild and A[c].lchild != -1:
      inorder(A,D,c)

def postorder(A,E,a,e):
  if A[a].lchild == -1 and A[a].rchild != -1:
    postorder(A,E,start(A,A[a].rchild),A[a].rchild)
  E.append(a)
  if a != e:
    if A[a].brother != -1:
      postorder(A,E,start(A,A[a].brother),e)
    else:
      postorder(A,E,A[a].parent,e)

C = []
D = []
E = []

print("Preorder")
print(" ",end="")
print(" ".join(map(str, preorder(A,C,root))))
print("Inorder")
print(" ",end="")
s = start(A,root)
inorder(A,D,s)
print(" ".join(map(str, D)))
print("Postorder")
print(" ",end="")
postorder(A,E,s,root)
print(" ".join(map(str, E)))

Solution (Python):
def preOrder(s):
	print(" " + str(s),end="")
	if main[s][1] != -1:
		preOrder(main[s][1])
	if main[s][2] != -1:
		preOrder(main[s][2])

def inOrder(s):
	if main[s][1] != -1:
		inOrder(main[s][1])
	print(" " + str(s),end="")
	if main[s][2] != -1:
		inOrder(main[s][2])

def postOrder(s):
	if main[s][1] != -1:
		postOrder(main[s][1])
	if main[s][2] != -1:
		postOrder(main[s][2])
	print(" " + str(s),end="")

n = int(input())
main = [[-1] * 1 for i in range(n+1)]
for i in range(n):
	a = input().split()
	for j in range(1,3):
		main[int(a[j])][0] = int(a[0])
		main[int(a[0])].append(int(a[j]))
	

del a


for i in range(n):
	if main[i][0] == -1:
		print("Preorder")
		preOrder(int(i))
		print()
		print("Inorder")
		inOrder(int(i))
		print()
		print("Postorder")
		postOrder(int(i))
		break
print()

Solution (Python):
class Node:
    
    def __init__(self, parent = -1, left = -1, right = -1):
        self.parent = parent
        self.left = left
        self.right = right
    
    def get_degree(self):
        d = 0
        if self.left != -1:
            d += 1
        if self.right != -1:
            d += 1
        return d

class BinaryTree:
    
    def __init__(self, size):
        self.tree = [Node() for i in range(N)]
    
    def set(self, node_id, left, right):
        self.tree[node_id].left = left
        self.tree[node_id].right = right

        if left != -1:
            self.tree[left].parent = node_id
        if right != -1:
            self.tree[right].parent = node_id
    
    def get_root(self):
        for i in range(len(self.tree)):
            node = self.tree[i]
            if node.parent == -1:
                return i
    
    def walk_preorder(self, node):
        if node == -1:
            return
        print(' %d' % (node), end = '')
        self.walk_preorder(self.tree[node].left)
        self.walk_preorder(self.tree[node].right)
    
    def walk_inorder(self, node):
        if node == -1:
            return
        self.walk_inorder(self.tree[node].left)
        print(' %d' % (node), end = '')
        self.walk_inorder(self.tree[node].right)
    
    def walk_postorder(self, node):
        if node == -1:
            return
        self.walk_postorder(self.tree[node].left)
        self.walk_postorder(self.tree[node].right)
        print(' %d' % (node), end = '')

N = int(input())


binary_tree = BinaryTree(N)


for _ in range(N):
    node_id, left, right = list(map(int, input().split()))
    binary_tree.set(node_id, left, right)

root = binary_tree.get_root()

print('Preorder')
binary_tree.walk_preorder(root)
print('\n', end = '')
print('Inorder')
binary_tree.walk_inorder(root)
print('\n', end = '')
print('Postorder')
binary_tree.walk_postorder(root)
print('\n', end = '')

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

def preParse(u):
    if u ==-1:
        return
    print(" %d"%(u),end = "")
    
    preParse(Nodes[u].left)
    preParse(Nodes[u].right)

def inParse(u):
    if u ==-1:
        return
    inParse(Nodes[u].left)
    print(" %d"%(u),end = "")

    
    inParse(Nodes[u].right)

def postParse(u):
    if u ==-1:
        return
    postParse(Nodes[u].left)
    postParse(Nodes[u].right)
    
    print(" %d"%(u),end = "")



def decode_node_data(n):
    '''
    n...受け取る文字列、一行ずつ
    一行ずつ、文字列からノードに変化する
    '''
    global Nodes
    num_of_elem = len(n)
    if num_of_elem < 2:
        raise ValueError
    elif num_of_elem == 2:  
        pass

    else:
        id, left,right = list(map(int,n))
        
        Nodes[id].left = left
        if left!=-1:
            Nodes[left].parent=id
        
        Nodes[id].right = right
        if right !=-1 :
            Nodes[right].parent=id


MAX_NODES = 100001
Nodes = [Node(-1, None, None) for _ in range(MAX_NODES)]
if __name__ == "__main__":

    num_of_nodes = int(input())
    node_data = []
    for _ in range(num_of_nodes):
        node_data.append(input().split(' '))

    for n in node_data:
        decode_node_data(n)
    
    for i in range(num_of_nodes):
        if Nodes[i].parent==-1:
            root=i
    
    print('Preorder')
    preParse(root)
    print()
    
    print('Inorder')
    inParse(root)
    print()
    
    print('Postorder')
    postParse(root)
    print()

Solution (Python):
"""
与えられた二分木の全ての節点を体系的に訪問する
"""
import copy

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



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


for i in range(n):
    l = list(map(int, input().split()))
    node_id = l[0]

    for j in range(2):
        try:
            child = l[1+j] 
            nodes[node_id].children.append(child) 
            if not child == -1:
                nodes[child].parent = node_id 
        except:
            pass 
    else:
        pass 

def getRoot(node_id):
    target = nodes[node_id]
    if target.parent == -1:
        return node_id

def preParse(node_id):
    if node_id == -1:
        return
    print(' '+str(node_id), end='')
    preParse(nodes[node_id].children[0])
    preParse(nodes[node_id].children[1])

def inParse(node_id):
    if node_id == -1:
        return
    inParse(nodes[node_id].children[0])
    print(' '+str(node_id), end='')
    inParse(nodes[node_id].children[1])

def postParse(node_id):
    if node_id == -1:
        return
    postParse(nodes[node_id].children[0])
    postParse(nodes[node_id].children[1])
    print(' '+str(node_id), end='')

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

print('Preorder')
preParse(root_id)
print('\nInorder')
inParse(root_id)
print('\nPostorder')
postParse(root_id)
print()

Solution (Python):
import sys

def preorder_tree_walk(nid, route):
    left = nodes[nid][1]
    right = nodes[nid][2]
    route.append(nid)
    if left != -1: preorder_tree_walk(left, route)
    if right != -1: preorder_tree_walk(right, route)
    return route

def inorder_tree_walk(nid, route):
    left = nodes[nid][1]
    right = nodes[nid][2]
    if left != -1: inorder_tree_walk(left, route)
    route.append(nid)
    if right != -1: inorder_tree_walk(right, route)
    return route

def postorder_tree_walk(nid, route):
    left = nodes[nid][1]
    right = nodes[nid][2]
    if left != -1: postorder_tree_walk(left, route)
    if right != -1: postorder_tree_walk(right, route)
    route.append(nid)
    return route

n = int(input())
nodes = [[-1, -1, -1] for _ in range(n)]

for _ in range(n):
    nid, left, right = list(map(int, sys.stdin.readline().split()))
    nodes[nid][1] = left
    nodes[nid][2] = right

    if left != -1: nodes[left][0] = nid
    if right != -1: nodes[right][0] = nid

for nid, node in enumerate(nodes):
    root_nid = nid
    if node[0] == -1: break

preorder_route = preorder_tree_walk(root_nid, [])
inorder_route = inorder_tree_walk(root_nid, [])
postorder_route = postorder_tree_walk(root_nid, [])

print('Preorder')
print('', *preorder_route)
print('Inorder')
print('', *inorder_route)
print('Postorder')
print('', *postorder_route)

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 

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


n = int(input())
node = {}
for i in range(n):
    node[i] = Node(-1, -1, -1)


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


def pre_parse(T, u, pre_list):
    if u == -1:
        return
    pre_list.append(u)
    pre_parse(T, T[u].l, pre_list)
    pre_parse(T, T[u].r, pre_list)

def in_parse(T, u, in_list):
    if u == -1:
        return
    in_parse(T, T[u].l, in_list)
    in_list.append(u)
    in_parse(T, T[u].r, in_list)

def post_parse(T, u, post_list):
    if u == -1:
        return
    post_parse(T, T[u].l, post_list)
    post_parse(T, T[u].r, post_list)
    post_list.append(u)


for k, v in node.items():
    if v.p == -1:
        root = k

pre_list = []
in_list = []
post_list = []
pre_parse(node, root, pre_list)
in_parse(node, root, in_list)
post_parse(node, root, post_list)

print('Preorder')
print('', *pre_list)
print('Inorder')
print('', *in_list)
print('Postorder')
print('', *post_list)

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


class BinaryTree(list):
    def __init__(self, n):
        super().__init__([BinaryNode() for _ in range(n)])
        self.len = n
        self.root = None

    def set_node(self, id, left, right):
        self[id].left = left
        self[id].right = right
        if left > -1:
            self[left].parent = id
        if right > -1:
            self[right].parent = id

    def __set_depth(self, id, depth):
        self[id].depth = depth
        if self[id].left > -1:
            self.__set_depth(self[id].left, depth + 1)
        if self[id].right > -1:
            self.__set_depth(self[id].right, depth + 1)

    def set_depth(self):
        self.__set_depth(self.root, 0)

    def __set_height(self, id):
        if id == -1:
            return -1
        height = 1 + max(self.__set_height(self[id].left), self.__set_height(self[id].right))
        self[id].height = height
        return height

    def set_height(self):
        self.__set_height(self.root)

    def set_root(self):
        for i in range(self.len):
            if self[i].parent == -1:
                self.root = i
                break

    def get_nodetype(self, i):
        if self[i].parent == -1:
            return "root"
        elif self[i].left == -1 and self[i].right == -1:
            return "leaf"
        else:
            return "internal node"

    def get_sibling(self, i):
        parent = self[i].parent
        if parent == -1:
            return -1
        if self[parent].left == i:
            return self[parent].right
        else:
            return self[parent].left

    def get_degree(self, i):
        return (self[i].left > -1) * 1 + (self[i].right > -1) * 1

    def set_all(self):
        self.set_root()
        self.set_depth()
        self.set_height()

    def print(self):
        for i in range(self.len):
            print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
                i, self[i].parent, self.get_sibling(i), self.get_degree(i),
                self[i].depth, self[i].height, self.get_nodetype(i)))

    def __preorder(self, id):
        if id == -1:
            return []
        return [id] + self.__preorder(self[id].left) + self.__preorder(self[id].right)

    def order_str(self, order_type):
        if order_type == 0:
            order_list = self.__preorder(self.root)
        elif order_type == 1:
            order_list = self.__inorder(self.root)
        else:
            order_list = self.__postorder(self.root)

        return " ".join(map(str, order_list))

    def __inorder(self, id):
        if id == -1:
            return []
        return self.__inorder(self[id].left) + [id] + self.__inorder(self[id].right)

    def __postorder(self, id):
        if id == -1:
            return []
        return self.__postorder(self[id].left) + self.__postorder(self[id].right) + [id]


def main():
    n = int(input())
    tree = BinaryTree(n)
    for _ in range(n):
        node_info = input().split(" ")
        node_info = list(map(int, node_info))
        tree.set_node(node_info[0], node_info[1], node_info[2])
    tree.set_all()
    print("Preorder")
    print(" " + tree.order_str(0))
    print("Inorder")
    print(" " + tree.order_str(1))
    print("Postorder")
    print(" " + tree.order_str(2))


if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
nil=-1
t=[[-1,-1,-1]for _ in range(n)]
for i in range(n):
	a,b,c=map(int,input().split())
	if b!=-1:
		t[b][0]=a
		t[a][1]=b
	if c!=-1:
		t[c][0]=a
		t[a][2]=c
cnt=0
for i in range(n):
	if t[i][0]==-1:
		root=i
		break
def pre(u):
	if u==nil:
		return
	print(" "+str(u),end="")
	pre(t[u][1])
	pre(t[u][2])
def pre2(u):
	if u==nil:
		return
	pre2(t[u][1])
	print(" "+str(u),end="")
	pre2(t[u][2])
def pre3(u):
	if u==nil:
		return
	pre3(t[u][1])
	pre3(t[u][2])
	global cnt
	if cnt==n-1:
		print(" "+str(u))
	else:
		print(" "+str(u),end="")
	cnt+=1
print("Preorder")
pre(root)
print("\n"+"Inorder")
pre2(root)
print("\n"+"Postorder")
pre3(root)

Solution (Python):




null = -1

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

def preParse(u):
    if u == null:
        return
    print(" ", end = "")
    print(Tree[u].id, end = "")
    preParse(Tree[u].left)
    preParse(Tree[u].right)
    
def inParse(u):
    if u == null:
        return
    inParse(Tree[u].left)
    print(" ", end = "")
    print(Tree[u].id, end = "")
    inParse(Tree[u].right)
    
def postParse(u):
    if u == null:
        return
    postParse(Tree[u].left)
    postParse(Tree[u].right)
    print(" ", end = "")
    print(Tree[u].id, end = "")


Tree = []
root = 0

n = int(input())
for i in range(n):
    Tree.append(Node())
    
for i in range(n):
    tmp = list(map(int, input().split()))
    
    Tree[tmp[0]].id = tmp[0]
    
    if tmp[1] != -1:
        Tree[tmp[0]].left = tmp[1]
        Tree[tmp[1]].parent = tmp[0]
    if tmp[2] != -1:
        Tree[tmp[0]].right = tmp[2]
        Tree[tmp[2]].parent = tmp[0]

for i in range(n):
    if Tree[i].parent == null:
        root = i
        break

print("Preorder\n", end = "")
preParse(root)
print("\nInorder")
inParse(root)
print("\nPostorder")
postParse(root)
print("")

Solution (Python):
N = int(input())
childs = [[] for _ in range(N)]
parent = [-1 for _ in range(N)]
for _ in range(N):
    i, l, r = map(int, input().split())
    childs[i].extend([l, r])
    for child in [l, r]:
        if child != -1:
            parent[child] = i

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


def dfs(cur):
    preorder.append(cur)
    [left, right] = childs[cur]
    if left != -1:
        dfs(left)
    inorder.append(cur)
    if right != -1:
        dfs(right)
    postorder.append(cur)


root = 0
while root < N:
    if parent[root] == -1:
        break
    else:
        root += 1
dfs(root)


print('Preorder')
print(' ' + ' '.join(map(str, preorder)))
print('Inorder')
print(' ' + ' '.join(map(str, inorder)))
print('Postorder')
print(' ' + ' '.join(map(str, postorder)))

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

def preorder(tree, root):
    if root == -1:
        pass
    else:
        print(' %d' % root, end='')
        preorder(tree, tree[root].left)
        preorder(tree, tree[root].right)

def inorder(tree, root):
    if root == -1:
        pass
    else:
        inorder(tree, tree[root].left)
        print(' %d' % root, end='')
        inorder(tree, tree[root].right)

def postorder(tree, root):
    if root == -1:
        pass
    else:
        postorder(tree, tree[root].left)
        postorder(tree, tree[root].right)
        print(' %d' % root, end='')

if __name__ == '__main__':
    n = int(input())
    tree = {}
    root = -1
    for _ in range(n):
        datas = [int(num) for num in input().split(' ')]
        nodeid = datas[0]
        if nodeid not in tree.keys():
            tree[nodeid] = Node(nodeid)
        tree[nodeid].left = left = int(datas[1])
        tree[nodeid].right = right = int(datas[2])
        if left != -1:
            if left not in tree.keys():
                tree[left] = Node(left)
            tree[left].parent = nodeid
        if right != -1:
            if right not in tree.keys():
                tree[right] = Node(right)
            tree[right].parent = nodeid

    for i in range(n):
        if tree[i].parent == -1:
            
            root = i
            break
            
    print('Preorder')
    preorder(tree, root)
    print()

    print('Inorder')
    inorder(tree, root)
    print()

    print('Postorder')
    postorder(tree, root)
    print()

Solution (Python):

N = int(input())

preorder_list = []
inorder_list = []
postorder_list = []

rooted_tree = [{} for i in range(N)]
for _ in range(N):
    row = input()
    id, left, right = list(map(int, row.split()))
    rooted_tree[id]["id"] = id
    rooted_tree[id]["right"] = right
    rooted_tree[id]["left"] = left
    
    if left > -1:
        left_child_id = left
        rooted_tree[left_child_id]["parent"] = id
    if right > -1:
        right_child_id = right
        rooted_tree[right_child_id]["parent"] = id
        
def preParse(node):
    preorder_list.append(node["id"])
    if node["left"] != -1:
        preParse(rooted_tree[node["left"]])
    if node["right"] != -1:
        preParse(rooted_tree[node["right"]])
    
def inParse(node):
    if node["left"] != -1:
        inParse(rooted_tree[node["left"]])
    inorder_list.append(node["id"])
    if node["right"] != -1:
        inParse(rooted_tree[node["right"]])
    
def postParse(node):
    if node["left"] != -1:
        postParse(rooted_tree[node["left"]])
    if node["right"] != -1:
        postParse(rooted_tree[node["right"]])
    postorder_list.append(node["id"])
    
def get_parent(node):
    parent = -1
    if "parent" in node:
        return node["parent"]
    return parent

for node in rooted_tree:
    if get_parent(node) == -1:
        root_id = node["id"]
        break

print("Preorder")
preParse(rooted_tree[root_id])
print(" "+" ".join(map(str, preorder_list)))

print("Inorder")
inParse(rooted_tree[root_id])

print(" "+" ".join(map(str, inorder_list)))
print("Postorder")
postParse(rooted_tree[root_id])

print(" "+" ".join(map(str, postorder_list)))

Solution (Python):
def prePhase(u):
    left,right=T[u]
    if u==-1:return
    print(" {}".format(u), end="")
    prePhase(left)
    prePhase(right)


def inPhase(u):
    left,right=T[u]
    if u==-1:return
    inPhase(left)
    print(" {}".format(u), end="")
    inPhase(right)


def postPhase(u):
    left,right=T[u]
    if u==-1:return
    postPhase(left)
    postPhase(right)
    print(" {}".format(u), end="")


n=int(input())
A=sorted([list(map(int,input().split())) for i in range(n)])
T=[]
top=[i for i in range(n)]
for i in range(n):
    B=A[i]
    node,left,right=B[0],B[1],B[2]
    if left!=-1:top.remove(left)
    if right!=-1:top.remove(right)
    T.append([left,right])
top=top[0]

print("Preorder")
prePhase(top)
print()
print("Inorder")
inPhase(top)
print()
print("Postorder")
postPhase(top)
print()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u):
        lu, ru = chi[u]
        pre.append(u)
        if lu != -1: dfs(lu)
        ino.append(u)
        if ru != -1: dfs(ru)
        pos.append(u)

    n = int(input())
    par = [-1] * n
    chi = [[] for _ in range(n)]
    for _ in range(n):
        u, l, r = map(int, input().split())
        if l != -1: par[l] = u
        if r != -1: par[r] = u
        chi[u] += [l]
        chi[u] += [r]

    root = par.index(-1)
    pre = []
    ino = []
    pos = []
    dfs(root)

    print("Preorder")
    print("", *pre)
    print("Inorder")
    print("", *ino)
    print("Postorder")
    print("", *pos)

main()