Given a binary tree. Find the postorder traversal of the tree without using recursion.
Example 1
Input:
           1
         /   \
        2     3
      /  \
     4    5
Output: 4 5 2 3 1
Explanation:
Postorder traversal (Left->Right->Root) of 
the tree is 4 5 2 3 1.
Example 2
Input:
             8
          /      \
        1          5
         \       /   \
          7     10    6
           \   /
            10 6
Output: 10 7 1 6 10 6 5 8 
Explanation:
Postorder traversal (Left->Right->Root) 
of the tree is 10 7 1 6 10 6 5 8 .
 
Your task:
You don't need to read input or print anything. Your task is to complete the function postOrder() which takes the root of the tree as input and returns a list containing the postorder traversal of the tree, calculated without using recursion.
 
Expected time complexity: O(N)
Expected auxiliary space: O(N)
 
Constraints:
1 <= Number of nodes <= 10^{5}
1 <= Data of a node <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
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

'''

class Solution:

    # Return a list containing the inorder traversal of the given tree

    def postOrder(self,node):

        # code here

Solutions:
class Solution:

	def postOrder(self, node):
		if node:
			st = []
			st2 = []
			st.append(node)
			while st:
				root = st.pop()
				st2.append(root.data)
				if root.left:
					st.append(root.left)
				if root.right:
					st.append(root.right)
		return st2[::-1]


class Solution:

	def postOrder(self, node):
		if node == None:
			return []
		ans = []
		q = []
		ans = []
		q.append(node)
		while q != []:
			t = q.pop()
			ans.append(t.data)
			if t.left:
				q.append(t.left)
			if t.right:
				q.append(t.right)
		return ans[::-1]


class Solution:

	def postOrder(self, root):
		post = []
		s1 = []
		s2 = []
		s1.append(root)
		while s1:
			root = s1[-1]
			s1.pop()
			s2.append(root)
			if root.left:
				s1.append(root.left)
			if root.right:
				s1.append(root.right)
		while s2:
			post.append(s2[-1].data)
			s2.pop()
		return post


class Solution:

	def postOrder(self, node):
		a = []

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


class Solution:

	def postOrder(self, node):
		stack = []
		stack.append(node)
		ans = []
		while len(stack) != 0:
			t = stack.pop()
			ans.append(t.data)
			if t.left:
				stack.append(t.left)
			if t.right:
				stack.append(t.right)
		return ans[::-1]


class Solution:

	def postOrder(self, node):
		return fun(root, [])

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


class Solution:

	def postOrder(self, node):
		(s, res) = ([], [])
		s.append(node)
		while len(s) != 0:
			c = s.pop()
			res.append(c.data)
			if c.left is not None:
				s.append(c.left)
			if c.right is not None:
				s.append(c.right)
		res.reverse()
		return res


class Solution:

	def postOrder(self, node):
		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


class Solution:

	def postOrder(self, root):
		a = []

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


class Solution:

	def postOrder(self, node):
		s = [(root, False)]
		res = []
		while s:
			(node, visited) = s.pop()
			if node:
				if visited:
					res.append(node.data)
				else:
					s.append((node, True))
					s.append((node.right, False))
					s.append((node.left, False))
		return res


class Solution:

	def postOrder(self, node):
		if node == None:
			return []
		st = []
		(pre, ino, post) = ([], [], [])
		st.append([node, 1])
		while st:
			(it1, it2) = st.pop()
			if it2 == 1:
				pre.append(it1.data)
				it2 += 1
				st.append([it1, it2])
				if it1.left:
					st.append([it1.left, 1])
			elif it2 == 2:
				ino.append(it1.data)
				it2 += 1
				st.append([it1, it2])
				if it1.right:
					st.append([it1.right, 1])
			else:
				post.append(it1.data)
		return post


class Solution:

	def postOrder(self, node):
		if node 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


class Solution:

	def postOrder(self, node):
		x = []
		y = []
		a = []
		if node is None:
			return
		x.append(node)
		while x:
			t = x.pop()
			y.append(t)
			if t.left:
				x.append(t.left)
			if t.right:
				x.append(t.right)
		while y:
			t = y.pop()
			a.append(t.data)
		return a


class Solution:

	def postOrder(self, node):
		st = []
		st.append(node)
		final = []
		while st:
			curr = st.pop()
			if curr.left:
				st.append(curr.left)
			if curr.right:
				st.append(curr.right)
			final.append(curr.data)
		return final[::-1]


class Solution:

	def postOrder(self, node):
		sta = [root]
		ans = []
		while sta:
			while sta[-1].left and sta[-1].left.data != -1:
				sta.append(sta[-1].left)
			if sta[-1].right and sta[-1].right.data != -1:
				sta.append(sta[-1].right)
			else:
				ans.append(sta[-1].data)
				sta[-1].data = -1
				sta.pop()
		return ans


class Solution:

	def postOrder(self, root):
		ans = []

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


class Solution:

	def postOrder(self, node):
		if not root:
			return []
		st = [root]
		x = []
		while st:
			main = st.pop()
			x.append(main.data)
			if main.left:
				st.append(main.left)
			if main.right:
				st.append(main.right)
		return x[::-1]


class Solution:

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


class Solution:

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


class Solution:

	def postOrder(self, node):
		ans = []

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


from collections import deque

class Solution:

	def postOrder(self, node):
		if root is None:
			return []
		st = [root]
		post = []
		while len(st) != 0:
			node = st.pop()
			if node is not None:
				post.append(node.data)
				st.append(node.left)
				st.append(node.right)
		return post[::-1]


class Solution:

	def postOrder(self, node):
		stack1 = []
		stack2 = []
		postorder = []
		if node == None:
			return postorder
		stack1.append(node)
		while stack1:
			root = stack1[-1]
			stack1.pop()
			stack2.append(root)
			if root.left != None:
				stack1.append(root.left)
			if root.right != None:
				stack1.append(root.right)
		while stack2:
			a = stack2.pop()
			postorder.append(a.data)
		return postorder


class Solution:

	def postOrder(self, node):
		st = []
		r = []
		a = set()
		node = root
		while st or node:
			if node != None:
				st.append(node)
				node = node.left
			else:
				node = st.pop()
				if node.right and node.right not in a:
					st.append(node)
					node = node.right
				else:
					a.add(node)
					r.append(node.data)
					node = None
		return r


class Solution:

	def postOrder(self, root):
		(l1, l2) = ([], [])
		if root == None:
			return l1
		l2.append(root)
		while l2:
			t = l2.pop()
			l1.append(t.data)
			if t.left:
				l2.append(t.left)
			if t.right:
				l2.append(t.right)
		l1 = l1[::-1]
		return l1


class Solution:

	def postOrder(self, node):
		s1 = []
		s2 = []
		s1.append(root)
		while len(s1):
			t = s1.pop()
			s2.append(t)
			if t.left:
				s1.append(t.left)
			if t.right:
				s1.append(t.right)
		res = []
		for i in s2:
			res.append(i.data)
		return res[::-1]


class Solution:

	def postOrder(self, node):
		if node is None:
			return []
		st = [node]
		res = []
		while len(st) != 0:
			it = st.pop()
			if it:
				res.append(it.data)
				st.append(it.left)
				st.append(it.right)
		return res[::-1]


class Solution:

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


class Solution:

	def postOrder(self, node):
		if root is None:
			return
		stack = [root]
		r = []
		a = []
		while len(stack) > 0:
			curr = stack.pop()
			r.append(curr)
			if curr.left:
				stack.append(curr.left)
			if curr.right:
				stack.append(curr.right)
		while r:
			curr = r.pop()
			a.append(curr.data)
		return a


from collections import deque

class Solution:

	def postOrder(self, node):
		st1 = [node]
		st2 = []
		ans = []
		while st1:
			root = st1.pop()
			if root != None:
				st2.append(root)
				if root.left != None:
					st1.append(root.left)
				if root.right != None:
					st1.append(root.right)
		while st2:
			temp = st2.pop()
			ans.append(temp.data)
		return ans


class Solution:

	def postOrder(self, node):
		stck1 = []
		stck2 = []
		stck1.append(node)
		while stck1:
			popped = stck1.pop(-1)
			if popped:
				stck2.append(popped)
				stck1.append(popped.left)
				stck1.append(popped.right)
		res = []
		while stck2:
			popped = stck2.pop(-1)
			res.append(popped.data)
		return res


class Solution:

	def postOrder(self, node):
		ans = []
		self.solve(node, ans)
		return ans

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


class Solution:

	def postOrder(self, root):
		st = []
		st.append([root, 1])
		(preorder, inorder, postorder) = ([], [], [])
		while st:
			var = st.pop()
			if var[1] == 1:
				preorder.append(var[0].data)
				st.append([var[0], 2])
				if var[0].left:
					st.append([var[0].left, 1])
			elif var[1] == 2:
				inorder.append(var[0].data)
				st.append([var[0], 3])
				if var[0].right:
					st.append([var[0].right, 1])
			elif var[1] == 3:
				postorder.append(var[0].data)
		return postorder


class Solution:

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


class Solution:

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


class Solution:

	def postOrder(self, node):
		ans = []
		s = []
		s.append(node)
		while s:
			p = s.pop()
			if type(p) == int:
				ans.append(p)
				continue
			s.append(p.data)
			if p.right:
				s.append(p.right)
			if p.left:
				s.append(p.left)
		return ans


class Solution:

	def postOrder(self, node):
		l = []

		def po(root):
			if not root:
				return -1
			else:
				po(root.left)
				po(root.right)
				l.append(root.data)
		po(root)
		return l


class Solution:

	def postOrder(self, root):
		ans = []
		arr = [root]
		count = 0
		while len(arr) != 0:
			if count == 1:
				arr.pop()
			if root.left:
				arr.append(root.left)
			if root.right:
				arr.append(root.right)
			ans.append(root.data)
			if count == 0:
				arr.pop(0)
				count = 1
			if len(arr) == 0:
				break
			root = arr[len(arr) - 1]
		return ans[::-1]


class Solution:
	s = []

	def postOrder(self, node):
		s = []

		def postOrder1(node):
			if node == None:
				return None
			postOrder1(node.left)
			postOrder1(node.right)
			s.append(node.data)
		postOrder1(node)
		return s


class Solution:

	def postOrder(self, node):
		e = []

		def post(root, e):
			if root:
				if root:
					if root.left:
						post(root.left, e)
					if root.right:
						post(root.right, e)
					e.append(root.data)
		post(root, e)
		return e


class Solution:

	def postOrder(self, node):
		r = root
		(stk, sol) = ([], [])
		while True:
			if r:
				stk.append(r)
				sol.append(r.data)
				r = r.right
			elif stk:
				r = stk.pop()
				r = r.left
			else:
				break
		return sol[::-1]


class Solution:

	def postOrder(self, node):
		if root == None:
			return None
		result = []
		q = deque()
		q.append(root)
		while len(q) != 0:
			ele = q.pop()
			result.append(ele.data)
			if ele.left:
				q.append(ele.left)
			if ele.right:
				q.append(ele.right)
		return result[::-1]


class Solution:

	def postOrder(self, node):
		post = []
		curr = node
		while curr != None:
			if curr.right == None:
				post.append(curr.data)
				curr = curr.left
			else:
				temp = curr.right
				while temp.left != None and temp.left != curr:
					temp = temp.left
				if temp.left == None:
					post.append(curr.data)
					temp.left = curr
					curr = curr.right
				else:
					temp.left = None
					curr = curr.left
		post.reverse()
		return post


class Solution:

	def postOrder(self, node):
		st = []
		ans = []
		st.append(node)
		while st:
			cn = st.pop()
			ans.append(cn.data)
			if cn.left:
				st.append(cn.left)
			if cn.right:
				st.append(cn.right)
		ans.reverse()
		return ans


class Solution:

	def postOrder(self, node):

		def pos(r, l):
			if r == None:
				return
			pos(r.left, l)
			pos(r.right, l)
			l.append(r.data)
		l = []
		pos(node, l)
		return l


from collections import deque

class Solution:

	def postOrder(self, node):
		answer = []
		if root == None:
			return answer
		stack = deque()
		while True:
			if node:
				stack.append(node)
				node = node.left
			else:
				temp = stack[-1].right
				if temp:
					node = temp
				else:
					if len(stack):
						temp1 = stack.pop()
						answer.append(temp1.data)
					while len(stack) and stack[-1].right == temp1:
						temp1 = stack.pop()
						answer.append(temp1.data)
					if len(stack) == 0:
						return answer


class Solution:

	def postOrder(self, node):
		if node is None:
			return []
		stack1 = [node]
		stack2 = []
		while stack1:
			n = stack1.pop()
			stack2.append(n.data)
			if n.left:
				stack1.append(n.left)
			if n.right:
				stack1.append(n.right)
		stack2 = stack2[-1::-1]
		return stack2


class Solution:

	def postOrder(self, node):
		if root == None:
			return
		q = []
		q.append(root)
		c = []
		while len(q) > 0:
			temp = q.pop(-1)
			c.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
		return c[::-1]


class Solution:

	def postOrder(self, node):
		if node is None:
			return []
		stack1 = [node]
		stack2 = []
		while stack1:
			ele = stack1.pop()
			if ele:
				stack1.append(ele.left)
				stack1.append(ele.right)
				stack2.append(ele.data)
		stack2.reverse()
		return stack2


class Solution:

	def postOrder(self, node):
		self.res = []

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


class Solution:

	def postOrder(self, node):
		if not root:
			return
		stck = []
		res = []
		node = root
		vis = set()
		while stck or node:
			if node:
				stck.append(node)
				node = node.left
			else:
				node = stck.pop()
				if node.right and (not node.right in vis):
					stck.append(node)
					node = node.right
				else:
					vis.add(node)
					res.append(node.data)
					node = None
		return res


class Solution:

	def postOrder(self, node):
		from collections import deque
		s1 = deque()
		s2 = deque()
		result = []
		if not node:
			return result
		s1.append(node)
		while len(s1):
			node = s1.pop()
			s2.append(node.data)
			if node.left:
				s1.append(node.left)
			if node.right:
				s1.append(node.right)
		while len(s2):
			result.append(s2.pop())
		return result


class Solution:

	def peek(self, stack):
		if len(stack) > 0:
			return stack[-1]
		return None

	def postOrder(self, node):
		root = node
		if root is None:
			return []
		stack = []
		res = []
		while True:
			while root:
				if root.right:
					stack.append(root.right)
				stack.append(root)
				root = root.left
			root = stack.pop()
			if root.right is not None and root.right == self.peek(stack):
				stack.pop()
				stack.append(root)
				root = root.right
			else:
				res.append(root.data)
				root = None
			if len(stack) <= 0:
				break
		return res


class Solution:

	def postOrder(self, node):
		stack = []
		cur = root
		res = []
		res1 = []
		while True:
			if cur is not None:
				stack.append(cur)
				res.append(cur.data)
				cur = cur.right
			elif stack:
				cur = stack.pop()
				cur = cur.left
			else:
				break
		while res:
			res1.append(res.pop())
		return res1


class Solution:

	def postOrder(self, node):
		s1 = [node]
		s2 = []
		postorder = []
		while s1:
			root = s1.pop()
			s2.append(root.data)
			if root.left:
				s1.append(root.left)
			if root.right:
				s1.append(root.right)
		while s2:
			node = s2.pop()
			postorder.append(node)
		return postorder


class Solution:

	def postOrder(self, node):
		ans = []
		stack = [(root, False)]
		while stack:
			(curr, vis) = stack.pop()
			if curr:
				if vis:
					ans.append(curr.data)
				else:
					stack.append((curr, True))
					if curr.right != None:
						stack.append((curr.right, False))
					if curr.left != None:
						stack.append((curr.left, False))
		return ans


class Solution:

	def postOrder(self, node):
		res = []
		if not node:
			return
		stack = [node]
		while stack:
			curr = stack.pop()
			res.append(curr.data)
			if curr.left:
				stack.append(curr.left)
			if curr.right:
				stack.append(curr.right)
		return res[::-1]


class Solution:

	def postOrder(self, node):
		ans = []
		stack = [node]
		while stack:
			ele = stack.pop()
			if ele is None:
				continue
			ans.append(ele.data)
			stack.append(ele.left)
			stack.append(ele.right)
		return ans[::-1]


class Solution:
	from collections import deque

	def postOrder(self, node):
		d1 = deque()
		l = []
		d2 = deque()
		d1 += [node]
		while len(d1) != 0:
			n = d1.pop()
			d2 += [n]
			if n.left != None:
				d1 += [n.left]
			if n.right != None:
				d1 += [n.right]
		while len(d2) != 0:
			p = d2.pop()
			l += [p.data]
		return l


class Solution:

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


class Solution:

	def postOrder(self, node):
		stack1 = []
		vec = []
		stack2 = []
		stack1.append(node)
		while stack1 != []:
			temp = stack1[-1]
			stack2.append(temp.data)
			stack1.pop()
			if temp.left:
				stack1.append(temp.left)
			if temp.right:
				stack1.append(temp.right)
		while stack2 != []:
			vec.append(stack2[-1])
			stack2.pop()
		return vec


class Solution:

	def postOrder(self, node):
		res = []
		stk = []
		cur = node
		if not node:
			return res
		while cur or stk:
			if cur:
				stk.append(cur)
				cur = cur.left
				continue
			else:
				temp = stk[-1].right
				if not temp:
					temp = stk.pop()
					res.append(temp.data)
					while stk and stk[-1].right == temp:
						temp = stk.pop()
						res.append(temp.data)
				else:
					cur = temp
		return res


class Solution:

	def postOrder(self, node):
		output = []
		stack = [node]
		while stack:
			root = stack.pop()
			if root is None:
				continue
			output.append(root.data)
			stack.append(root.left)
			stack.append(root.right)
		return output[::-1]


class Solution:

	def postOrder(self, root):
		s1 = []
		s2 = []
		res = []
		cur = None
		s1.append(root)
		while len(s1):
			cur = s1[-1]
			s1.pop()
			s2.append(cur)
			if cur.left:
				s1.append(cur.left)
			if cur.right:
				s1.append(cur.right)
		while len(s2):
			cur = s2[-1]
			res.append(cur.data)
			s2.pop()
		return res


class Solution:

	def postOrder(self, node):
		stack = [[root, 1]]
		pre = list()
		while stack:
			if stack[-1][1] == 1:
				stack[-1][1] += 1
				if stack[-1][0].left:
					stack.append([stack[-1][0].left, 1])
			elif stack[-1][1] == 2:
				stack[-1][1] += 1
				if stack[-1][0].right:
					stack.append([stack[-1][0].right, 1])
			else:
				pre.append(stack.pop()[0].data)
		return pre


class Solution:

	def postOrder(self, node):
		nodes = []

		def dfs(root):
			if not root:
				return None
			dfs(root.left)
			dfs(root.right)
			nodes.append(root.data)
		dfs(root)
		return nodes


class Solution:

	def post(self, s1, s2, r):
		while s1:
			t = s1.pop()
			s2.append(t.data)
			if t.left:
				s1.append(t.left)
			if t.right:
				s1.append(t.right)

	def postOrder(self, r):
		s1 = [r]
		s2 = []
		self.post(s1, s2, r)
		s2.reverse()
		return s2


class Solution:

	def postOrder(self, node):
		postOrder = []
		stack = []
		if node:
			stack.append([node, 1])
		while stack:
			if stack[-1][1] == 1:
				stack[-1][1] += 1
				curNode = stack[-1][0]
				if curNode.left:
					stack.append([curNode.left, 1])
			if stack[-1][1] == 2:
				stack[-1][1] += 1
				curNode = stack[-1][0]
				if curNode.right:
					stack.append([curNode.right, 1])
			if stack[-1][1] == 3:
				(curr, val) = stack.pop()
				postOrder.append(curr.data)
		return postOrder


class Solution:

	def postOrder(self, root):
		list1 = []
		self.result(root, list1)
		return list1

	def result(self, root, list1):
		if root:
			self.result(root.left, list1)
			self.result(root.right, list1)
			list1.append(root.data)


class Solution:

	def postOrder(self, node):
		s1 = []
		s2 = []
		arr = []
		s1.append(root)
		while len(s1) != 0:
			a = s1.pop()
			s2.append(a)
			if a.left:
				s1.append(a.left)
			if a.right:
				s1.append(a.right)
		while len(s2) != 0:
			arr.append(s2.pop().data)
		return arr


from collections import deque

class Solution:

	def postOrder(self, node):
		if not node:
			return
		cur = node
		ans = deque()
		nodes = []
		nodes.append(cur)
		while nodes:
			cur = nodes.pop()
			ans.appendleft(cur.data)
			if cur.left:
				nodes.append(cur.left)
			if cur.right:
				nodes.append(cur.right)
		return ans


class Solution:

	def h(self, root, r):
		if root:
			self.h(root.left, r)
			self.h(root.right, r)
			r.append(root.data)

	def postOrder(self, node):
		if not root:
			return
		r = []
		self.h(root, r)
		return r


class Solution:

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


class Solution:

	def postOrder(self, node):
		if not root:
			return []
		stack = []
		result = []
		visited = set()
		node = root
		while stack or node:
			if node is not None:
				stack.append(node)
				node = node.left
			else:
				node = stack.pop()
				if node.right and (not node.right in visited):
					stack.append(node)
					node = node.right
				else:
					visited.add(node)
					result.append(node.data)
					node = None
		return result


class Solution:

	def postOrder(self, node):
		stack = [[node, 1]]
		(pre, post, inorder) = ([], [], [])
		if not node:
			return []
		while stack:
			val = stack.pop()
			if val[1] == 1:
				pre.append(val[0].data)
				val[1] += 1
				stack.append(val)
				if val[0].left:
					stack.append([val[0].left, 1])
			elif val[1] == 2:
				inorder.append(val[0].data)
				val[1] += 1
				stack.append(val)
				if val[0].right:
					stack.append([val[0].right, 1])
			else:
				post.append(val[0].data)
		return post


class Solution:

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

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


class Solution:

	def postOrder(self, node):
		st = [root]
		l = []
		while len(st) != 0:
			x = st.pop()
			if x is not None:
				l.append(x.data)
				st.append(x.left)
				st.append(x.right)
		return l[::-1]


class Solution:

	def postOrder(self, node):
		s1 = []
		s2 = []
		ans = []
		if node is None:
			return
		s1.append(node)
		while s1:
			t = s1.pop()
			s2.append(t)
			if t.left:
				s1.append(t.left)
			if t.right:
				s1.append(t.right)
		while s2:
			t = s2.pop()
			ans.append(t.data)
		return ans


class Solution:

	def postOrder(self, node):
		self.out = []

		def Preorder(root):
			if root:
				Preorder(root.left)
				Preorder(root.right)
				self.out.append(root.data)
		Preorder(node)
		return self.out


from collections import deque

class Solution:

	def postOrder(self, node):
		q = deque()
		q.append(node)
		res = deque()
		while q:
			v = q.pop()
			res.appendleft(v.data)
			if v.left:
				q.append(v.left)
			if v.right:
				q.append(v.right)
		return res


class Solution:

	def postOrder(self, node):
		if not root:
			return []
		s = [root]
		ans = []
		while s:
			top = s.pop()
			ans.append(top.data)
			if top.left:
				s.append(top.left)
			if top.right:
				s.append(top.right)
		return ans[::-1]


class Solution:

	def postOrder(self, node):
		l = []

		def ak(node, l):
			if node is None:
				return 0
			ak(node.left, l)
			ak(node.right, l)
			l.append(node.data)
			return l
		return ak(root, l)


class Solution:

	def postOrder(self, node):
		ans = []

		def dfs(node):
			if not node:
				return
			dfs(node.left)
			dfs(node.right)
			ans.append(node.data)
		dfs(node)
		return ans


class Solution:

	def postOrder(self, node):
		stack = [(node, 1)]
		preorder = []
		postorder = []
		inorder = []
		while stack:
			(curr, num) = stack.pop()
			if num == 1:
				preorder.append(curr.data)
				stack.append((curr, num + 1))
				if curr.left:
					stack.append((curr.left, 1))
			elif num == 2:
				inorder.append(curr.data)
				stack.append((curr, num + 1))
				if curr.right:
					stack.append((curr.right, 1))
			else:
				postorder.append(curr.data)
		return postorder