Given a preOrder and inOrder traversal of a binary tree your task is to print the postOrder traversal of the tree .You are required to complete the function printPostOrder which prints the node of the tree in post order fashion . You should not read any input from stdin/console. There are multiple test cases. For each test case, this method will be called individually.
Example 1:
Input
6
4 2 5 1 3 6
1 2 4 5 3 6
Output 4  5  2  6  3 1
Input Format:
The task is to complete the function printPostOrder which takes 3 argument, the first being the array of inOrder Traversal of the tree (in) , the second beeing the preOrder traversal of the tree (pre) and third being the no of nodes of the Tree (N).
There are multiple test cases. For each test case, this method will be called individually.
Output Format:
The function should print the PostOrder traversal of the binary tree separated by space.
Your Task:
Complete the function printPostOrder.
Constraints:
1 <=T<= 30
1 <=Number of nodes<= 100
1 <=Data of a node<= 1000
Note: The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: # Your task is to complete this function

# Function should print postorder traversal of Tree

def printPostOrder(inorder, preorder, n):

    # Code here



Solutions:
def printPostOrder(inorder, preorder, n):

	def solve(inorder, preorder, ans):
		if len(inorder) == 0:
			return
		if len(inorder) == 1:
			ans.append(inorder[0])
			return
		n = preorder[0]
		nidx = inorder.index(n)
		(l_in, r_in) = (inorder[:nidx], inorder[nidx + 1:])
		(l_p, r_p) = (preorder[1:nidx + 1], preorder[nidx + 1:])
		solve(l_in, l_p, ans)
		solve(r_in, r_p, ans)
		ans.append(n)
	ans = []
	solve(inorder, preorder, ans)
	for each in ans:
		print(each, end=' ')


def printPostOrder(inorder, preorder, n):
	root = search(inorder, preorder[0], n)
	if root != 0:
		printPostOrder(inorder, preorder[1:n], root)
	if root != n - 1:
		printPostOrder(inorder[root + 1:n], preorder[root + 1:n], n - root - 1)
	print(preorder[0], end=' ')

def search(arr, x, n):
	for i in range(0, n):
		if arr[i] == x:
			return i
	return -1


class TreeNode:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None

def printPostOrder(inorder, preorder, n):

	def maketree(inorder, preorder):
		if not inorder or not preorder:
			return None
		root = TreeNode(preorder[0])
		ind = inorder.index(preorder[0])
		root.left = maketree(inorder[:ind], preorder[1:ind + 1])
		root.right = maketree(inorder[ind + 1:], preorder[ind + 1:])
		return root

	def postorder(node):
		if not node:
			return
		postorder(node.left)
		postorder(node.right)
		print(node.data, end=' ')
	node = maketree(inorder, preorder)
	postorder(node)


def search(arr, x, n):
	for i in range(n):
		if arr[i] == x:
			return i
	return -1

def printPostOrder(In, pre, n):
	root = search(In, pre[0], n)
	if root != 0:
		printPostOrder(In, pre[1:n], root)
	if root != n - 1:
		printPostOrder(In[root + 1:n], pre[root + 1:n], n - root - 1)
	print(pre[0], end=' ')


def printPostOrder(inorder, preorder, n):
	h = {}
	for j in range(0, len(inorder)):
		h[inorder[j]] = j
	global ans
	global ind
	ans = []
	ind = -1

	def cal(arr, l, r):
		global ans
		global ind
		if l <= r:
			tempi = ind + 1
			vt = h[preorder[tempi]]
			ind += 1
			cal(arr, l, vt - 1)
			cal(arr, vt + 1, r)
			print(preorder[tempi], end=' ')
	cal(inorder, 0, len(inorder) - 1)


class Node:

	def __init__(self, data):
		self.right = None
		self.left = None
		self.data = data

def printPostOrder(inorder, preorder, n):
	p = 0

	def helper(start, stop):
		nonlocal p
		if start >= stop:
			return None
		cur = Node(preorder[p])
		for i in range(start, stop):
			if inorder[i] == preorder[p]:
				p += 1
				cur.left = helper(start, i)
				cur.right = helper(i + 1, stop)
				break
		return cur
	tree = helper(0, n)

	def postOrder(root):
		if root == None:
			return
		postOrder(root.left)
		postOrder(root.right)
		print(root.data, end=' ')
	postOrder(tree)
	return


