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

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
'''

# Node Class:

class Node:

    def init(self,val):

        self.data = val

        self.left = None

        self.right = None

'''



class Solution:

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

    def preOrder(self, root):

        # code here

Solutions:
class Solution:

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


class Solution:

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

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


class Solution:

	def preOrder(self, root):
		a = list()
		v = list()
		v.append(root)
		while len(v) > 0:
			n = v.pop()
			a.append(n.data)
			if n.right:
				v.append(n.right)
			if n.left:
				v.append(n.left)
		return a


class Solution:

	def preOrder(self, root):
		s = [root]
		res = []
		while len(s) > 0:
			n = s.pop()
			res.append(n.data)
			if n.right:
				s.append(n.right)
			if n.left:
				s.append(n.left)
		return res


class Solution:

	def preOrder(self, root):
		st = []
		if root == None:
			return st
		ans = []
		st.append(root)
		while len(st) != 0:
			x = st.pop()
			ans.append(x.data)
			if x.right != None:
				st.append(x.right)
			if x.left != None:
				st.append(x.left)
		return ans


class Solution:

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


class Solution:

	def preOrder(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.left, False))
				stack.append((node, True))
		return ans


class Solution:

	def preOrder(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.left, False))
					s.append((node, True))
		return res


class Solution:

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

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


class Solution:

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


class Solution:

	def preOrder(self, root):
		st = []
		st.append(root)
		final = []
		while st:
			curr = st.pop()
			final.append(curr.data)
			if curr.right:
				st.append(curr.right)
			if curr.left:
				st.append(curr.left)
		return final


class Solution:

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


class Solution:

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

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def preOrder(self, root):
		st = [root]
		res = []
		while st:
			node = st.pop()
			res.append(node.data)
			if node.right:
				st.append(node.right)
			if node.left:
				st.append(node.left)
		return res


class Solution:

	def preOrder(self, root):
		if root is None:
			return
		node = []
		node.append(root)
		res = []
		while len(node) > 0:
			n = node.pop()
			res.append(n.data)
			if n.right is not None:
				node.append(n.right)
			if n.left is not None:
				node.append(n.left)
		return res


class Solution:

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


class Solution:

	def preOrder(self, root):
		l = []
		if root == None:
			return l
		l.append(root)
		k = []
		while len(l) > 0:
			t = l.pop()
			k.append(t.data)
			if t.right:
				l.append(t.right)
			if t.left:
				l.append(t.left)
		return k


class Solution:

	def preOrder(self, root):
		(l1, l2) = ([], [])
		while 1:
			if root != None:
				l1.append(root.data)
				l2.append(root)
				root = root.left
			elif l2:
				t = l2.pop()
				root = t.right
			else:
				break
		return l1


from collections import deque

class Solution:

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


class Solution:

	def preOrder(self, root):
		res = []

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


class Solution:

	def preOrder(self, root):
		b = []
		Solution.bst(root, b)
		return b

	def bst(root, b):
		b.append(root.data)
		if root.left:
			Solution.bst(root.left, b)
		if root.right:
			Solution.bst(root.right, b)


class Solution:

	def preOrder(self, root):
		l = []
		res = []
		l.append(root)
		while len(l):
			t = l.pop()
			res.append(t.data)
			if t.right:
				l.append(t.right)
			if t.left:
				l.append(t.left)
		return res


class Solution:

	def preOrder(self, root):
		st = []
		res = []
		st.append(root)
		while len(st) != 0:
			it = st.pop()
			res.append(it.data)
			if it.right:
				st.append(it.right)
			if it.left:
				st.append(it.left)
		return res


class Solution:

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


class Solution:

	def preOrder(self, root):
		stck = []
		stck.append(root)
		res = []
		while stck:
			popped = stck.pop(-1)
			res.append(popped.data)
			if popped.right:
				stck.append(popped.right)
			if popped.left:
				stck.append(popped.left)
		return res


class Solution:

	def preOrder(self, root):
		stack = [[root, False]]
		ans = []
		while stack:
			(node, left_accessed) = stack[-1]
			if left_accessed == False:
				ans.append(node.data)
				stack[-1][-1] = True
				if node.left:
					stack.append([node.left, False])
			else:
				stack.pop()
				if node.right:
					stack.append([node.right, False])
		return ans


class Solution:

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


class Solution:

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


class Solution:

	def preOrder(self, root):
		pre_order = []
		curr = root
		if curr == None:
			return pre_order
		s = []
		s.append(curr)
		while len(s) > 0:
			top_node = s.pop()
			pre_order.append(top_node.data)
			if top_node.right:
				s.append(top_node.right)
			if top_node.left:
				s.append(top_node.left)
		return pre_order


class Solution:

	def preOrder(self, root):
		lis = []
		ans = []
		cur = root
		while lis or cur:
			while cur:
				lis.append(cur)
				ans.append(cur.data)
				cur = cur.left
			cur = lis.pop()
			cur = cur.right
		return ans


from collections import deque

class Solution:

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


