Given a binary tree, find the Postorder Traversal of it.
For Example, the postorder traversal of the following tree is: 
5 10 39 1
        1
     /     \
   10     39
  /
5
Example 1:
Input:
        19
     /     \
    10      8
  /    \
 11    13
Output: 11 13 10 8 19
Example 2:
Input:
          11
         /
       15
      /
     7
Output: 7 15 11
Your Task:
You don't need to read input or print anything. Your task is to complete the function postOrder() that takes root node as input and returns an array containing the postorder traversal of the given Binary Tree.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= Number of nodes <= 10^{5}
0 <= Data of a node <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3


'''
# Node Class:
class Node:
    def __init__(self,val):
        self.data = val
        self.left = None
        self.right = None
'''

#Function to return a list containing the postorder traversal of the tree.
def postOrder(root):
    # code here


Solutions:
def postOrder(root):

	def helper(root, ans):
		if root:
			helper(root.left, ans)
			helper(root.right, ans)
			ans.append(root.data)
	res = []
	helper(root, res)
	return res


def postOrder(root):
	li = []
	q = [root]
	while q:
		obg = q.pop()
		if obg:
			li.append(obg.data)
			q.append(obg.left)
			q.append(obg.right)
	li.reverse()
	return li


def Helper(root, postorder):
	if not root:
		return []
	Helper(root.left, postorder)
	Helper(root.right, postorder)
	postorder.append(root.data)
	return postorder

def postOrder(root):
	return Helper(root, [])


def postOrder(root):
	a = []

	def postorder(root):
		if root:
			postorder(root.left)
			postorder(root.right)
			a.append(root.data)
		else:
			return
		return a
	return postorder(root)


def postOrder(root):
	res = []
	helper(root, res)
	return res

def helper(root, res):
	if root is None:
		return
	helper(root.left, res)
	helper(root.right, res)
	res.append(root.data)


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

def postOrder(root):
	res = list()
	PostOrder(root, res)
	return res


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


def postOrder(root):
	if root == None:
		return []
	nodes = []
	nodes.extend(postOrder(root.left))
	nodes.extend(postOrder(root.right))
	nodes.append(root.data)
	return nodes


def postOrder(root):
	ans = []
	if root is not None:
		ans += postOrder(root.left)
		ans += postOrder(root.right)
		ans.append(root.data)
	return ans


def postOrder(root):
	ans = []
	if root.left:
		ans += postOrder(root.left)
	if root.right:
		ans += postOrder(root.right)
	ans.append(root.data)
	return ans


def postOrder(root):
	s = [root]
	res = []
	while len(s) > 0:
		node = s.pop()
		res.append(node.data)
		if node.left:
			s.append(node.left)
		if node.right:
			s.append(node.right)
	res.reverse()
	return res


def postOrder(root):
	if root == None:
		return []
	ans1 = postOrder(root.left)
	ans2 = postOrder(root.right)
	ans = [root.data]
	ans = ans1 + ans2 + ans
	return ans


def postOrder(root):
	stack = [root]
	ans = []
	while stack:
		node = stack.pop()
		ans.append(node.data)
		if node.left:
			stack.append(node.left)
		if node.right:
			stack.append(node.right)
	return ans[::-1]


def po(root, s):
	if not root:
		return
	po(root.left, s)
	po(root.right, s)
	s.append(root.data)

def postOrder(root):
	s = []
	po(root, s)
	return s


arr = []

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


def postOrder(root):
	ans = []
	if root is None:
		return ans
	stack = []
	stack.append(root)
	while len(stack) != 0:
		top = stack.pop()
		if top.left is not None:
			stack.append(top.left)
		if top.right is not None:
			stack.append(top.right)
		ans.append(top.data)
	return ans[::-1]


def postOrder(root):
	if root:
		return postOrder(root.left) + postOrder(root.right) + [root.data]
	else:
		return []


def solve(root, l):
	if root:
		solve(root.left, l)
		solve(root.right, l)
		l.append(root.data)

def postOrder(root):
	l = []
	solve(root, l)
	return l


def postOrder(root):
	arr = []
	if root != None:
		postOrder(root.left)
		postOrder(root.right)
		print(root.data, end=' ')
	return arr


def cal_postorder(root, ans_lst):
	if root:
		cal_postorder(root.left, ans_lst)
		cal_postorder(root.right, ans_lst)
		ans_lst.append(root.data)
	return ans_lst

def postOrder(root):
	ans_lst = []
	return cal_postorder(root, ans_lst)


def postOrder(root):
	trav = []

	def traverse(root):
		if not root:
			return
		traverse(root.left)
		traverse(root.right)
		trav.append(root.data)
	traverse(root)
	return trav