def printPostOrder(inorder, preorder, n):

	def post(d1, inord, pre, sin, ein, spre):
		if sin > ein:
			return
		idx = d1[pre[spre]]
		lcnt = idx - sin
		rcnt = ein - idx
		post(d1, inord, pre, sin, idx - 1, spre + 1)
		post(d1, inord, pre, idx + 1, ein, spre + lcnt + 1)
		print(pre[spre], end=' ')
	d1 = {}
	for i in range(n):
		d1[inorder[i]] = i
	post(d1, inorder, preorder, 0, n - 1, 0)


def printPostorder(start, end, preorder, pIndex, dict):
	if start > end:
		return pIndex
	value = preorder[pIndex]
	pIndex = pIndex + 1
	if start == end:
		print(value, end=' ')
		return pIndex
	i = dict[value]
	pIndex = printPostorder(start, i - 1, preorder, pIndex, dict)
	pIndex = printPostorder(i + 1, end, preorder, pIndex, dict)
	print(value, end=' ')
	return pIndex

def findPostorder(inorder, preorder):
	dict = {}
	for (i, e) in enumerate(inorder):
		dict[e] = i
	pIndex = 0
	printPostorder(0, len(inorder) - 1, preorder, pIndex, dict)

def printPostOrder(inorder, preorder, n):
	findPostorder(inorder, preorder)


def search(arr, x, n):
	for i in range(n):
		if arr[i] == x:
			return i
	return -1

def printPostOrder(In, pre, n):
	try:
		idx = In.index(pre[0])
	except:
		idx = -1
	if idx != 0:
		printPostOrder(In[:idx], pre[1:n], idx)
	if idx != n - 1:
		printPostOrder(In[idx + 1:n], pre[idx + 1:n], n - idx - 1)
	print(pre[0], end=' ')


class Node:

	def __init__(self, data):
		self.data = data
		self.left = self.right = None

def post(Tree):
	if Tree != None:
		post(Tree.left)
		post(Tree.right)
		print(Tree.data, end=' ')

def printPostOrder(inorder, preorder, n):
	order = {inorder[i]: i for i in range(len(inorder))}
	head = Node(preorder[0])
	stack = [head]
	for i in range(1, len(preorder)):
		if order[preorder[i]] < order[stack[-1].data]:
			stack[-1].left = Node(preorder[i])
			stack.append(stack[-1].left)
		else:
			kicked = stack[-1]
			while len(stack) > 0 and order[preorder[i]] > order[stack[-1].data]:
				kicked = stack.pop()
			kicked.right = Node(preorder[i])
			stack.append(kicked.right)
	result = []
	post(head)


class BinaryTreeNode:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

def PostorderTraversal(root):
	if root == None:
		return None
	else:
		PostorderTraversal(root.left)
		PostorderTraversal(root.right)
		print(root.data, end=' ')

def printPostOrder(inorder, preorder, n):
	if len(preorder) == 0:
		return None
	else:
		root = BinaryTreeNode(preorder[0])
		index_root = inorder.index(preorder[0])
		left_inorder = inorder[:index_root]
		right_inorder = inorder[index_root + 1:]
		left_preorder = preorder[1:len(left_inorder) + 1]
		right_preorder = preorder[len(left_inorder) + 1:]
		left_subtree = printPostOrder(left_inorder, left_preorder, n)
		right_subtree = printPostOrder(right_inorder, right_preorder, n)
		root.left = left_subtree
		root.right = right_subtree
		PostorderTraversal(root)


def printPostOrder(In, pre, n):
	val = pre[0]
	root = None
	for i in range(n):
		if In[i] == val:
			root = i
			break
	if root != 0:
		printPostOrder(In, pre[1:n], root)
	if root != n - 1:
		printPostOrder(In[root + 1:n], pre[root + 1:n], n - root - 1)
	print(pre[0], end=' ')


def printPostOrder(inorder, preorder, n):
	root = inorder.index(preorder[0])
	if root != 0:
		printPostOrder(inorder, preorder[1:root + 1], root)
	if root != n - 1:
		printPostOrder(inorder[root + 1:n], preorder[root + 1:n], n - root - 1)
	print(preorder[0], end=' ')