class Solution:

	def preOrder(self, root):
		current = root
		stack = [root]
		while stack:
			crr = stack.pop()
			print(crr.data, end=' ')
			if crr.right:
				stack.append(crr.right)
			if crr.left:
				stack.append(crr.left)
		return []


class Solution:

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

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


class Solution:

	def preOrder(self, root):
		li = []
		stack = []
		li.append(root)
		while li:
			node = li.pop()
			stack.append(node.data)
			if node.right != None:
				li.append(node.right)
			if node.left != None:
				li.append(node.left)
		return stack


class Solution:

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


class Solution:

	def preOrder(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
					res.append(curr.data)
					curr = curr.left
				else:
					prev.right = None
					curr = curr.right
		return res


from collections import deque

class Solution:

	def preOrder(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
					ans.append(curr.data)
					curr = curr.left
				else:
					node.right = None
					curr = curr.right
		return ans


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def preOrder(self, root):
		s = [root]
		a = []
		if root is None:
			return
		while len(s) > 0:
			n = s.pop()
			a.append(n.data)
			if n.right:
				s.append(n.right)
			if n.left:
				s.append(n.left)
		return a


from collections import deque

class Solution:

	def preOrder(self, root):
		answer = []
		if root:
			stack = deque()
			stack.append(root)
			while len(stack):
				temp = stack.pop()
				answer.append(temp.data)
				if temp.right:
					stack.append(temp.right)
				if temp.left:
					stack.append(temp.left)
		return answer


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def preOrder(self, root):
		if root == [] or root == None:
			return []

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


class Solution:
	from collections import deque

	def preOrder(self, root):
		d = deque()
		l = []
		d += [root]
		while len(d) != 0:
			f = d.pop()
			l += [f.data]
			if f.right != None:
				d += [f.right]
			if f.left != None:
				d += [f.left]
		return l


class Solution:

	def preOrder(self, root):
		st1 = []
		vec = []
		st1.append(root)
		while st1:
			root = st1[-1]
			st1.pop()
			if root.right:
				st1.append(root.right)
			if root.left:
				st1.append(root.left)
			vec.append(root.data)
		return vec


class Solution:

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


class Solution:

	def preOrder(self, root):
		output = []
		stack = [root]
		while stack:
			head = stack.pop()
			if head == None:
				continue
			output.append(head.data)
			stack.append(head.right)
			stack.append(head.left)
		return output


class Solution:

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


class Solution:

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


class Solution:

	def preOrder(self, root):
		stack = []
		stack.append(root)
		cur = None
		res = []
		while len(stack) != 0:
			cur = stack[-1]
			res.append(cur.data)
			stack.pop()
			if cur.right != None:
				stack.append(cur.right)
			if cur.left != None:
				stack.append(cur.left)
		return res


class Solution:

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


class Solution:

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


class Solution:

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

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


class Solution:

	def preOrder(self, root):
		nodes = []

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


class Solution:

	def preOrder(self, A):
		stack = []
		curr = A
		ans = []
		while stack or curr != None:
			while curr != None:
				ele = curr.data
				ans.append(ele)
				stack.append(curr)
				curr = curr.left
			curr = stack[-1]
			stack.pop()
			curr = curr.right
		return ans


class Solution:

	def preOrder(self, root):
		from collections import deque
		stack = deque()
		arr = []
		if not root:
			return []
		stack.append(root)
		while len(stack):
			node = stack.pop()
			arr.append(node.data)
			if node.right:
				stack.append(node.right)
			if node.left:
				stack.append(node.left)
		return arr


class Solution:

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

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


class Solution:

	def preOrder(self, root):
		if not root:
			return
		ans = []
		nodes = []
		nodes.append(root)
		cur = root
		while nodes:
			cur = nodes.pop()
			ans.append(cur.data)
			if cur.right:
				nodes.append(cur.right)
			if cur.left:
				nodes.append(cur.left)
		return ans


class Solution:

	def preOrder(self, root):
		q = []
		q.append(root)
		res = []
		while len(q) > 0:
			c = q.pop(-1)
			if c:
				res.append(c.data)
			if c and c.right:
				q.append(c.right)
			if c and c.left:
				q.append(c.left)
		return res


class Solution:

	def preOrder(self, root):
		if root == None:
			return
		stack = []
		final = []
		stack.append(root)
		while len(stack) != 0:
			val = stack.pop()
			final.append(val.data)
			if val.right:
				stack.append(val.right)
			if val.left:
				stack.append(val.left)
		return final


class Solution:

	def preOrder(self, root):
		k = []

		def preorder(root, k):
			if not root:
				return
			k.append(root.data)
			preorder(root.left, k)
			preorder(root.right, k)
		preorder(root, k)
		return k


class Solution:

	def preOrder(self, r):
		s = []
		r = []
		s.append(root)
		while len(s):
			t = s[-1]
			r.append(t.data)
			s.pop()
			if t.right:
				s.append(t.right)
			if t.left:
				s.append(t.left)
		return r


class Solution:

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