Given a Binary Tree, find the In-Order Traversal of it.
Example 1:
Input:
       1
     /  \
    3    2
Output: 3 1 2
Example 2:
Input:
        10
     /      \ 
    20       30 
  /    \    /
 40    60  50
Output: 40 20 60 10 50 30
Your Task:
You don't need to read input or print anything. Your task is to complete the function inOrder() that takes root node of the tree as input and returns a list containing the In-Order 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^{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 inorder traversal of the tree. 
class Solution:
    def InOrder(self,root):
        # code here


Solutions:
class Solution:

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

	def InOrder(self, root):
		ans = []
		self.solve(root, ans)
		return ans


class Solution:

	def InOrderHelper(self, root, inorder):
		if root is None:
			return []
		self.InOrderHelper(root.left, inorder)
		inorder.append(root.data)
		self.InOrderHelper(root.right, inorder)
		return inorder

	def InOrder(self, root):
		return self.InOrderHelper(root, [])


class Solution:

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

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


class Solution:

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

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


class Solution:

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


class Solution:

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

	def InOrder(self, root):
		res = list()
		self.inorder(root, res)
		return res


class Solution:

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


class Solution:

	def InOrder(self, root):
		ans = []
		if root is None:
			return ans
		else:
			ans += self.InOrder(root.left)
			ans.append(root.data)
			ans += self.InOrder(root.right)
			return ans


class Solution:

	def __init__(self):
		self.arr = []

	def InOrder(self, root):
		if root:
			self.InOrder(root.left)
			self.arr.append(root.data)
			self.InOrder(root.right)
		return self.arr


class Solution:

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


class Solution:

	def InOrder(self, root):
		stack = []
		ans = []
		node = root
		while True:
			if node:
				stack.append(node)
				node = node.left
			else:
				if len(stack) == 0:
					break
				node = stack.pop()
				ans.append(node.data)
				node = node.right
		return ans


class Solution:

	def ino(self, root, s):
		if root == None:
			return
		self.ino(root.left, s)
		s.append(root.data)
		self.ino(root.right, s)

	def InOrder(self, root):
		s = []
		self.ino(root, s)
		return s


class Solution:

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


class Solution:

	def InOrder(self, root):
		t = root
		ans = []

		def traverse(t, ans):
			if t is not None:
				if t.left is not None:
					traverse(t.left, ans)
				ans.append(t.data)
				if t.right is not None:
					traverse(t.right, ans)
		traverse(t, ans)
		return ans


class Solution:

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


class Solution:

	def sol(self, root, rev):
		if root != None:
			self.sol(root.left, rev)
			rev.append(root.data)
			self.sol(root.right, rev)

	def InOrder(self, root):
		rev = []
		self.sol(root, rev)
		return rev


class Solution:

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

	def InOrder(self, root):
		l = []
		self.solve(root, l)
		return l


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

class Solution:

	def InOrder(self, root):
		ans_lst = []
		return cal_Inorder(root, ans_lst)


class Solution:

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


class Solution:

	def InOrder(self, root):
		lst = []

		def fun(root):
			if root:
				fun(root.left)
				lst.append(root.data)
				fun(root.right)
		fun(root)
		return lst


class Solution:

	def InOrder(self, root):
		trav = []

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


class Solution:

	def InOrder(self, root):

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


class Solution:

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

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


class Solution:

	def InOrder(self, root):
		result = []
		if root.left:
			result += self.InOrder(root.left)
		result.append(root.data)
		if root.right:
			result += self.InOrder(root.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):
		ls = []

		def tree(root):
			if root:
				tree(root.left)
				ls.append(root.data)
				tree(root.right)
		tree(root)
		return ls


class Solution:

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


class Solution:

	def InOrder(self, root):
		tr_left = []
		tr_right = []
		if root.left != None:
			tr_left = self.InOrder(root.left)
		if root.right != None:
			tr_right = self.InOrder(root.right)
		ret = []
		if len(tr_left) != 0:
			ret += tr_left
		ret.append(root.data)
		if len(tr_right) != 0:
			ret += tr_right
		return ret