class Node:

	def __init__(self, data):
		self.left = None
		self.right = None
		self.data = data

def searchIndex(inorder, el):
	for i in range(len(inorder)):
		if inorder[i] == el:
			return i

def printPostOrder(inorder, preorder, n):
	if len(preorder) == 0:
		return
	if len(preorder) == 1:
		print(preorder[0], end=' ')
		return
	root_idx = searchIndex(inorder, preorder[0])
	printPostOrder(inorder[:root_idx], preorder[1:root_idx + 1], n)
	printPostOrder(inorder[root_idx + 1:], preorder[root_idx + 1:], n)
	print(preorder[0], end=' ')


def printPostOrder(In, pre, n):
	if not In or not pre:
		return None
	root = In.index(pre[0])
	printPostOrder(In[:root], pre[1:root + 1], n)
	printPostOrder(In[root + 1:], pre[root + 1:], n)
	print(pre[0], end=' ')


def printPostOrder(inorder, pre, n):
	if len(pre) < 1:
		return
	if len(pre) == 1:
		print(pre[0], end=' ')
		return
	root = pre[0]
	for i in range(len(inorder)):
		if inorder[i] == root:
			index = i
	printPostOrder(inorder[:index], pre[1:index + 1], n)
	printPostOrder(inorder[index + 1:], pre[index + 1:], n)
	print(root, end=' ')


class Node:

	def __init__(self=None):
		self.left = None
		self.right = None
		self.value = None

def search_split_index(root, inorder):
	for x in range(len(inorder)):
		if inorder[x] == root:
			return x
	return -1

def buildTree(inorder, preorder):
	if len(preorder) == 0:
		return None
	root_split_index = search_split_index(preorder[0], inorder)
	buildTree(inorder[0:root_split_index], preorder[1:root_split_index + 1])
	buildTree(inorder[root_split_index + 1:], preorder[root_split_index + 1:])
	print(preorder[0], end=' ')

def printPostOrder(inorder, preorder, n):
	root_node = buildTree(inorder, preorder)


class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

def find(inorder, key):
	for i in range(len(inorder)):
		if inorder[i] == key:
			return i

def postorder(head):
	if not head:
		return
	postorder(head.left)
	postorder(head.right)
	print(head.data, end=' ')

def base(inorder, preorder, n):
	if len(inorder) <= 0:
		return
	new_Node = Node(preorder[0])
	root = find(inorder, preorder[0])
	new_Node.left = base(inorder[0:root], preorder[1:n + 1], n)
	new_Node.right = base(inorder[root + 1:n + 1], preorder[root + 1:n + 1], n)
	return new_Node

def printPostOrder(inorder, preorder, n):
	head = base(inorder, preorder, n)
	postorder(head)


def search(arr, pre, n):
	for i in range(n):
		if arr[i] == pre:
			return i
	return -1

def printPostOrder(inorder, preorder, n):
	s = search(inorder, preorder[0], n)
	if s != 0:
		printPostOrder(inorder, preorder[1:n], s)
	if s != n - 1:
		printPostOrder(inorder[s + 1:n], preorder[s + 1:n], n - s - 1)
	print(preorder[0], end=' ')


class BinaryTreeNode:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None
import sys
sys.setrecursionlimit(10 ** 6)

def printPostOrder(inorder, preorder, n):
	if len(inorder) == 0:
		return None
	rootdata = preorder[0]
	root = BinaryTreeNode(rootdata)
	rootindex = -1
	for i in range(len(inorder)):
		if rootdata == inorder[i]:
			rootindex = i
			break
	if rootindex == -1:
		return None
	leftinorder = inorder[:rootindex]
	rightinorder = inorder[rootindex + 1:]
	lenpreorder = len(leftinorder)
	leftpreorder = preorder[1:lenpreorder + 1]
	rightpreorder = preorder[lenpreorder + 1:]
	leftchild = printPostOrder(leftinorder, leftpreorder, n)
	rightchild = printPostOrder(rightinorder, rightpreorder, n)
	root.left = leftchild
	root.right = rightchild
	print(root.data, end=' ')


class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None

