Given an array arr[] of N nodes representing preorder traversal of some BST. You have to build the exact PostOrder from it's given preorder traversal. 
In Pre-Order traversal, the root node is visited before the left child and right child nodes.
Example 1:
Input:
N = 5
arr[]  = {40,30,35,80,100}
Output: 35 30 100 80 40
Explanation: PreOrder: 40 30 35 80 100
Therefore, the BST will be:
              40
           /      \
         30       80
           \        \   
           35      100
Hence, the postOrder traversal will
be: 35 30 100 80 40
Example 2:
Input:
N = 8
arr[]  = {40,30,32,35,80,90,100,120}
Output: 35 32 30 120 100 90 80 40
Your Task:
You need to complete the given function and return the root of the tree. The driver code will then use this root to print the post order traversal.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 10^{3}
1 <= arr[i] <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3



class Node:



    def __init__(self, data=0):

        self.data = data

        self.left = None

        self.right = None



#Function that constructs BST from its preorder traversal.

def post_order(pre, size) -> Node:

    #code here

Solutions:
class Node:

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

def post_order(pre, size) -> Node:
	i = [0]

	def create(top, bottom):
		if i[0] >= len(pre):
			return None
		node = Node(pre[i[0]])
		if node.data > top or node.data < bottom:
			return None
		i[0] += 1
		node.left = create(node.data, bottom)
		node.right = create(top, node.data)
		return node
	return create(float('inf'), -float('inf'))


class Node:

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

def util(pre, n):
	if n == 0:
		return None
	if n == 1:
		return Node(pre[0])
	rootele = pre[0]
	pre = pre[1:]
	index = 0
	for i in range(n - 1):
		if rootele < pre[i]:
			index = i
			break
	root = Node(rootele)
	root.left = util(pre[:index], len(pre[:index]))
	root.right = util(pre[index:], len(pre[index:]))
	return root

def post_order(pre, size) -> Node:
	return util(pre, size)


import math

class Node:

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

def buildTree(pre, size, ind, mn, mx):
	if ind[0] >= size:
		return None
	key = pre[ind[0]]
	if key < mn[0] or key > mx[0]:
		return None
	root = Node(key)
	ind[0] += 1
	root.left = buildTree(pre, size, ind, mn, [key - 1])
	root.right = buildTree(pre, size, ind, [key + 1], mx)
	return root

def post_order(pre, size) -> Node:
	if pre is None:
		return None
	root = buildTree(pre, size, [0], [-math.inf], [math.inf])
	return root


class Node:

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

def func(a):
	if not a:
		return
	root = Node(a[0])
	i = 1
	while i < len(a) and a[i] < root.data:
		i += 1
	root.left = func(a[1:i])
	root.right = func(a[i:])
	return root

def fun(root, ans):
	if root is None:
		return
	fun(root.left, ans)
	fun(root.right, ans)
	ans.append(root.data)

def post_order(pre, size) -> Node:
	root = func(pre)
	return root


class Node:

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

def binary_search(arr, ele):
	(low, high) = (0, len(arr))
	while low < high:
		mid = (low + high) // 2
		if arr[mid] < ele:
			low = mid + 1
		else:
			high = mid
	return low

def construct_tree(preorder, inorder):
	if len(preorder) == 0:
		return
	rootval = preorder[0]
	root = Node(rootval)
	rootpos = binary_search(inorder, rootval)
	root.left = construct_tree(preorder[1:1 + rootpos], inorder[:rootpos])
	root.right = construct_tree(preorder[1 + rootpos:], inorder[rootpos + 1:])
	return root

def post_order(preorder, size) -> Node:
	inorder = sorted(preorder)
	root = construct_tree(preorder, inorder)
	return root


class Node:

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

def util(pre):
	if len(pre) == 0:
		return None
	rootdata = pre[0]
	pre.pop(0)
	count = 0
	for i in range(len(pre)):
		if rootdata > pre[i]:
			count += 1
		else:
			break
	root = Node(rootdata)
	root.left = util(pre[:count])
	root.right = util(pre[count:])
	return root

def post_order(pre, size) -> Node:
	return util(pre)


class Node:

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

def post_order(pre, size) -> Node:
	global preindex
	preindex = 0
	inorder = []
	for i in pre:
		inorder.append(i)
	inorder.sort()
	root = cons_BST(pre, inorder, 0, size - 1)
	return root

def cons_BST(pre, inorder, ist, ied):
	global preindex
	if ist > ied or preindex >= len(pre):
		return None
	root = Node(pre[preindex])
	index = inorder.index(pre[preindex])
	preindex += 1
	root.left = cons_BST(pre, inorder, ist, index - 1)
	root.right = cons_BST(pre, inorder, index + 1, ied)
	return root


class Node:

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

