Given a binary tree. Find the inorder traversal of the tree without using recursion.
Example 1
Input:
           1
         /    \
       2       3
      /   \
    4     5
Output: 4 2 5 1 3
Explanation:
Inorder traversal (Left->Root->Right) of 
the tree is 4 2 5 1 3.
Example 2
Input:
            8
          /   \
            1      5
             \    /  \
             7   10   6
             \  /
          10 6
Output: 1 7 10 8 6 10 5 6
Explanation:
Inorder traversal (Left->Root->Right) 
of the tree is 1 7 10 8 6 10 5 6.
 
Your task:
You don't need to read input or print anything. Your task is to complete the function inOrder() which takes the root of the tree as input and returns a list containing the inorder 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
'''

# Return a list containing the inorder traversal of the given tree
class Solution:
    def inOrder(self, root):
        # code here

Solutions:
class Solution:

	def inOrder(self, root):
		result = []
		stack = []
		currentNode = root
		while True:
			if currentNode:
				stack.append(currentNode)
				currentNode = currentNode.left
			elif stack:
				currentNode = stack.pop()
				result.append(currentNode.data)
				currentNode = currentNode.right
			else:
				break
		return result


class Solution:

	def inOrder(self, root):
		result = []
		stack = []
		currentNode = root
		while currentNode or stack:
			while currentNode:
				stack.append(currentNode)
				currentNode = currentNode.left
			currentNode = stack.pop()
			result.append(currentNode.data)
			currentNode = currentNode.right
		return result


class Solution:

	def inOrder(self, root):
		ans = []
		st = []
		while True:
			if root:
				st.append(root)
				root = root.left
			elif st:
				root = st.pop()
				ans.append(root.data)
				root = root.right
			else:
				break
		return ans


class Solution:

	def inOrder(self, root):
		return fun(root, [])

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


class Solution:

	def inOrder(self, root):
		s = []
		res = []
		current = root
		while True:
			if current is not None:
				s.append(current)
				current = current.left
			elif len(s) > 0:
				current = s.pop()
				res.append(current.data)
				current = current.right
			else:
				break
		return res


class Solution:

	def inOrder(self, root):
		cur = root
		stack = []
		res = []
		while stack or cur:
			while cur:
				stack.append(cur)
				cur = cur.left
			cur = stack.pop()
			res.append(cur.data)
			cur = cur.right
		return res


class Solution:

	def inOrder(self, root):
		result = []
		stack = []
		current = root
		while current or stack:
			while current:
				stack.append(current)
				current = current.left
			node = stack.pop()
			result.append(node.data)
			current = node.right
		return result


class Solution:

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


class Solution:

	def inOrder(self, root):
		(s, ans) = ([], [])
		curr = root
		while len(s) > 0 or curr != None:
			while curr != None:
				s.append(curr)
				curr = curr.left
			curr = s.pop()
			ans.append(curr.data)
			curr = curr.right
		return ans


class Solution:

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

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


class Solution:

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


class Solution:

	def inOrder(self, r):
		s = []
		res = []
		while True:
			if r:
				s += [r]
				r = r.left
			else:
				if not s:
					break
				r = s.pop()
				res += [r.data]
				r = r.right
		return res


class Solution:

	def inOrder(self, root):
		stack = [root]
		current = root.left
		final = []
		while len(stack) > 0 or current != None:
			while current != None:
				stack.append(current)
				current = current.left
			current = stack.pop(-1)
			final.append(current.data)
			current = current.right
		return final


class Solution:

	def inOrder(self, root):
		stack = []
		result = []
		current = root
		if root is None:
			return result
		while current or stack:
			while current:
				stack.append(current)
				current = current.left
			current = stack.pop()
			result.append(current.data)
			current = current.right
		return result


class Solution:

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


class Solution:

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


class Solution:

	def inOrder(self, root):
		if not root:
			return []
		st = []
		x = []
		dummy = root
		while st or dummy:
			if dummy:
				st.append(dummy)
				dummy = dummy.left
			else:
				main = st.pop()
				x.append(main.data)
				dummy = main.right
		return x


class Solution:

	def inOrder(self, root):
		stack = []
		ans = []
		curr = root
		while 1:
			if curr is not None:
				stack.append(curr)
				curr = curr.left
			elif len(stack) != 0:
				curr = stack.pop()
				ans.append(curr.data)
				curr = curr.right
			else:
				break
		return ans


class Solution:

	def inOrder(self, root):
		inorder = []
		if root == None:
			return
		stack = []
		curr = root
		while curr != None:
			stack.append(curr)
			curr = curr.left
		while stack:
			curr = stack.pop()
			inorder.append(curr.data)
			curr = curr.right
			while curr != None:
				stack.append(curr)
				curr = curr.left
		return inorder


class Solution:

	def inOrder(self, root):
		s = []

		def inorder(root):
			if root != None:
				inorder(root.left)
				s.append(root.data)
				inorder(root.right)
		inorder(root)
		return s


class Solution:

	def inOrder(self, root):
		ans = []
		stack = []
		while root:
			stack.append(root)
			root = root.left
		while stack:
			root = stack.pop()
			ans.append(root.data)
			if root.right:
				root = root.right
				while root:
					stack.append(root)
					root = root.left
		return ans


class Solution:

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

		def help(node):
			if node:
				help(node.left)
				ans.append(node.data)
				help(node.right)
				return ans
		return help(root)


class Solution:

	def inOrder(self, root):
		arr = []
		stack = []
		curr = root
		while curr is not None:
			stack.append(curr)
			curr = curr.left
		while stack:
			curr = stack.pop()
			arr.append(curr.data)
			curr = curr.right
			while curr is not None:
				stack.append(curr)
				curr = curr.left
		return arr


class Solution:

	def inOrder(self, root):
		stack = []
		current = root
		res = []
		while True:
			if current:
				stack.append(current)
				current = current.left
			elif stack:
				current = stack.pop()
				res.append(current.data)
				current = current.right
			else:
				break
		return res


class Solution:

	def inOrder(self, root):
		st = []
		r = []
		node = root
		while st or node:
			if node != None:
				st.append(node)
				node = node.left
			else:
				node = st.pop()
				r.append(node.data)
				node = node.right
		return r


class Solution:

	def inOrder(self, root):
		s = []
		l = []
		while 1:
			if root != None:
				s.append(root)
				root = root.left
			elif len(s):
				t = s.pop()
				l.append(t.data)
				root = t.right
			else:
				break
		return l


class Solution:

	def inOrder(self, root):
		l = [root]
		curr = root
		res = []
		while len(l):
			if curr != None:
				l.append(curr)
				curr = curr.left
			else:
				t = l.pop()
				res.append(t.data)
				curr = t.right
		res.pop()
		return res


class Solution:

	def inOrder(self, root):
		res = []
		st = []
		curr = root
		while st or curr:
			while curr:
				st.append(curr)
				curr = curr.left
			curr = st.pop()
			res.append(curr.data)
			curr = curr.right
		return res


class Solution:

	def inOrder(self, root):
		curr = root
		res = []
		while curr:
			if curr.left is None:
				res.append(curr.data)
				curr = curr.right
			else:
				prev = curr.left
				while prev.right and prev.right != curr:
					prev = prev.right
				if prev.right is None:
					prev.right = curr
					curr = curr.left
				else:
					res.append(curr.data)
					curr = curr.right
					prev.right = None
		return res


class Solution:

	def inOrder(self, root):
		l = []

		def inO(root):
			if not root:
				return []
			else:
				inO(root.left)
				l.append(root.data)
				inO(root.right)
		inO(root)
		return l


class Solution:

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


class Solution:

	def inOrder(self, root):
		st = []
		ino = []
		while True:
			if root is not None:
				st.append(root)
				root = root.left
			else:
				if len(st) == 0:
					return ino
				root = st[-1]
				st.pop()
				ino.append(root.data)
				root = root.right
		return ino


class Solution:

	def inOrder(self, root):
		in_order = []
		node = root
		stack = []
		while True:
			if node != None:
				stack.append(node)
				node = node.left
			else:
				if len(stack) < 1:
					break
				node = stack.pop()
				in_order.append(node.data)
				node = node.right
		return in_order


class Solution:

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


class Solution:

	def inOrder(self, root):
		current = root
		stack = []
		while True:
			if current is not None:
				stack.append(current)
				current = current.left
			elif stack:
				current = stack.pop()
				print(current.data, end=' ')
				current = current.right
			else:
				break
		return []


class Solution:

	def inOrder(self, root):
		curr = root
		stack = []
		ans = []
		while stack or curr:
			if curr:
				stack.append(curr)
				curr = curr.left
			else:
				curr = stack.pop()
				ans += [curr.data]
				curr = curr.right
		return ans


from collections import deque

class Solution:

	def inOrder(self, root):
		curr = root
		ans = []
		while curr:
			if curr.left == None:
				ans.append(curr.data)
				curr = curr.right
			else:
				node = curr.left
				while node.right and node.right != curr:
					node = node.right
				if node.right == None:
					node.right = curr
					curr = curr.left
				else:
					node.right = None
					ans.append(curr.data)
					curr = curr.right
		return ans


class Solution:

	def inOrder(self, root):
		result = []
		curr = root
		while curr:
			if curr.left is None:
				result.append(curr.data)
				curr = curr.right
			else:
				pre = curr.left
				while pre.right and pre.right != curr:
					pre = pre.right
				if pre.right is None:
					pre.right = curr
					curr = curr.left
				else:
					pre.right = None
					result.append(curr.data)
					curr = curr.right
		return result


class Solution:

	def inOrder(self, root):
		e = []

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


class Solution:

	def inOrder(self, root):
		sol = []
		stk = [root]
		while stk:
			r = stk[-1]
			while r and r.left:
				stk.append(r.left)
				r = r.left
			r = stk.pop()
			sol.append(r.data)
			while stk and r.right == None:
				r = stk.pop()
				sol.append(r.data)
			if r.right:
				stk.append(r.right)
		return sol


class Solution:

	def inOrder(self, root):

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


from collections import deque

class Solution:

	def inOrder(self, root):
		answer = []
		stack = deque()
		node = root
		while True:
			if node != None:
				stack.append(node)
				node = node.left
			elif len(stack):
				temp = stack.pop()
				answer.append(temp.data)
				node = temp.right
			else:
				return answer


class Solution:

	def inOrder(self, root):
		q = []
		ans = []
		cur = root
		while True:
			if cur is not None:
				q.append(cur)
				cur = cur.left
			elif q:
				cur = q.pop()
				ans.append(cur.data)
				cur = cur.right
			else:
				break
		return ans


class Solution:

	def inOrder(self, root):
		result = []
		curr = root
		while curr:
			if not curr.left:
				result.append(curr.data)
				curr = curr.right
			else:
				temp = curr.left
				while temp.right and temp.right != curr:
					temp = temp.right
				if not temp.right:
					temp.right = curr
					curr = curr.left
				elif temp.right == curr:
					result.append(curr.data)
					temp.right = None
					curr = curr.right
		return result


class Solution:

	def inOrder(self, root):
		q = []
		q.append(root)
		ans = []
		cur = root
		while q:
			while cur:
				if cur.left:
					q.append(cur.left)
				cur = cur.left
			p = q.pop()
			ans.append(p.data)
			if p.right:
				cur = p.right
				q.append(p.right)
		return ans


class Solution:

	def inOrder(self, root):
		self.res = []

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


class Solution:

	def inOrder(self, root):
		if not root:
			return
		stck = []
		res = []
		node = root
		while stck or node:
			if node:
				stck.append(node)
				node = node.left
			else:
				node = stck.pop()
				res.append(node.data)
				node = node.right
		return res


class Solution:

	def inOrder(self, root):
		result = []
		from collections import deque
		s = deque()
		node = root
		while True:
			if node:
				s.append(node)
				node = node.left
			else:
				if len(s) == 0:
					return result
				popped = s.pop()
				result.append(popped.data)
				node = popped.right


class Solution:

	def inOrder(self, root):
		if root is None:
			return []
		queue = []
		res = []
		temp = root
		while True:
			if temp is not None:
				queue.append(temp)
				temp = temp.left
			elif queue:
				temp = queue.pop()
				res.append(temp.data)
				temp = temp.right
			else:
				break
		return res


class Solution:

	def inOrder(self, root):
		inorder = []
		stack = []
		node = root
		while True:
			if node != None:
				stack.append(node)
				node = node.left
			else:
				if not stack:
					break
				node = stack.pop()
				inorder.append(node.data)
				node = node.right
		return inorder


class Solution:

	def inOrder(self, root):
		current = root
		stack = []
		ans = []
		while True:
			if current:
				stack.append(current)
				current = current.left
			elif stack:
				ele = stack.pop()
				if ele is None:
					continue
				ans.append(ele.data)
				current = ele.right
			else:
				break
		return ans


class Solution:

	def inOrder(self, root):
		visited = {}
		stack = [root]
		ans = []
		while stack:
			ele = stack.pop()
			if ele is None:
				continue
			if ele in visited:
				ans.append(ele.data)
			else:
				visited[ele] = True
				stack.append(ele.right)
				stack.append(ele)
				stack.append(ele.left)
		return ans


class Solution:

	def inOrder(self, root):
		stack = []
		ans = []
		while 1:
			if root != None:
				stack.append(root)
				root = root.left
			else:
				if not stack:
					break
				node = stack.pop()
				ans.append(node.data)
				root = node.right
		return ans


class Solution:

	def inOrder(self, root):
		st = []
		op = []
		while root or st:
			while root:
				st.append(root)
				root = root.left
			root = st.pop()
			op.append(root.data)
			root = root.right
		return op


class Solution:
	from collections import deque

	def inOrder(self, root):
		stack = deque()
		l = []
		while True:
			if root != None:
				stack += [root]
				root = root.left
			else:
				if len(stack) == 0:
					break
				root = stack[-1]
				stack.pop()
				l += [root.data]
				root = root.right
		return l


class Solution:

	def inOrder(self, root):
		stack = []
		vec = []
		temp = root
		while stack or temp:
			while temp:
				stack.append(temp)
				temp = temp.left
			else:
				if stack == None:
					break
				temp = stack.pop()
				vec.append(temp.data)
				temp = temp.right
		return vec


class Solution:

	def inOrder(self, root):
		if root is None:
			return
		q = []
		c = []
		curr = root
		while curr:
			q.append(curr)
			curr = curr.left
		while len(q) > 0:
			curr = q.pop()
			c.append(curr.data)
			curr = curr.right
			while curr:
				q.append(curr)
				curr = curr.left
		return c


class Solution:

	def inOrder(self, root):
		stack = []
		curr = root
		res = []
		while curr != None or len(stack) > 0:
			while curr != None:
				stack.append(curr)
				curr = curr.left
			curr = stack.pop()
			res.append(curr.data)
			curr = curr.right
		return res


class Solution:

	def inOrder(self, root):
		cur = root
		nodeStack = []
		ans = []
		while True:
			if cur != None:
				nodeStack.append(cur)
				cur = cur.left
			elif nodeStack:
				cur = nodeStack.pop()
				ans.append(cur.data)
				cur = cur.right
			else:
				break
		return ans


class Solution:

	def inOrder(self, root):
		left = []
		right = []
		output = []
		if root.left:
			left = [root.left]
			root.left = None
		if root.right:
			right = [root.right]
			root.right = None
		right.append(root)
		while left or right:
			while left:
				item = left.pop()
				if item.left:
					left.append(item.left)
					item.left = None
				if item.right:
					right.append(item.right)
					item.right = None
				right.append(item)
			item = right.pop()
			if item.left:
				left.append(item.left)
				item.left = None
				if item.right:
					right.append(item.right)
					item.right = None
				right.append(item)
			else:
				output.append(item.data)
				if item.right:
					right.append(item.right)
					item.right = None
		return output


class Solution:

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


class Solution:

	def inOrder(self, root):
		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:
				pre.append(stack[-1][0].data)
				stack[-1][1] += 1
				if stack[-1][0].right:
					stack.append([stack[-1][0].right, 1])
			else:
				stack.pop()
		return pre


class Solution:

	def inOrder(self, root):
		if root == None:
			return
		q = root
		st = []
		res = []
		while q or st:
			while q:
				st.append(q)
				q = q.left
			q = st.pop()
			res.append(q.data)
			q = q.right
		return res


class Solution:

	def inOrder(self, root):
		from collections import deque
		stack = deque()
		arr = []
		curr = root
		while True:
			if curr:
				stack.append(curr)
				curr = curr.left
			else:
				if len(stack) == 0:
					return arr
				n = stack.pop()
				arr.append(n.data)
				curr = n.right


class Solution:

	def inOrder(self, root):
		q = []
		c = root
		res = []
		q.append(c)
		c = c.left
		while True:
			if c:
				q.append(c)
				c = c.left
			if not c:
				if len(q):
					c = q.pop()
					res.append(c.data)
					c = c.right
				else:
					break
		return res


class Solution:

	def inOrder(self, root):
		queue = [root]
		visited = {}
		output = []
		while len(queue) > 0:
			x = queue[-1]
			if x not in visited:
				visited[x] = 1
				if x.left:
					queue.append(x.left)
			else:
				output.append(x.data)
				queue.pop()
				if x.right:
					queue.append(x.right)
		return output


class Solution:

	def inOrder(self, root):
		list1 = []
		self.Result(root, list1)
		return list1

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