def build_tree(inorder, preorder):
	if len(inorder) == 0:
		return None
	data = preorder[0]
	position = inorder.index(data)
	left_inorder = inorder[:position]
	right_inorder = inorder[position + 1:]
	root = Node(data)
	root.left = build_tree(left_inorder, preorder[1:len(left_inorder) + 1])
	root.right = build_tree(right_inorder, preorder[1 + len(left_inorder):])
	return root

def postOrder(root):
	if root is None:
		return []
	left_tree = postOrder(root.left)
	right_tree = postOrder(root.right)
	return left_tree + right_tree + [root.data]

def printPostOrder(inorder, preorder, n):
	binary_tree = build_tree(inorder, preorder)
	post_traversal = postOrder(binary_tree)
	print_string = ' '.join([str(x) for x in post_traversal])
	print(print_string, end='')
	return print_string
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		ino = list(map(int, input().strip().split()))
		pre = list(map(int, input().strip().split()))
		printPostOrder(ino, pre, n)
		print('')


def search(arr, x, n):
	for i in range(n):
		if arr[i] == x:
			return i
	return -1

def printPostOrder(inorder, preorder, n):
	root = search(inorder, preorder[0], n)
	if root != 0:
		printPostOrder(inorder, preorder[1:n], root)
	if root != n - 1:
		printPostOrder(inorder[root + 1:n], preorder[root + 1:n], n - root - 1)
	print(preorder[0], end=' ')
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		ino = list(map(int, input().strip().split()))
		pre = list(map(int, input().strip().split()))
		printPostOrder(ino, pre, n)
		print('')


class Node:

	def __init__(self, data):
		self.left = None
		self.right = None
		self.data = data

def pp(i, p, r):
	if len(p) < 1:
		return
	x = p[0]
	y = i.index(x)
	r = Node(x)
	r.left = pp(i[:y], p[1:y + 1], r.left)
	r.right = pp(i[y + 1:], p[y + 1:], r.right)
	return r

def intt(r):
	if not r:
		return
	intt(r.left)
	intt(r.right)
	print(r.data, end=' ')

def printPostOrder(i, p, n):
	r = Node(0)
	r = pp(i, p, r)
	intt(r)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		ino = list(map(int, input().strip().split()))
		pre = list(map(int, input().strip().split()))
		printPostOrder(ino, pre, n)
		print('')


def pp(i, p):
	if len(p) < 1:
		return
	y = i.index(p[0])
	pp(i[:y], p[1:y + 1])
	pp(i[y + 1:], p[y + 1:])
	print(p[0], end=' ')

def printPostOrder(i, p, n):
	r = pp(i, p)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		ino = list(map(int, input().strip().split()))
		pre = list(map(int, input().strip().split()))
		printPostOrder(ino, pre, n)
		print('')


def helper(inorder, instrt, inend, preorder, prestrt, preend, di):
	if prestrt > preend or instrt > inend:
		return
	rindex = di[preorder[prestrt]]
	helper(inorder, instrt, rindex - 1, preorder, prestrt + 1, prestrt + rindex - instrt, di)
	helper(inorder, rindex + 1, inend, preorder, prestrt + rindex - instrt + 1, preend, di)
	print(inorder[rindex], end=' ')

def printPostOrder(inorder, preorder, n):
	di = {}
	for i in range(n):
		di[inorder[i]] = i
	helper(inorder, 0, n - 1, preorder, 0, n - 1, di)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		ino = list(map(int, input().strip().split()))
		pre = list(map(int, input().strip().split()))
		printPostOrder(ino, pre, n)
		print('')


def printPostOrder(inorder, preorder, n):
	ind = inorder.index(preorder[0])
	if ind != 0:
		printPostOrder(inorder[:ind], preorder[1:ind + 1], ind)
	if ind != n - 1:
		printPostOrder(inorder[ind + 1:], preorder[ind + 1:], n - ind - 1)
	print(preorder[0], end=' ')


def printPostOrder(inorder, preorder, n):
	dct = {}
	for i in range(n):
		dct[inorder[i]] = i
	ans = []

	def helper(ino, pre, s, e, ans):
		if s > e:
			return
		if len(pre) == 1:
			ans.append(pre[0])
			return
		if len(pre) == 0:
			return
		node = pre.pop(0)
		ans.append(node)
		ind = dct[node]
		lpre = pre[:ind - s]
		rpre = pre[ind - s:]
		helper(ino, rpre, ind + 1, e, ans)
		helper(ino, lpre, s, ind - 1, ans)
	helper(inorder, preorder, 0, n - 1, ans)
	ans.reverse()
	for i in ans:
		print(i, end=' ')