def post_order(pre, size) -> Node:
	preorder = pre
	inorder = list(sorted(pre))

	def fun(ino, pre):
		if not ino or not pre:
			return None
		root = Node(pre[0])
		mid = ino.index(pre[0])
		root.left = fun(ino[:mid], pre[1:mid + 1])
		root.right = fun(ino[mid + 1:], pre[mid + 1:])
		return root
	return fun(inorder, preorder)


class Node:

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

def post_order(pre, size) -> Node:
	if len(pre) == 0:
		return
	root = Node(pre[0])
	i = 1
	while i < len(pre) and pre[i] < root.data:
		i += 1
	root.left = post_order(pre[1:i], size)
	root.right = post_order(pre[i:], size)
	return root


class Node:

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

def ins(root, ele):
	if root.left == None and ele < root.data:
		root.left = Node(ele)
		return
	if root.right == None and ele > root.data:
		root.right = Node(ele)
		return
	if ele < root.data:
		ins(root.left, ele)
	elif ele > root.data:
		ins(root.right, ele)

def post_order(pre, size) -> Node:
	root = Node(pre[0])
	for i in range(1, size):
		ins(root, pre[i])
	return root


class Node:

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

def post_order(pre, size) -> Node:
	i = 0

	def solve(arr, minn, maxx):
		global i
		if i >= len(arr):
			return None
		elif arr[i] < minn or arr[i] > maxx:
			return None
		root = Node(arr[i])
		i += 1
		root.left = solve(arr, minn, root.data)
		root.right = solve(arr, root.data, maxx)
		return root

	def post_order(pre, size):
		global i
		i = 0
		return solve(pre, -9999999, 9999999)
	return post_order(pre, size)


class Node:

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

def post_order(pre, size) -> Node:

	def insert(root, val):
		if not root:
			return Node(val)
		if val < root.data:
			root.left = insert(root.left, val)
		else:
			root.right = insert(root.right, val)
		return root
	root = None
	for i in pre:
		root = insert(root, i)
	return root


class Node:

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

	def add(self, data):
		if self.data == data:
			return
		if data < self.data:
			if self.left:
				self.left.add(data)
			else:
				self.left = Node(data)
		elif self.right:
			self.right.add(data)
		else:
			self.right = Node(data)

def add(root, data):
	if root.data == data:
		return
	if data < root.data:
		if root.left:
			add(root.left, data)
		else:
			root.left = Node(data)
	elif root.right:
		add(root.right, data)
	else:
		root.right = Node(data)

def post_order(pre, size) -> Node:
	root = Node(pre[0])
	for i in range(1, size):
		add(root, pre[i])
	return root


class Node:

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

def post_order(pre, size) -> Node:

	def fgt(arr):
		for j in range(len(arr)):
			if arr[j] > arr[0]:
				return j
		return len(arr)

	def solve(arr):
		if not arr:
			return None
		root = Node(arr[0])
		indx = fgt(arr)
		root.left = solve(arr[1:indx])
		root.right = solve(arr[indx:])
		return root
	return solve(pre)


class Node:

	def __init__(self, data=0):
		self.data = data
		self.left = None
		self.right = None
INT_MIN = -2 ** 31
INT_MAX = 2 ** 31

def findPostOrderUtil(pre, n, minval, maxval, preIndex):
	if preIndex[0] == n:
		return
	if pre[preIndex[0]] < minval or pre[preIndex[0]] > maxval:
		return
	val = pre[preIndex[0]]
	preIndex[0] += 1
	findPostOrderUtil(pre, n, minval, val, preIndex)
	findPostOrderUtil(pre, n, val, maxval, preIndex)
	print(val, end=' ')

def post_order(pre, size) -> Node:
	preIndex = [0]
	findPostOrderUtil(pre, size, INT_MIN, INT_MAX, preIndex)


class Node:

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

def post_order(pre, size) -> Node:
	root = Node(pre[0])
	for i in range(1, size):
		bst(root, pre[i])
	return root

def postorder(root, res):
	if root:
		postorder(root.left, res)
		postorder(root.right, res)
		res.append(root.data)
	return res

def bst(root, val):
	if not root:
		return Node(val)
	if root.data < val:
		root.right = bst(root.right, val)
	elif root.data > val:
		root.left = bst(root.left, val)
	return root


class Node:

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

def post_order(pre, size) -> Node:
	i = [0]

	def make_bst(pre, ls, rl):
		root = Node(pre[i[0]])
		i[0] = i[0] + 1
		if i[0] < size and pre[i[0]] < root.data and (pre[i[0]] > ls):
			root.left = make_bst(pre, ls, root.data)
		else:
			root.left = None
		if i[0] < size and pre[i[0]] > root.data and (pre[i[0]] < rl):
			root.right = make_bst(pre, root.data, rl)
		else:
			root.right = None
		return root
	r = make_bst(pre, -1, 1000000)
	return r


class Node:

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

