Given a binary tree, find its preorder traversal.
Example 1:
Input:
        1      
      /          
    4    
  /    \   
4       2
Output: 1 4 4 2 
Example 2:
Input:
       6
     /   \
    3     2
     \   / 
      1 2
Output: 6 3 1 2 2 
Your Task:
You just have to complete the function preorder() which takes the root node of the tree as input and returns an array containing the preorder traversal of the tree.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= Number of nodes <= 10^{4}
0 <= Data of a node <= 10^{5}

Difficulty: EASY
Tags: Tree algorithms

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

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 preorder traversal of the tree.
def preorder(root):
   
    # code here

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

def preorder(root):
	ans = []
	solve(root, ans)
	return ans


def preorderHelper(root, preorderList):
	if root is None:
		return []
	preorderList.append(root.data)
	preorderHelper(root.left, preorderList)
	preorderHelper(root.right, preorderList)
	return preorderList

def preorder(root):
	return preorderHelper(root, [])


def preorder(root):
	a = []

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


def preorder(root):
	ans = []

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


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


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

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


def preorderBT(root, result):
	if root is not None:
		result.append(root.data)
		preorderBT(root.left, result=result)
		preorderBT(root.right, result=result)

def preorder(root):
	result = []
	preorderBT(root, result)
	return result


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

def preorder(root):
	ans = []
	dfs(root, ans)
	return ans


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


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

def preorder(root):
	arr = list()
	PreOrder(root, arr)
	return arr


def preorder(root):
	if root is None:
		return []
	traversal = []
	preorderUtil(root, traversal)
	return traversal

def preorderUtil(root, traversal):
	if root is None:
		return
	traversal.append(root.data)
	preorderUtil(root.left, traversal)
	preorderUtil(root.right, traversal)


def preorder(root):
	list = []

	def sample(root):
		if root == None:
			return
		list.append(root.data)
		sample(root.left)
		sample(root.right)
	sample(root)
	return list


def preorder(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


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


def preorder(root):
	res = []

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


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


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


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


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


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


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


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


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

def preorder(root):
	stack = []
	pre(root, stack)
	return stack


def preorder(root):
	traversal = []
	if root is not None:
		traversal.append(root.data)
		traversal.extend(preorder(root.left))
		traversal.extend(preorder(root.right))
	return traversal


def preorder(root):
	res = []
	st = []
	while True:
		if root:
			st.append(root)
			res.append(root.data)
			root = root.left
		elif len(st):
			root = st.pop()
			root = root.right
		else:
			break
	return res


def preorder(root):
	res = []
	solution(root, res)
	return res

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


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

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


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

def preorder(root):
	ans_lst = []
	return output(root, ans_lst)


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


def preorder(root):
	arr = []

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


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


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

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


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


def preorder(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


def preorder(root):
	if root is None:
		return []
	left_node = preorder(root.left)
	right_node = preorder(root.right)
	return [root.data] + left_node + right_node


def preorder(root):
	stack = []
	preorder = []
	while True:
		if root:
			stack.append(root)
			preorder.append(root.data)
			root = root.left
		elif stack:
			root = stack.pop()
			root = root.right
		else:
			break
	return preorder


def preorder(root):
	if root is None:
		return
	a = [root]
	ans = []
	while a:
		x = a.pop()
		ans.append(x.data)
		if x.right:
			a.append(x.right)
		if x.left:
			a.append(x.left)
	return ans


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

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


def preorder(root):

	def help(root, res):
		if root is not None:
			res.append(root.data)
			help(root.left, res)
			help(root.right, res)
		return res
	res = help(root, [])
	return res


def preorder(root):
	res = []
	preorder_res(res, root)
	return res

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


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

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


def preorder(root):
	if not root:
		return []
	st = deque()
	st.append(root)
	preorder = []
	while len(st) != 0:
		node = st.pop()
		preorder.append(node.data)
		if node.right:
			st.append(node.right)
		if node.left:
			st.append(node.left)
	return preorder


def preorder(root):
	curr = root
	stack = []
	ans = []
	while curr or stack:
		if curr:
			ans.append(curr.data)
			stack.append(curr)
			curr = curr.left
		else:
			node = stack.pop()
			if node.right:
				curr = node.right
	return ans


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


def preorder(root):
	ans = []

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


def preorder(root):
	res = []
	stack = []
	stack.append(root)
	while len(stack) != 0:
		node = stack.pop()
		res.append(node.data)
		if node.right:
			stack.append(node.right)
		if node.left:
			stack.append(node.left)
	return res


def preorder(root):
	result = []
	from collections import deque
	stack = deque()
	stack.append(root)
	while len(stack):
		node = stack.pop()
		result.append(node.data)
		if node.right:
			stack.append(node.right)
		if node.left:
			stack.append(node.left)
	return result


def preorder(root):
	global pre
	pre = []
	recpre(root)
	return pre

def recpre(x):
	if x is not None:
		pre.append(x.data)
		recpre(x.left)
		recpre(x.right)


def preorder(root):
	if not root:
		return
	stack = []
	result = []
	stack.append(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


def preorder(root):
	res = []

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


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


def preorder(root):
	result = []

	def preorderTraversal(node):
		if not node:
			return result
		result.append(node.data)
		preorderTraversal(node.left)
		preorderTraversal(node.right)
	preorderTraversal(root)
	return result


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


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

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


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


def preorder(root):
	ans = []

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


def preorder(root):
	a = list()
	v = [root]
	while v:
		n = v.pop()
		a.append(n.data)
		if n.right:
			v.append(n.right)
		if n.left:
			v.append(n.left)
	return a


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

def preorder(root):
	l = []
	PreProcess(root, l)
	return l


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

def preorder(root):
	res = []
	return PreOrder(root, res)


def preorder(root):
	res = []

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


def preorder(root):
	l = []

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


def preorder(root):
	list = listL = listR = []
	list.append(root.data)
	if root.left is not None:
		listL = preorder(root.left)
		list.extend(listL)
	if root.right is not None:
		listR = preorder(root.right)
		list.extend(listR)
	return list