def printPostOrder(inorder, preorder, n):
	indx = inorder.index(preorder[0])
	if indx != 0:
		printPostOrder(inorder[0:indx], preorder[1:indx + 1], indx)
	if indx != n - 1:
		printPostOrder(inorder[indx + 1:n], preorder[indx + 1:n], n - indx - 1)
	print(preorder[0], end=' ')


def post(inorder, preorder, n):
	dict = {}
	for i in range(n):
		dict[inorder[i]] = i
	rootIndex = dict[preorder[0]]
	if rootIndex != 0:
		post(inorder[0:rootIndex], preorder[1:rootIndex + 1], rootIndex)
	if rootIndex != n - 1:
		post(inorder[rootIndex + 1:n], preorder[rootIndex + 1:n], n - rootIndex - 1)
	print(preorder[0], end=' ')
	return

def printPostOrder(inorder, preorder, n):
	post(inorder, preorder, n)
	return


def printPostOrder(inorder, preorder, n):
	if n == 0:
		return
	root = preorder[0]
	root_index_inorder = inorder.index(root)
	total_l = len(inorder)
	if root_index_inorder != 0:
		printPostOrder(inorder[0:root_index_inorder], preorder[1:root_index_inorder + 1], root_index_inorder)
	if root_index_inorder != total_l - 1:
		printPostOrder(inorder[root_index_inorder + 1:total_l], preorder[root_index_inorder + 1:total_l], total_l - (root_index_inorder + 1))
	print(root, end=' ')


def s(a, x, n):
	for i in range(n):
		if a[i] == x:
			return i
	return -1

def printPostOrder(inorder, preorder, n):
	index = s(inorder, preorder[0], n)
	if index != 0:
		printPostOrder(inorder, preorder[1:n], index)
	if index != n - 1:
		printPostOrder(inorder[index + 1:n], preorder[index + 1:n], n - index - 1)
	print(preorder[0], end=' ')


def postorder(ino, preo, l, h):
	if l == h:
		print(ino[0], end=' ')
		return
	if l > h:
		return
	for i in range(0, h + 1):
		if preo[0] == ino[i]:
			break
	postorder(ino[0:i], preo[1:i + 1], 0, i - 1)
	postorder(ino[i + 1:h + 1], preo[i + 1:h + 1], 0, h - i - 1)
	print(preo[0], end=' ')

def printPostOrder(inorder, preorder, n):
	postorder(inorder, preorder, 0, n - 1)


def printPostOrder(inorder, preorder, n):

	def array(left, right):
		global PreIdx, d
		if left > right:
			return
		idx = d[preorder[PreIdx]]
		PreIdx += 1
		array(left, idx - 1)
		array(idx + 1, right)
		print(inorder[idx], end=' ')
	global PreIdx, d
	d = {}
	PreIdx = 0
	for (i, j) in enumerate(inorder):
		d[j] = i
	array(0, len(inorder) - 1)


def printPostOrder(inorder, preorder, n):
	if preorder:
		root = preorder[0]
		root_idx = inorder.index(root)
		inorder_left = inorder[:root_idx]
		inorder_right = inorder[root_idx + 1:]
		left_n = len(inorder_left)
		right_n = len(inorder_right)
		preorder_left = preorder[1:left_n + 1]
		preorder_right = preorder[left_n + 1:]
		printPostOrder(inorder_left, preorder_left, left_n)
		printPostOrder(inorder_right, preorder_right, right_n)
		print(root, end=' ')


def printPostOrder(inorder, preorder, n):
	final = []

	def printPostOrderUtil(inorder, preorder):
		if preorder == []:
			return
		inorder_index = inorder.index(preorder[0])
		root = preorder[0]
		printPostOrderUtil(inorder[:inorder_index], preorder[1:inorder_index + 1])
		printPostOrderUtil(inorder[inorder_index + 1:], preorder[1 + inorder_index:])
		print(root, end=' ')
	printPostOrderUtil(inorder, preorder)