def construct(pre, s, e):
	if s > e:
		return None
	if s == e:
		return Node(pre[s])
	j = e + 1
	for i in range(s + 1, e + 1):
		if pre[i] > pre[s]:
			j = i
			break
	node = Node(pre[s])
	node.left = construct(pre, s + 1, j - 1)
	node.right = construct(pre, j, e)
	return node

def post_order(pre, size) -> Node:
	return construct(pre, 0, size - 1)


class Node:

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

def post_order(pre_order, size) -> Node:
	if len(pre_order) <= 0:
		return None
	root = Node(pre_order[0])
	index_for_right = check_first_greater_element(pre_order, root.data)
	if index_for_right == -1:
		root.right = None
		root.left = post_order(pre_order[1:], size)
	else:
		root.right = post_order(pre_order[index_for_right:], size)
		root.left = post_order(pre_order[1:index_for_right], size)
	return root

def check_first_greater_element(input_arr: [], key: int):
	n = len(input_arr)
	for i in range(0, n):
		if key < input_arr[i]:
			return i
	return -1


class Node:

	def __init__(self, data=0):
		self.data = data
		self.left = None
		self.right = None
INT_MAX = 2 ** 63 - 1
INT_MIN = -2 ** 63 - 1

def PreorderToBST(pre, indx, n, minimum, maximum):
	if indx[0] >= n:
		return None
	if pre[indx[0]] > maximum or pre[indx[0]] < minimum:
		return None
	root = Node(pre[indx[0]])
	indx[0] += 1
	root.left = PreorderToBST(pre, indx, n, minimum, root.data)
	root.right = PreorderToBST(pre, indx, n, root.data, maximum)
	return root

def post_order(pre, size) -> Node:
	indx = [0]
	return PreorderToBST(pre, indx, size, INT_MIN, INT_MAX)


class Node:

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

def post_order(pre, size) -> Node:
	preind = [0]

	def findpostorder(minv, maxv):
		if preind[0] >= len(pre):
			return None
		if pre[preind[0]] < minv or pre[preind[0]] > maxv:
			return None
		val = pre[preind[0]]
		root = Node(val)
		preind[0] += 1
		root.left = findpostorder(minv, val)
		root.right = findpostorder(val, maxv)
		return root
	return findpostorder(-999999999, 999999999)


import sys

class Node:

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

def f(pre, size, i, mini, maxi):
	if i[0] >= size:
		return None
	root = None
	if mini <= pre[i[0]] <= maxi:
		root = Node(pre[i[0]])
		i[0] += 1
		if i[0] < size:
			root.left = f(pre, size, i, mini, root.data)
		if i[0] < size:
			root.right = f(pre, size, i, root.data, maxi)
	return root

def post_order(pre, size) -> Node:
	mini = -sys.maxsize
	maxi = sys.maxsize
	i = [0]
	return f(pre, size, i, mini, maxi)


class Node:

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

def f(pre, si, ei):
	if si > ei:
		return None
	if si == ei:
		return Node(pre[si])
	root = Node(pre[si])
	i = si
	while i <= ei:
		if root.data < pre[i]:
			break
		i += 1
	if i == ei + 1:
		root.left = f(pre, si + 1, i - 1)
		root.right = None
	else:
		root.left = f(pre, si + 1, i - 1)
		root.right = f(pre, i, ei)
	return root

def post_order(pre, size) -> Node:
	return f(pre, 0, len(pre) - 1)


class Node:

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

def post_order(pre, size) -> Node:
	root = Node(pre[0])
	for i in range(1, size):
		root1 = post_to_tree(pre[i], root)
	return root1

def post_to_tree(val, root):
	if not root:
		return Node(val)
	if val < root.data:
		root.left = post_to_tree(val, root.left)
	elif val >= root.data:
		root.right = post_to_tree(val, root.right)
	return root


class Node:

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

def post_order(arr, size) -> Node:
	import sys
	sol = []

	def post(root):
		if root == None:
			return
		post(root.left)
		post(root.right)
		sol.append(root.data)

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

	def construct(arr, lb, rb):
		if arr == []:
			return None
		if lb < arr[0] < rb:
			nn = Node(arr.pop(0))
			nn.left = construct(arr, lb, nn.data)
			nn.right = construct(arr, nn.data, rb)
		else:
			return None
		return nn
	postOrd(construct(arr, -sys.maxsize, sys.maxsize))


from collections import deque

class Node:

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

def post_order(pre, size) -> Node:
	queue = deque(pre)

	def createBST(queue, parent):
		if not queue:
			return None
		root = Node(queue.popleft())
		if queue and queue[0] < root.data:
			root.left = createBST(queue, root)
		if queue and (parent and root.data < queue[0] < parent.data):
			root.right = createBST(queue, parent)
		return root
	return createBST(queue, Node(float('inf')))