class Solution:

	def InOrder(self, root):
		if root is None:
			return
		t = root
		a = []
		ans = []
		while True:
			if t:
				a.append(t)
				t = t.left
			else:
				if len(a) == 0:
					break
				t = a.pop()
				ans.append(t.data)
				t = t.right
		return ans


class Solution:

	def InOrder(self, root):
		arr = []
		self.solve(root, arr)
		return arr

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


class Solution:

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


class Solution:

	def Inorder_x(self, arr, root):
		if root == None:
			return
		self.Inorder_x(arr, root.left)
		arr.append(root.data)
		self.Inorder_x(arr, root.right)

	def InOrder(self, root):
		arr = []
		self.Inorder_x(arr, root)
		return arr


class Solution:

	def InOrder(self, root):
		inorder = []
		if not root:
			return inorder
		st = deque()
		node = root
		while True:
			if node:
				st.append(node)
				node = node.left
			else:
				if len(st) == 0:
					break
				node = st.pop()
				inorder.append(node.data)
				node = node.right
		return inorder


class Solution:

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


class Solution:

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


class Solution:

	def InOrder(self, root):
		mylist = []
		ans = self.InorderHelper(root, mylist)
		y = []
		if ans == -1:
			y.append(-1)
			return y
		return ans

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


class Solution:

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

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


class Solution:

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


class Solution:

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


class Solution:

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

		def inn(root):
			if root is None:
				return
			inn(root.left)
			l.append(root.data)
			inn(root.right)
		inn(root)
		return l


class Solution:

	def InOrder(self, root):
		if root is None:
			return
		stack = []
		result = []
		current = root
		while stack or current:
			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):
		result = []

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


class Solution:

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

	def InOrder(self, root):
		return self.helper(root, [])


class Solution:

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


class Solution:

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


class Solution:

	def Inorder_util(self, root, arr):
		if not root:
			return
		self.Inorder_util(root.left, arr)
		arr.append(root.data)
		self.Inorder_util(root.right, arr)

	def InOrder(self, root):
		arr = []
		self.Inorder_util(root, arr)
		return arr


class Solution:

	def inorderTraversalUtil(self, root, ans):
		if root:
			self.inorderTraversalUtil(root.left, ans)
			ans.append(root.data)
			self.inorderTraversalUtil(root.right, ans)

	def InOrder(self, root):
		ans = []
		self.inorderTraversalUtil(root, ans)
		return ans


class Solution:

	def InOrder(self, root):
		z = []

		def I(root, z):
			if root:
				I(root.left, z)
				z.append(root.data)
				I(root.right, z)
		I(root, z)
		return z


class Solution:

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

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


class Solution:

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

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


class Solution:

	def InOrder(self, root):
		return self.InOrderHelper(root)

	def InOrderHelper(self, root):
		if root:
			if root.left and root.right:
				return self.InOrderHelper(root.left) + [root.data] + self.InOrderHelper(root.right)
			elif root.left:
				return self.InOrderHelper(root.left) + [root.data]
			elif root.right:
				return [root.data] + self.InOrderHelper(root.right)
			else:
				return [root.data]
		else:
			return []


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def __init__(self):
		self.stack = []

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


class Solution:

	def InOrder(self, root):
		res = []
		stack = []
		cur = root
		while cur or stack:
			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):

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


class Solution:

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

	def InOrder(self, root):
		stack = []
		node = root
		ans = []
		while len(stack) != 0 or node != None:
			if node == None:
				node = stack.pop()
				ans.append(node.data)
				node = node.right
			else:
				stack.append(node)
				node = node.left
		return ans


class Solution:

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

	def InOrder(self, root):
		solu = []
		self.rec_sol(root, solu)
		return solu