def printPostOrder(inorder, preorder, n):
	x = preorder[0]
	p = -1
	for i in range(n):
		if inorder[i] == x:
			p = i
			break
	if p != 0:
		printPostOrder(inorder, preorder[1:], p)
	if p != n - 1:
		printPostOrder(inorder[p + 1:], preorder[p + 1:], n - p - 1)
	print(x, end=' ')


def printPostOrder(inorder, preorder, n, i=0):
	if len(inorder) == 1:
		return inorder[0]
	elif len(inorder) == 0:
		return
	else:
		root = preorder[i]
		while root not in inorder:
			i = i + 1
			root = preorder[i]
		left = printPostOrder(inorder[:inorder.index(root)], preorder, n, i + 1)
		if left:
			preorder.remove(left)
			print(left, end=' ')
		right = printPostOrder(inorder[inorder.index(root) + 1:], preorder, n, i + 1)
		if right:
			preorder.remove(right)
			print(right, end=' ')
		print(root, end=' ')


def printPostOrder(inorder, preorder, n):
	output = []

	def serach(arr, root):
		i = 0
		for a in arr:
			if a == root:
				return i
			i += 1
		return -1

	def postorder(inorder, preorder, n):
		ind_root = serach(inorder, preorder[0])
		if ind_root != 0:
			postorder(inorder[:ind_root], preorder[1:], ind_root)
		if ind_root != n - 1:
			postorder(inorder[ind_root + 1:n], preorder[ind_root + 1:n], n - ind_root - 1)
		print(preorder[0], end=' ')
	postorder(inorder, preorder, n)


def printPostOrder(inorder, preorder, n):
	if not preorder:
		return
	node_val = preorder.pop(0)
	index = inorder.index(node_val)
	right_inorder = inorder[index + 1:]
	left_inorder = inorder[:index]
	left_inorder_vals = set(left_inorder)
	right_inorder_vals = set(right_inorder)
	left_preorder = []
	right_preorder = []
	for i in preorder:
		if i in left_inorder_vals:
			left_preorder.append(i)
		else:
			right_preorder.append(i)
	printPostOrder(left_inorder, left_preorder, n)
	printPostOrder(right_inorder, right_preorder, n)
	print(node_val, end=' ')


hm = {}
preIndex = 0

def printPost(inn, pre, inStrt, inEnd):
	global preIndex, hm
	if inStrt > inEnd or preIndex >= n:
		return
	inIndex = hm[pre[preIndex]]
	preIndex += 1
	printPost(inn, pre, inStrt, inIndex - 1)
	printPost(inn, pre, inIndex + 1, inEnd)
	print(inn[inIndex], end=' ')

def printPostOrder(inorder, preorder, n):
	global hm, preIndex
	hm = {}
	preIndex = 0
	for i in range(n):
		hm[inorder[i]] = i
	printPost(inorder, preorder, 0, n - 1)


def printPostOrder(inorder, preorder, n):
	li = []
	a = [0]
	m = max(preorder)
	global hm
	hm = {}
	for i in range(len(inorder)):
		hm[inorder[i]] = i
	util(inorder, preorder, a, 0, n - 1, li)

def util(ino, pre, a, l, r, li):
	if l > r:
		return
	ind = hm[pre[a[0]]]
	a[0] += 1
	util(ino, pre, a, l, ind - 1, li)
	util(ino, pre, a, ind + 1, r, li)
	print(ino[ind], end=' ')


def printPostOrder(inorder, preorder, n):
	if inorder:
		idx = inorder.index(preorder.pop(0))
		temp = inorder[idx]
		printPostOrder(inorder[:idx], preorder, n)
		printPostOrder(inorder[idx + 1:], preorder, n)
		print(temp, end=' ')
		return


preInd = 0

def rec(hm, ino, pre, st, end):
	global preInd
	if st > end:
		return
	(pos, preInd) = (hm[pre[preInd]], preInd + 1)
	rec(hm, ino, pre, st, pos - 1)
	rec(hm, ino, pre, pos + 1, end)
	print(ino[pos], end=' ')

def printPostOrder(ino, pre, n):
	global preInd
	hm = {}
	for (i, j) in enumerate(ino):
		hm[j] = i
	rec(hm, ino, pre, 0, n - 1)
	(hm, preInd) = ({}, 0)