def helper(root, ans):
	if root == None:
		return
	helper(root.left, ans)
	helper(root.right, ans)
	ans.append(root.data)

def postOrder(root):
	ans = []
	helper(root, ans)
	return ans


def postOrder(root):
	result = []
	if root.left:
		result += postOrder(root.left)
	if root.right:
		result += postOrder(root.right)
	result.append(root.data)
	return result


def postOrder(root):
	res = []
	if root.left:
		res += postOrder(root.left)
	if root.right:
		res += postOrder(root.right)
	res.append(root.data)
	return res


def postOrder(root):
	post = []
	st = []
	curr = root
	while curr != None or len(st) != 0:
		if curr != None:
			st.append(curr)
			curr = curr.left
		else:
			temp = st[-1].right
			if temp == None:
				temp = st.pop()
				post.append(temp.data)
				while len(st) != 0 and temp == st[-1].right:
					temp = st.pop()
					post.append(temp.data)
			else:
				curr = temp
	return post


def postOrder(root):
	postorder = []
	if not root:
		return postorder
	st1 = deque()
	st2 = deque()
	st1.append(root)
	while len(st1) != 0:
		node = st1.pop()
		st2.append(node)
		if node.left:
			st1.append(node.left)
		if node.right:
			st1.append(node.right)
	while len(st2) != 0:
		node = st2.pop()
		postorder.append(node.data)
	return postorder


def postOrder(root):
	stack = [(root, False)]
	ans = []
	while stack:
		(node, visited) = stack.pop()
		if visited:
			ans.append(node.data)
		elif node:
			stack.append((node, True))
			stack.append((node.right, False))
			stack.append((node.left, False))
	return ans


def postOrder(root):
	if root is None:
		return
	a = [root]
	ans = []
	while a:
		t = a.pop()
		ans.append(t.data)
		if t.left:
			a.append(t.left)
		if t.right:
			a.append(t.right)
	return ans[::-1]


def postOrder(root):
	arr = []
	solve(root, arr)
	return arr

def solve(root, arr):
	if root is None:
		return
	solve(root.left, arr)
	solve(root.right, arr)
	arr.append(root.data)


def po(root, arr):
	if root:
		po(root.left, arr)
		po(root.right, arr)
		arr.append(root.data)

def postOrder(root):
	arr = []
	po(root, arr)
	return arr


def postOrder(root):
	if root:
		l = postOrder(root.left)
		r = postOrder(root.right)
		return l + r + [root.data]
	return []


def postOrder(root):
	res = []
	postOrder_res(res, root)
	return res

def postOrder_res(res, root):
	if root == None:
		return
	postOrder_res(res, root.left)
	postOrder_res(res, root.right)
	res.append(root.data)


def postOrder(root):
	mylist = []
	ans = postOrderHelper(root, mylist)
	x = []
	if ans == -1:
		x.append(-1)
		return x
	return ans

def postOrderHelper(root, mylist):
	if root is None:
		return -1
	postOrderHelper(root.left, mylist)
	postOrderHelper(root.right, mylist)
	mylist.append(root.data)
	return mylist


def postOrder(root):
	current = root
	stack = []
	ans = []
	while current or stack:
		if current:
			if current.right:
				stack.append(current.right)
			stack.append(current)
			current = current.left
		else:
			node = stack.pop()
			if stack and node.right == stack[-1]:
				current = stack.pop()
				stack.append(node)
			else:
				ans.append(node.data)
	return ans


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


def postOrder(root):

	def getpostorder(root):
		if not root:
			return
		getpostorder(root.left)
		getpostorder(root.right)
		ans.append(root.data)
		return ans
	ans = []
	getpostorder(root)
	return ans


def postOrder(root):
	s1 = []
	s2 = []
	res = []
	s1.append(root)
	while len(s1) != 0:
		popped_val = s1.pop()
		s2.append(popped_val)
		if popped_val.left:
			s1.append(popped_val.left)
		if popped_val.right:
			s1.append(popped_val.right)
	while len(s2) != 0:
		res.append(s2.pop().data)
	return res


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


def postOrder(root):
	if root is None:
		return
	stack = []
	result = []
	stack.append(root)
	while stack:
		current = stack.pop()
		result.append(current.data)
		if current.left:
			stack.append(current.left)
		if current.right:
			stack.append(current.right)
	result = result[::-1]
	return result


def postOrder(root):
	result = []

	def postOrderTraversal(node):
		if node is None:
			return
		postOrderTraversal(node.left)
		postOrderTraversal(node.right)
		result.append(node.data)
	postOrderTraversal(root)
	return result