def printPostOrder(inorder, preorder, n):
	if len(inorder) != 0 and len(preorder) != 0:
		rootOfTheTree = preorder[0]
		iroot = inorder.index(rootOfTheTree)
		inorderOfLeftSubTree = inorder[0:iroot]
		inorderOfRightSubTree = inorder[iroot + 1:]
		nLeftSubTree = len(inorderOfLeftSubTree)
		nRightSubTree = len(inorderOfRightSubTree)
		preorderOfLeftSubTree = preorder[1:1 + nLeftSubTree]
		preorderOfRightSubTree = preorder[1 + nLeftSubTree:]
		printPostOrder(inorderOfLeftSubTree, preorderOfLeftSubTree, nLeftSubTree)
		printPostOrder(inorderOfRightSubTree, preorderOfRightSubTree, nRightSubTree)
		print(rootOfTheTree, end=' ')


def printPostOrder(inn, pre, n):
	if inn:
		ind = inn.index(pre.pop(0))
		temp = inn[ind]
		printPostOrder(inn[0:ind], pre, n)
		printPostOrder(inn[ind + 1:], pre, n)
		print(temp, end=' ')
		return


(preIndex, hm) = (0, {})

def helper(inn, pre, inStrt, inEnd):
	global preIndex, hm
	if inStrt > inEnd:
		return
	inIndex = hm[pre[preIndex]]
	preIndex += 1
	helper(inn, pre, inStrt, inIndex - 1)
	helper(inn, pre, inIndex + 1, inEnd)
	print(inn[inIndex], end=' ')

def printPostOrder(inn, pre, n):
	global preIndex, hm
	for i in range(n):
		hm[inn[i]] = i
	helper(inn, pre, 0, n - 1)
	(preIndex, hm) = (0, {})


def printPostOrder(inorder, preorder, n):
	if not inorder:
		return
	root = inorder.index(preorder[0])
	x = preorder.pop(0)
	printPostOrder(inorder[:root], preorder, root)
	printPostOrder(inorder[root + 1:], preorder, n - int(root) - 1)
	print(x, end=' ')


class Node:

	def __init__(self, key):
		self.left = None
		self.right = None
		self.key = key

def postorder(root):
	if root is None:
		return
	postorder(root.left)
	postorder(root.right)
	print(root.key, end=' ')

def builttree(preo, pst, ped, ino, ist, ied, dict1):
	if pst > ped or ist > ied:
		return
	root = Node(preo[pst])
	inRoot = dict1[root.key]
	numleft = inRoot - ist
	root.left = builttree(preo, pst + 1, pst + numleft, ino, ist, inRoot - 1, dict1)
	root.right = builttree(preo, pst + numleft + 1, ped, ino, inRoot + 1, ied, dict1)
	return root

def printPostOrder(inorder, preorder, n):
	dict1 = {}
	for i in range(n):
		dict1[inorder[i]] = i
	root = Node(None)
	root = builttree(preorder, 0, n - 1, inorder, 0, n - 1, dict1)
	postorder(root)


def fun(ino, pre, n):
	if n > 0:
		if n == 1:
			print(pre[0], end=' ')
		else:
			for i in range(n):
				if pre[0] == ino[i]:
					fun(ino[0:i], pre[1:i + 1], i)
					fun(ino[i + 1:n], pre[i + 1:n], n - i - 1)
					print(pre[0], end=' ')
					break

def printPostOrder(inorder, preorder, n):
	for i in range(n):
		if preorder[0] == inorder[i]:
			fun(inorder[0:i], preorder[1:i + 1], i)
			fun(inorder[i + 1:n], preorder[i + 1:n], n - i - 1)
			print(preorder[0], end=' ')
			break


def printPostOrder(inorder, preorder, n):
	m = {}
	index = 0
	for i in range(n):
		m[inorder[i]] = i

	def post(s, e):
		nonlocal index
		if s > e:
			return
		part = m[preorder[index]]
		index += 1
		post(s, part - 1)
		post(part + 1, e)
		print(inorder[part], end=' ')
	post(0, n - 1)


def search(ino, x):
	n = len(ino)
	for i in range(n):
		if ino[i] == x:
			return i

def printPostOrder(ino, pre, n):
	root = search(ino, pre[0])
	s = []
	if root != 0:
		printPostOrder(ino, pre[1:n], root)
	if root != n - 1:
		printPostOrder(ino[root + 1:n], pre[root + 1:n], n - root - 1)
	print(pre[0], end=' ')


class Node:

	def __init__(self, val):
		self.left = None
		self.right = None
		self.data = val

def createTree(inorder, preorder):
	if not inorder or not preorder:
		return None
	root = Node(preorder[0])
	if len(inorder) == 1:
		return root
	for i in range(len(inorder)):
		if inorder[i] == root.data:
			root.left = createTree(inorder[:i], preorder[1:i + 1])
			root.right = createTree(inorder[i + 1:], preorder[i + 1:])
	return root

def postOrder(root):
	if root is None:
		return
	postOrder(root.left)
	postOrder(root.right)
	print(root.data, end=' ')

def printPostOrder(inorder, preorder, n):
	root = createTree(inorder, preorder)
	postOrder(root)


def printPostOrder(inorder, preorder, n):
	if n == 0:
		return
	if n == 1:
		print(inorder[0], end=' ')
	else:
		rootdata = preorder[0]
		ind = inorder.index(rootdata)
		leftinorder = inorder[:ind]
		lenleftinorder = len(leftinorder)
		leftpreorder = preorder[1:lenleftinorder + 1]
		rightinorder = inorder[ind + 1:]
		lenrightinorder = len(rightinorder)
		rightpreorder = preorder[lenleftinorder + 1:]
		printPostOrder(leftinorder, leftpreorder, lenleftinorder)
		printPostOrder(rightinorder, rightpreorder, lenrightinorder)
		print(inorder[ind], end=' ')


def printPostOrder(inorder, preorder, n):
	root = getElement(inorder, preorder[0], n)
	if root != 0:
		printPostOrder(inorder, preorder[1:n], root)
	if root != n - 1:
		printPostOrder(inorder[root + 1:], preorder[root + 1:], n - root - 1)
	print(preorder[0], end=' ')

def getElement(inorder, preorder, n):
	for i in range(n):
		if inorder[i] == preorder:
			return i
	return -1


def printPostOrder(inorder, preorder, n):
	search = {}
	for i in range(n):
		search[inorder[i]] = i
	getPost(inorder, preorder, search, 0, n - 1, 0)

def getPost(inorder, preorder, search, start, end, i):
	g = search[preorder[i]]
	if i == len(inorder) or g > end or g < start:
		return i
	elif start == end and end == g:
		pass
	elif g == end:
		i = getPost(inorder, preorder, search, start, g - 1, i + 1)
	elif g == start:
		i = getPost(inorder, preorder, search, g + 1, end, i + 1)
	else:
		i = getPost(inorder, preorder, search, start, g - 1, i + 1)
		i = getPost(inorder, preorder, search, g + 1, end, i + 1)
	print(inorder[g], end=' ')
	return i


def printPostOrder(inorder, preorder, n):
	d = {}
	for i in range(n):
		d[inorder[i]] = i
	ans = []
	ind = 0

	def helper(s, e):
		nonlocal d, ind, ans
		if s > e:
			return
		indindex = d[preorder[ind]]
		ind += 1
		helper(s, indindex - 1)
		helper(indindex + 1, e)
		ans.append(inorder[indindex])
	helper(0, n - 1)
	for i in ans:
		print(i, end=' ')


class Node:

	def __init__(self, data):
		self.left = None
		self.data = data
		self.right = None

def hashh(inorder, n):
	mapp = {}
	for i in range(n):
		mapp[inorder[i]] = i
	return mapp

def printpo(root):
	if root is not None:
		printpo(root.left)
		printpo(root.right)
		print(root.data, end=' ')

def constructBT(ino, inos, inoend, pre, pres, preend, mapp):
	if inos > inoend or pres > preend:
		return
	root = Node(pre[pres])
	idx = mapp[root.data]
	numleft = idx - inos
	root.left = constructBT(ino, inos, idx - 1, pre, pres + 1, pres + numleft, mapp)
	root.right = constructBT(ino, idx + 1, inoend, pre, pres + numleft + 1, preend, mapp)
	return root

def printPostOrder(inorder, preorder, n):
	mapp = hashh(inorder, n)
	root = constructBT(inorder, 0, n - 1, preorder, 0, n - 1, mapp)
	printpo(root)