def postOrder(root):
	if root == None:
		return []
	rn = postOrder(root.right)
	ln = postOrder(root.left)
	return ln + rn + [root.data]


def helper(root, ans):
	if not root:
		return ans
	helper(root.left, ans)
	helper(root.right, ans)
	ans.append(root.data)
	return ans

def postOrder(root):
	return helper(root, [])


def postOrder(root):
	if root == None:
		return []
	if root.left == None and root.right == None:
		return [root.data]
	leftarr = postOrder(root.left)
	rightarr = postOrder(root.right)
	return leftarr + rightarr + [root.data]


def postOrder(root):
	answer = []
	stack = [root]
	while stack:
		node = stack.pop()
		answer.append(node.data)
		if node.left:
			stack.append(node.left)
		if node.right:
			stack.append(node.right)
	return list(reversed(answer))


def postOrder(root):
	res = []

	def post(root, res):
		if root != None:
			post(root.left, res)
			post(root.right, res)
			res.append(root.data)
	post(root, res)
	return res


def postOrder(root):
	l = []

	def traverse(node):
		if node:
			traverse(node.left)
			traverse(node.right)
			l.append(node.data)
	traverse(root)
	return l


def postOrder(root):
	ans = []
	stk = [root]
	curr = None
	while stk:
		curr = stk.pop()
		ans.append(curr.data)
		if curr.left:
			stk.append(curr.left)
		if curr.right:
			stk.append(curr.right)
	return ans[::-1]


def postOrder(root):
	stack1 = []
	stack2 = []
	stack1.append(root)
	node = root
	while stack1:
		node = stack1[-1]
		stack2.append(stack1[-1].data)
		stack1.pop()
		if node.left:
			stack1.append(node.left)
		if node.right:
			stack1.append(node.right)
	return stack2[::-1]


def getList(root, li):
	if root:
		getList(root.left, li)
		getList(root.right, li)
		li.append(root.data)

def postOrder(root):
	li = []
	getList(root, li)
	return li


def postOrder(root):
	if root == None:
		return []
	if root.left == None and root.right == None:
		return [root.data]
	left = postOrder(root.left)
	right = postOrder(root.right)
	arr = []
	arr += left + right
	arr.append(root.data)
	return arr


def postOrder(root):

	def cal(root, stack):
		if root is None:
			return
		cal(root.left, stack)
		cal(root.right, stack)
		stack.append(root.data)
	stack = []
	cal(root, stack)
	return stack


def postOrder(root):

	def postOrderTraversal(root, l):
		if root is None:
			return
		if root.left:
			root.left = postOrderTraversal(root.left, l)
		if root.right:
			root.right = postOrderTraversal(root.right, l)
		l.append(root.data)
	l = []
	postOrderTraversal(root, l)
	return l


def rec_sol(root, ans):
	if root.left != None:
		rec_sol(root.left, ans)
	if root.right != None:
		rec_sol(root.right, ans)
	ans.append(root.data)

def postOrder(root):
	ans = []
	stack = []
	stack.append(root)
	while len(stack) != 0:
		node = stack.pop()
		ans.append(node.data)
		if node.left != None:
			stack.append(node.left)
		if node.right != None:
			stack.append(node.right)
	ans.reverse()
	return ans


def rec_sol(root, ans):
	if root.left != None:
		rec_sol(root.left, ans)
	if root.right != None:
		rec_sol(root.right, ans)
	ans.append(root.data)

def postOrder(root):
	ans = []
	rec_sol(root, ans)
	return ans


def postOrder(root):
	z = []

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


def postOrder(root):
	a = []

	def solve(root):
		if root:
			solve(root.left)
			solve(root.right)
			a.append(root.data)
	solve(root)
	return a


def postOrder(root):
	ans = []

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


def postorderutil(root, res):
	if root != None:
		postorderutil(root.left, res)
		postorderutil(root.right, res)
		res.append(root.data)

def postOrder(root):
	res = []
	postorderutil(root, res)
	return res


def postOrder(root):
	if root == None:
		return []
	left_nodes = postOrder(root.left)
	right_nodes = postOrder(root.right)
	return left_nodes + right_nodes + [root.data]


def postOrder(root):
	ans = []
	stk = []
	cur = root
	while cur or len(stk):
		if cur != None:
			ans.append(cur.data)
			stk.append(cur)
			cur = cur.right
		else:
			cur = stk.pop()
			cur = cur.left
	return ans[::-1]


def postOrder(root):
	if root == None:
		return []
	left_n = postOrder(root.left)
	right_n = postOrder(root.right)
	ans = left_n + right_n + [root.data]
	return ans