Given two BSTs, return elements of both BSTs in sorted form.
Example 1:
Input:
BST1:
       5
     /   \
    3     6
   / \
  2   4  
BST2:
        2
      /   \
     1     3
            \
             7
            /
           6
Output: 1 2 2 3 3 4 5 6 6 7
Explanation: 
After merging and sorting the
two BST we get 1 2 2 3 3 4 5 6 6 7.
Example 2:
Input:
BST1:
       12
     /   
    9
   / \    
  6   11
BST2:
      8
    /  \
   5    10
  /
 2
Output: 2 5 6 8 9 10 11 12
Explanation: 
After merging and sorting the
two BST we get 2 5 6 8 9 10 11 12.
Your Task:
You don't need to read input or print anything. Your task is to complete the function merge() which takes roots of both the BSTs as its input and returns an array of integers denoting the node values of both the BSTs in a sorted order.
Expected Time Complexity: O(M+N) where M and N are the sizes of the two BSTs.
Expected Auxiliary Space: O(Height of BST1 + Height of BST2 + M + N(for storing the answer)).
Constraints:
1 ≤ Number of Nodes ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

'''



class Solution:

    

    #Function to return a list of integers denoting the node 

    #values of both the BST in a sorted order.

    def merge(self, root1, root2):

        #code here.

Solutions:
class Solution:

	def merge(self, root1, root2):
		req = []
		(lst1, lst2) = ([], [])
		while root1:
			lst1.append(root1)
			root1 = root1.left
		while root2:
			lst2.append(root2)
			root2 = root2.left
		(x, y) = (get(lst1), get(lst2))
		while x and y:
			if x.data > y.data:
				req.append(y.data)
				y = get(lst2)
			else:
				req.append(x.data)
				x = get(lst1)
		while x:
			req.append(x.data)
			x = get(lst1)
		while y:
			req.append(y.data)
			y = get(lst2)
		return req

def get(lst):
	if not lst:
		return None
	x = lst.pop()
	if x.right:
		temp = x.right
		while temp:
			lst.append(temp)
			temp = temp.left
	return x


class Solution:

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

	def merge(self, root1, root2):
		l = []
		self.ele_out(root1, l)
		self.ele_out(root2, l)
		return sorted(l)


class Solution:

	def inorder(self, p, li):
		if p:
			self.inorder(p.left, li)
			li.append(p.data)
			self.inorder(p.right, li)

	def mergify(self, t1=None, t2=None):
		li = []
		li1 = []
		if t1 and t2:
			self.inorder(t1, li)
			self.inorder(t2, li1)
		elif t1:
			self.inorder(t1, li)
		elif t2:
			self.inorder(t2, li1)
		i = j = k = 0
		result = [None] * (len(li) + len(li1))
		while i < len(li) and j < len(li1):
			if li[i] <= li1[j]:
				result[k] = li[i]
				i += 1
			else:
				result[k] = li1[j]
				j += 1
			k += 1
		while i < len(li):
			result[k] = li[i]
			i += 1
			k += 1
		while j < len(li1):
			result[k] = li1[j]
			k += 1
			j += 1
		return result

	def merge(self, t1, t2):
		if t1 is None and t2 is None:
			return
		elif t1 is None:
			return self.mergify(t2)
		elif t2 is None:
			return self.mergify(t1)
		else:
			return self.mergify(t1, t2)


class Solution:

	def merge(self, root1, root2):
		stack1 = []
		stack2 = []
		result = []
		while True:
			while root1 or root2:
				if root1:
					stack1.append(root1)
					root1 = root1.left
				if root2:
					stack2.append(root2)
					root2 = root2.left
			if stack1 or stack2:
				if not stack1:
					root2 = stack2.pop()
					result.append(root2.data)
					root2 = root2.right
				elif not stack2:
					root1 = stack1.pop()
					result.append(root1.data)
					root1 = root1.right
				elif stack1[-1].data < stack2[-1].data:
					root1 = stack1.pop()
					result.append(root1.data)
					root1 = root1.right
				else:
					root2 = stack2.pop()
					result.append(root2.data)
					root2 = root2.right
			else:
				break
		return result


class Solution:

	def merge(self, root1, root2):
		(stack1, stack2) = ([], [])
		res = []
		(cur1, cur2) = (root1, root2)
		while cur1:
			stack1.append(cur1)
			cur1 = cur1.left
		while cur2:
			stack2.append(cur2)
			cur2 = cur2.left
		while stack1 or stack2:
			(item1, item2) = (None, None)
			if stack1:
				item1 = stack1[-1]
			if stack2:
				item2 = stack2[-1]
			if item1 and item2:
				if item1.data <= item2.data:
					res.append(item1.data)
					stack1.pop()
					item2 = None
				else:
					res.append(item2.data)
					stack2.pop()
					item1 = None
			elif item1:
				res.append(item1.data)
				stack1.pop()
			else:
				res.append(item2.data)
				stack2.pop()
			if item1 and item1.right:
				item1 = item1.right
				while item1:
					stack1.append(item1)
					item1 = item1.left
			if item2 and item2.right:
				item2 = item2.right
				while item2:
					stack2.append(item2)
					item2 = item2.left
		return res


class Solution:

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

	def merge(self, root1, root2):
		arr = []
		self.inorder(root1, arr)
		self.inorder(root2, arr)
		arr.sort()
		return arr


from collections import deque

class Solution:

	def merge(self, root1, root2):
		ans = []
		stack1 = []
		stack2 = []
		(curr1, curr2) = (root1, root2)
		while True:
			if curr1 is not None or curr2 is not None:
				if curr1 is not None:
					stack1.append(curr1)
					curr1 = curr1.left
				if curr2 is not None:
					stack2.append(curr2)
					curr2 = curr2.left
			else:
				top1 = stack1[-1] if len(stack1) != 0 else None
				top2 = stack2[-1] if len(stack2) != 0 else None
				if top1 is None and top2 is None:
					break
				elif top1 is None:
					stack2.pop()
					ans.append(top2.data)
					curr2 = top2.right
				elif top2 is None:
					stack1.pop()
					ans.append(top1.data)
					curr1 = top1.right
				elif top1.data < top2.data:
					stack1.pop()
					ans.append(top1.data)
					curr1 = top1.right
				else:
					stack2.pop()
					ans.append(top2.data)
					curr2 = top2.right
		return ans


class Solution:

	def merge(self, root1, root2):
		(p1, p2) = ([], [])

		def inorder(root, pos):
			if not root:
				return None
			inorder(root.left, pos)
			pos.append(root.data)
			inorder(root.right, pos)
		inorder(root1, p1)
		inorder(root2, p2)
		res = p1 + p2
		res.sort()
		return res


class Solution:

	def merge(self, root1, root2):
		stack1 = []
		node1 = root1
		stack2 = []
		node2 = root2
		result = []
		while node1 or stack1 or node2 or stack2:
			while node1:
				stack1.append(node1)
				node1 = node1.left
			while node2:
				stack2.append(node2)
				node2 = node2.left
			if not stack2 or (stack1 and stack1[-1].data < stack2[-1].data):
				node1 = stack1.pop()
				result.append(node1.data)
				node1 = node1.right
			else:
				node2 = stack2.pop()
				result.append(node2.data)
				node2 = node2.right
		return result


class Solution:

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

	def merge_arrays(self, arr1, arr2):
		n1 = len(arr1)
		n2 = len(arr2)
		if n1 == 0:
			return arr2
		if n2 == 0:
			return arr1
		arr3 = [-1] * (n1 + n2)
		i = j = k = 0
		while i < n1 and j < n2:
			if arr1[i] <= arr2[j]:
				arr3[k] = arr1[i]
				i += 1
			else:
				arr3[k] = arr2[j]
				j += 1
			k += 1
		while i < n1:
			arr3[k] = arr1[i]
			i += 1
			k += 1
		while j < n2:
			arr3[k] = arr2[j]
			j += 1
			k += 1
		return arr3

	def create_bst(self, arr, start, end):
		if start > end:
			return
		mid = start + (end - start) // 2
		root = Node(arr[mid])
		root.left = self.create_bst(arr, start, mid - 1)
		root.right = self.create_bst(arr, mid + 1, end)
		return root

	def merge(self, root1, root2):
		inord_1 = []
		self.inorder(root1, inord_1)
		inord_2 = []
		self.inorder(root2, inord_2)
		arr = self.merge_arrays(inord_1, inord_2)
		return arr


class Solution:

	def merge(self, root1, root2):
		res = []
		(s1, s2, curr1, curr2) = ([], [], root1, root2)
		while curr1:
			s1.append(curr1)
			curr1 = curr1.left
		while curr2:
			s2.append(curr2)
			curr2 = curr2.left
		while s1 or s2:
			(item1, item2) = (None, None)
			if s1:
				item1 = s1[-1]
			if s2:
				item2 = s2[-1]
			if item1 and item2:
				if item1.data <= item2.data:
					res.append(item1.data)
					s1.pop()
					item2 = None
				else:
					res.append(item2.data)
					s2.pop()
					item1 = None
			elif item1:
				res.append(item1.data)
				s1.pop()
			else:
				res.append(item2.data)
				s2.pop()
			if item1 and item1.right:
				item1 = item1.right
				while item1:
					s1.append(item1)
					item1 = item1.left
			if item2 and item2.right:
				item2 = item2.right
				while item2:
					s2.append(item2)
					item2 = item2.left
		return res


class Solution:

	def inorder(self, root):
		ele = []
		if root.left:
			ele += self.inorder(root.left)
		ele.append(root.data)
		if root.right:
			ele += self.inorder(root.right)
		return ele

	def merge(self, root1, root2):
		ans1 = []
		ans2 = []
		ans1 += self.inorder(root1)
		ans2 += self.inorder(root2)
		for i in ans2:
			ans1.append(i)
		ans1.sort()
		return ans1


from collections import deque

class Solution:

	def merge(self, root1, root2):
		(stk1, stk2, res) = (deque(), deque(), [])
		while root1:
			stk1.append(root1)
			root1 = root1.left
		while root2:
			stk2.append(root2)
			root2 = root2.left
		while stk1 or stk2:
			if stk1 and (not stk2 or stk1[-1].data <= stk2[-1].data):
				root1 = stk1.pop()
				res.append(root1.data)
				root1 = root1.right
				while root1:
					stk1.append(root1)
					root1 = root1.left
			else:
				root2 = stk2.pop()
				res.append(root2.data)
				root2 = root2.right
				while root2:
					stk2.append(root2)
					root2 = root2.left
		return res


class Solution:

	def merge(self, root1, root2):

		def dfs(ls, root):
			if not root:
				return None
			dfs(ls, root.left)
			ls.append(root.data)
			dfs(ls, root.right)
			return ls
		ls1 = dfs([], root1)
		ls2 = dfs([], root2)
		res = []
		i1 = 0
		i2 = 0
		while i1 < len(ls1) and i2 < len(ls2):
			if ls1[i1] < ls2[i2]:
				res.append(ls1[i1])
				i1 += 1
			else:
				res.append(ls2[i2])
				i2 += 1
		if i1 < len(ls1):
			res = res + ls1[i1:]
		if i2 < len(ls2):
			res = res + ls2[i2:]
		return res


class Solution:

	def merge(self, root1, root2):
		(first, second) = ([], [])
		while root1:
			first.append(root1)
			root1 = root1.left
		while root2:
			second.append(root2)
			root2 = root2.left
		ans = []
		while len(first) or len(second):
			if len(first) and (len(second) == 0 or first[-1].data <= second[-1].data):
				X = first.pop()
				ans += [X.data]
				if X.right:
					X = X.right
					while X:
						first.append(X)
						X = X.left
			else:
				X = second.pop()
				ans += [X.data]
				if X.right:
					X = X.right
					while X:
						second.append(X)
						X = X.left
		return ans


class Solution:

	def merge(self, root1, root2):
		inorder1 = self.inorder(root1)
		inorder2 = self.inorder(root2)
		return sorted(inorder1 + inorder2)

	def inorder(self, root):
		if not root:
			return []
		return self.inorder(root.left) + [root.data] + self.inorder(root.right)


class Solution:

	def merge(self, root1, root2):
		ans1 = []
		ans2 = []

		def find(ans, root):
			if root is None:
				return None
			find(ans, root.left)
			ans.append(root.data)
			find(ans, root.right)
		find(ans1, root1)
		find(ans2, root2)
		return sorted(ans1 + ans2)


class Solution:

	def merge(self, root1, root2):
		lst = []
		ans1 = self.preOrder(root1, lst)
		lst = []
		ans2 = self.preOrder(root2, lst)
		lst = []
		lst = ans1 + ans2
		return sorted(lst)

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


class Solution:

	def merge(self, root1, root2):
		ans1 = []
		ans2 = []
		self.inorder(root1, ans1)
		self.inorder(root2, ans2)
		return sorted(ans1 + ans2)

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


class Solution:

	def inorder(self, root):
		arr = []
		if not root:
			return arr
		arr += self.inorder(root.left)
		arr.append(root.data)
		arr += self.inorder(root.right)
		return arr

	def merge(self, root1, root2):
		arr1 = self.inorder(root1)
		arr2 = self.inorder(root2)
		i = j = 0
		sortedArr = []
		while i < len(arr1) and j < len(arr2):
			if arr1[i] < arr2[j]:
				sortedArr.append(arr1[i])
				i += 1
			else:
				sortedArr.append(arr2[j])
				j += 1
		if i < len(arr1):
			sortedArr += arr1[i:]
		if j < len(arr2):
			sortedArr += arr2[j:]
		return sortedArr


class Solution:
	arr = []
	brr = []

	def gem(self, root, brr):
		if root == None:
			return
		self.gen(root.left, brr)
		brr.append(root.data)
		self.gen(root.right, brr)

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

	def merge(self, root1, root2):
		arr = []
		brr = []
		self.gen(root1, arr)
		self.gem(root2, brr)
		i = 0
		j = 0
		ans = []
		while i < len(arr) and j < len(brr):
			if arr[i] < brr[j]:
				ans.append(arr[i])
				i += 1
			else:
				ans.append(brr[j])
				j += 1
		while i < len(arr):
			ans.append(arr[i])
			i += 1
		while j < len(brr):
			ans.append(brr[j])
			j += 1
		return ans
		return []


class Solution:

	def merge(self, root1, root2):

		def inorder(root, ino):
			if not root:
				return
			inorder(root.left, ino)
			ino.append(root.data)
			inorder(root.right, ino)
		(ino1, ino2) = ([], [])
		inorder(root1, ino1)
		inorder(root2, ino2)
		return sorted(ino1 + ino2)


class Solution:

	def merge(self, root1, root2):
		global lis
		lis = []

		def solve(root):
			if root:
				solve(root.left)
				lis.append(root.data)
				solve(root.right)
		solve(root1)
		solve(root2)
		return sorted(lis)


class Solution:

	def inorderTraversal(self, root):
		ll = []
		if root.left:
			ll += self.inorderTraversal(root.left)
		ll.append(root.data)
		if root.right:
			ll += self.inorderTraversal(root.right)
		return ll

	def merge(self, root1, root2):
		(ll1, ll2) = ([], [])
		ll1 += self.inorderTraversal(root1)
		ll2 += self.inorderTraversal(root2)
		for i in ll2:
			ll1.append(i)
		ll1.sort()
		return ll1


class Solution:

	def inorder1(self, root1):
		if root1:
			self.inorder1(root1.left)
			self.res.append(root1.data)
			self.inorder1(root1.right)

	def inorder2(self, root2):
		if root2:
			self.inorder1(root2.left)
			self.res.append(root2.data)
			self.inorder1(root2.right)

	def merge(self, root1, root2):
		self.res = []
		self.inorder1(root1)
		self.inorder2(root2)
		self.res.sort()
		return self.res


class Solution:

	def merge(self, root1, root2):

		def build_tree_stack(root):
			stack = []
			this_node = root
			while True:
				stack.append(this_node)
				if not this_node.left:
					return stack
				this_node = this_node.left

		def add_elem_to_list_admin(this_node, stack, sorted_elements_list):
			sorted_elements_list.append(this_node.data)
			stack.pop(-1)
			if this_node.right:
				stack += build_tree_stack(this_node.right)
			return (stack, sorted_elements_list)
		root1_stack = build_tree_stack(root1)
		root2_stack = build_tree_stack(root2)
		sorted_elements = []
		while root1_stack and root2_stack:
			root1_elem = root1_stack[-1]
			root2_elem = root2_stack[-1]
			if root1_elem.data < root2_elem.data:
				(root1_stack, sorted_elements) = add_elem_to_list_admin(root1_elem, root1_stack, sorted_elements)
			if root2_elem.data <= root1_elem.data:
				(root2_stack, sorted_elements) = add_elem_to_list_admin(root2_elem, root2_stack, sorted_elements)
		leftover_stack = max([root1_stack, root2_stack])
		while leftover_stack:
			this_node = leftover_stack[-1]
			(leftover_stack, sorted_elements) = add_elem_to_list_admin(this_node, leftover_stack, sorted_elements)
		return sorted_elements


from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root

class Solution:

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

	def merge(self, root1, root2):
		res = self.inorder(root1) + self.inorder(root2)
		res.sort()
		return res


class Solution:

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

	def mergeTwoSortedArrays(self, arr1, arr2):
		(i, j, res) = (0, 0, [])
		while i < len(arr1) and j < len(arr2):
			if arr1[i] < arr2[j]:
				res.append(arr1[i])
				i += 1
			else:
				res.append(arr2[j])
				j += 1
		while i < len(arr1):
			res.append(arr1[i])
			i += 1
		while j < len(arr2):
			res.append(arr2[j])
			j += 1
		return res

	def inorderToBST(self, s, e, inOrder):
		if s > e:
			return None
		mid = (s + e) // 2
		root = Node(inOrder[mid])
		root.left = self.inorderToBST(s, mid - 1, inOrder)
		root.right = self.inorderToBST(mid + 1, e, inOrder)
		return root

	def merge(self, root1, root2):
		(bst1, bst2) = ([], [])
		self.inorder(root1, bst1)
		self.inorder(root2, bst2)
		mergeArray = self.mergeTwoSortedArrays(bst1, bst2)
		return mergeArray


class Solution:

	def merge(self, root1, root2):

		def inorder(root, li):
			if not root:
				return
			inorder(root.left, li)
			li.append(root.data)
			inorder(root.right, li)
			return

		def mergeTwoSortedArr(li1, li2, ans):
			i = 0
			j = 0
			while i < len(li1) and j < len(li2):
				if li1[i] <= li2[j]:
					ans.append(li1[i])
					i += 1
				else:
					ans.append(li2[j])
					j += 1
			if i == len(li1):
				ans.extend(li2[j:])
			elif j == len(li2):
				ans.extend(li1[i:])
		li1 = []
		li2 = []
		ans = []
		inorder(root1, li1)
		inorder(root2, li2)
		mergeTwoSortedArr(li1, li2, ans)
		return ans


class Solution:

	def merge(self, root1, root2) -> list:
		result = []
		if root1:
			self._merge(root1, result)
		if root2:
			self._merge(root2, result)
		result.sort()
		return result

	def _merge(self, node, result: list) -> None:
		if node is None:
			return
		result.append(node.data)
		self._merge(node.left, result)
		self._merge(node.right, result)


class Solution:

	def merge(self, root1, root2):
		x = self.inorder(root1, []) + self.inorder(root2, [])
		x.sort()
		return x

	def inorder(self, node, a):
		if node is None:
			return
		else:
			self.inorder(node.left, a)
			a.append(node.data)
			self.inorder(node.right, a)
		return a


def recGenerator(node: Node):
	if node.left is not None:
		for value in recGenerator(node.left):
			yield value
	yield node.data
	if node.right is not None:
		for value in recGenerator(node.right):
			yield value

class Solution:

	def merge(self, root1, root2):
		a = [i for i in recGenerator(root1)]
		b = [i for i in recGenerator(root2)]
		res = []
		(Aind, Bind) = (0, 0)
		while Aind != len(a) and Bind != len(b):
			if a[Aind] > b[Bind]:
				res.append(b[Bind])
				Bind += 1
			else:
				res.append(a[Aind])
				Aind += 1
		while Aind != len(a):
			res.append(a[Aind])
			Aind += 1
		while Bind != len(b):
			res.append(b[Bind])
			Bind += 1
		return res


class Solution:

	def merge(self, root1, root2):
		lis1 = []
		lis2 = []

		def fun(root, lis):
			if root == None:
				return
			fun(root.left, lis)
			lis.append(root.data)
			fun(root.right, lis)
		fun(root1, lis1)
		fun(root2, lis2)
		for i in lis2:
			lis1.append(i)
		lis1.sort()
		return lis1


class Solution:

	def merge(self, root1, root2):
		lis1 = []
		self.sorts(root1, lis1)
		lis2 = []
		self.sorts(root2, lis2)
		lis2 = lis1 + lis2
		lis2.sort()
		return lis2

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


class Solution:

	def merge(self, root1, root2):
		x1 = []

		def traversal(root, x):
			if root is None:
				return
			else:
				traversal(root.left, x)
				x.append(root.data)
				traversal(root.right, x)
		traversal(root1, x1)
		traversal(root2, x1)
		return sorted(x1)


class Solution:

	def merge(self, r1, r2):
		sol = []
		(stk1, stk2) = ([], [])
		(f1, f2, s1, s2) = (1, 1, 1, 1)
		while f1 or f2:
			while f1 and s1:
				if r1:
					stk1.append(r1)
					r1 = r1.left
				elif stk1:
					r1 = stk1.pop()
					d1 = r1.data
					r1 = r1.right
					break
				else:
					f1 = 0
			while f2 and s2:
				if r2:
					stk2.append(r2)
					r2 = r2.left
				elif stk2:
					r2 = stk2.pop()
					d2 = r2.data
					r2 = r2.right
					break
				else:
					f2 = 0
			if f1 and f2:
				if d1 < d2:
					sol.append(d1)
					s1 = 1
					s2 = 0
				else:
					sol.append(d2)
					s1 = 0
					s2 = 1
			elif f1:
				sol.append(d1)
				s1 = 1
			elif f2:
				sol.append(d2)
				s2 = 1
		return sol


class Solution:

	def merge(self, root1, root2):

		def bele(root, a):
			if root:
				a.append(root.data)
			else:
				return
			if root.left:
				bele(root.left, a)
			if root.right:
				bele(root.right, a)
		p = []
		q = []
		bele(root1, p)
		bele(root2, q)
		p += q
		p.sort()
		return p


class Solution:

	def traversal(self, root):
		if root.left:
			yield from self.traversal(root.left)
		yield root.data
		if root.right:
			yield from self.traversal(root.right)

	def nxt(self, i):
		try:
			a = next(i)
		except StopIteration as e:
			return None
		return a

	def merge(self, root1, root2):
		i1 = self.traversal(root1)
		i2 = self.traversal(root2)
		r = []
		a = self.nxt(i1)
		b = self.nxt(i2)
		while True:
			if not a and (not b):
				break
			elif a and b:
				if a <= b:
					while a and a <= b:
						r.append(a)
						a = self.nxt(i1)
				else:
					while b and b < a:
						r.append(b)
						b = self.nxt(i2)
			elif a and (not b):
				while a:
					r.append(a)
					a = self.nxt(i1)
			elif b and (not a):
				while b:
					r.append(b)
					b = self.nxt(i2)
		return r


class Solution:

	def merge(self, root1, root2):
		inorder1 = []

		def findinorder(root):
			if root == None:
				return None
			findinorder(root.left)
			inorder1.append(root.data)
			findinorder(root.right)
		findinorder(root1)
		inorder2 = []

		def findinorder2(root):
			if root == None:
				return None
			findinorder2(root.left)
			inorder2.append(root.data)
			findinorder2(root.right)
		findinorder2(root2)
		res = []
		i = 0
		j = 0
		while i < len(inorder1) and j < len(inorder2):
			if inorder1[i] <= inorder2[j]:
				res.append(inorder1[i])
				i += 1
			else:
				res.append(inorder2[j])
				j += 1
		while i < len(inorder1):
			res.append(inorder1[i])
			i += 1
		while j < len(inorder2):
			res.append(inorder2[j])
			j += 1
		return res


class Solution:

	def merge(self, root1, root2):
		res = []
		(s1, s2) = ([], [])
		while root1 or root2 or s1 or s2:
			while root1 is not None:
				s1.append(root1)
				root1 = root1.left
			while root2 is not None:
				s2.append(root2)
				root2 = root2.left
			if not s2 or (s1 and s1[-1].data <= s2[-1].data):
				root1 = s1[-1]
				del s1[-1]
				res.append(root1.data)
				root1 = root1.right
			else:
				root2 = s2[-1]
				del s2[-1]
				res.append(root2.data)
				root2 = root2.right
		return res


class Solution:

	def getList(self, root, ar):
		if not root:
			return
		self.getList(root.left, ar)
		ar.append(root.data)
		self.getList(root.right, ar)

	def merge(self, root1, root2):
		ar1 = []
		ar2 = []
		self.getList(root1, ar1)
		self.getList(root2, ar2)
		res = []
		i = j = 0
		while i < len(ar1) and j < len(ar2):
			if ar1[i] < ar2[j]:
				res.append(ar1[i])
				i += 1
			else:
				res.append(ar2[j])
				j += 1
		while i < len(ar1):
			res.append(ar1[i])
			i += 1
		while j < len(ar2):
			res.append(ar2[j])
			j += 1
		return res


class Solution:

	def merge(self, root1, root2):
		(l1, l2) = ([], [])

		def inorder(root, a):
			if root:
				inorder(root.left, a)
				a.append(root.data)
				inorder(root.right, a)
		inorder(root1, l1)
		inorder(root2, l2)
		k = []
		(i, j) = (0, 0)
		(m, n) = (len(l1), len(l2))
		while i < m and j < n:
			if l1[i] < l2[j]:
				k.append(l1[i])
				i += 1
			else:
				k.append(l2[j])
				j += 1
		if i < m:
			k.extend(l1[i:])
		else:
			k.extend(l2[j:])
		return k


class Solution:

	def merge(self, root1, root2):

		def inorder(root, a):
			if root:
				inorder(root.left, a)
				a.append(root.data)
				inorder(root.right, a)
		(t1, t2) = ([], [])
		inorder(root1, t1)
		inorder(root2, t2)
		t1.extend(t2)
		t1.sort()
		return t1


class Solution:

	def merge(self, root1, root2):
		rootList = []

		def getElements(node):
			if node is None:
				return
			rootList.append(node.data)
			getElements(node.left)
			getElements(node.right)
		getElements(root1)
		getElements(root2)
		rootList.sort()
		return rootList


class Solution:

	def merge(self, root1, root2):
		(lst1, lst2) = ([], [])
		result = []

		def dfs(node, lst):
			if node is None:
				return
			lst.append(node)
			dfs(node.left, lst)
		dfs(root1, lst1)
		dfs(root2, lst2)
		while lst1 or lst2:
			if lst1 and lst2:
				if lst1[-1].data <= lst2[-1].data:
					node = lst1.pop()
					result.append(node.data)
					dfs(node.right, lst1)
				else:
					node = lst2.pop()
					result.append(node.data)
					dfs(node.right, lst2)
			elif lst1:
				node = lst1.pop()
				result.append(node.data)
				dfs(node.right, lst1)
			elif lst2:
				node = lst2.pop()
				result.append(node.data)
				dfs(node.right, lst2)
		return result


class Solution:

	def merge(self, root1, root2):

		def traverse(node, l):
			if not node:
				return
			else:
				traverse(node.left, l)
				l.append(node.data)
				traverse(node.right, l)
		l = []
		traverse(root1, l)
		traverse(root2, l)
		return sorted(l)


class Solution:

	def merge(self, root1, root2):
		l1 = []
		l2 = []
		st = []
		while st or root1:
			while root1:
				st.append(root1)
				root1 = root1.left
			node = st.pop()
			l1.append(node.data)
			root1 = node.right
		st = []
		while st or root2:
			while root2:
				st.append(root2)
				root2 = root2.left
			node = st.pop()
			l2.append(node.data)
			root2 = node.right
		l = []
		(i, j) = (0, 0)
		while i < len(l1) and j < len(l2):
			if l1[i] <= l2[j]:
				l.append(l1[i])
				i += 1
			else:
				l.append(l2[j])
				j += 1
		while i < len(l1):
			l.append(l1[i])
			i += 1
		while j < len(l2):
			l.append(l2[j])
			j += 1
		return l


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

def Merge2SortedArray(arr1, arr2):
	indx1 = 0
	indx2 = 0
	size1 = len(arr1)
	size2 = len(arr2)
	ans = []
	while indx1 < size1 and indx2 < size2:
		if arr1[indx1] < arr2[indx2]:
			ans.append(arr1[indx1])
			indx1 += 1
		else:
			ans.append(arr2[indx2])
			indx2 += 1
	while indx1 < size1:
		ans.append(arr1[indx1])
		indx1 += 1
	while indx2 < size2:
		ans.append(arr2[indx2])
		indx2 += 1
	return ans

def ArraytoBST(arr, start, end):
	if start > end:
		return None
	n = (start + end) // 2
	root = Node(arr[n])
	root.left = ArraytoBST(arr, start, n - 1)
	root.right = ArraytoBST(arr, n + 1, end)
	return root

class Solution:

	def merge(self, root1, root2):
		if root1 == None and root2 == None:
			return []
		arr1 = []
		Inorder(root1, arr1)
		arr2 = []
		Inorder(root2, arr2)
		if len(arr1) == 0:
			return arr2
		if len(arr2) == 0:
			return arr1
		ans = Merge2SortedArray(arr1, arr2)
		return ans


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

class Solution:

	def merge(self, root1, root2):
		l1 = []
		l2 = []
		insert(root1, l1)
		insert(root2, l2)
		return sorted(l1 + l2)


class Solution:

	def merge(self, root1, root2):
		res = []
		array1 = self.inorder(root1, [])
		array2 = self.inorder(root2, [])
		(i, j) = (0, 0)
		while i < len(array1) and j < len(array2):
			if array1[i] < array2[j]:
				res.append(array1[i])
				i += 1
			else:
				res.append(array2[j])
				j += 1
		while i < len(array1):
			res.append(array1[i])
			i += 1
		while j < len(array2):
			res.append(array2[j])
			j += 1
		return res

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


class Solution:

	def merge(self, root1, root2):

		def helper(root):
			x = []
			if not root:
				return x
			x += helper(root.left)
			x.append(root.data)
			x += helper(root.right)
			return x
		return sorted(helper(root1) + helper(root2))


class Solution:

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

	def convert_bst_to_dll(self, root, head):
		if root == None:
			return
		self.convert_bst_to_dll(root.right, head)
		root.right = head[0]
		head[0] = root
		self.convert_bst_to_dll(root.left, head)

	def merge_lists(self, head1, head2):
		head = tail = None
		while head1 and head2:
			if head1.data < head2.data:
				if head == None:
					head = tail = head1
				else:
					tail.right = head1
					tail = head1
				head1 = head1.right
			else:
				if head == None:
					head = tail = head2
				else:
					tail.right = head2
					tail = head2
				head2 = head2.right
		while head1:
			tail.right = head1
			head1.left = tail
			tail = head1
			head1 = head1.right
		while head2:
			tail.right = head2
			head2.left = tail
			tail = head2
			head2 = head2.right
		return head

	def count_nodes(self, head):
		count = 0
		temp = head
		while temp:
			count += 1
			temp = temp.right
		return count

	def dll_to_bst(self, head, n):
		if n <= 0 or head[0] == None:
			return
		left = self.dll_to_bst(head, n // 2)
		root = head[0]
		root.left = left
		head[0] = head[0].right
		root.right = self.dll_to_bst(head, n - n // 2 - 1)
		return root

	def merge(self, root1, root2):
		head1 = [None]
		self.convert_bst_to_dll(root1, head1)
		head2 = [None]
		self.convert_bst_to_dll(root2, head2)
		head = self.merge_lists(head1[0], head2[0])
		head = [head]
		n = self.count_nodes(head[0])
		root = self.dll_to_bst(head, n)
		inord = []
		self.inorder(root, inord)
		return inord


class Solution:

	def merge(self, root1, root2):
		ans = []
		(s1, s2) = ([], [])
		while root1 or root2 or s1 or s2:
			while root1:
				s1.append(root1)
				root1 = root1.left
			while root2:
				s2.append(root2)
				root2 = root2.left
			if not s2 or (s1 and s1[-1].data <= s2[-1].data):
				root1 = s1[-1]
				del s1[-1]
				ans.append(root1.data)
				root1 = root1.right
			else:
				root2 = s2[-1]
				del s2[-1]
				ans.append(root2.data)
				root2 = root2.right
		return ans


class Solution:

	def merge(self, root1, root2):
		v = []
		self.inorder(root1, v)
		self.inorder(root2, v)
		v.sort()
		return v

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


class Solution:

	def Isorder1(self, root1, l1):
		if root1 is None:
			return
		self.Isorder1(root1.left, l1)
		l1.append(root1.data)
		self.Isorder1(root1.right, l1)

	def Isorder2(self, root2, l2):
		if root2 is None:
			return
		self.Isorder2(root2.left, l2)
		l2.append(root2.data)
		self.Isorder2(root2.right, l2)

	def merge(self, root1, root2):
		l1 = []
		l2 = []
		self.Isorder1(root1, l1)
		self.Isorder2(root2, l2)
		l3 = l1 + l2
		l3.sort()
		return l3


class Solution:

	def merge(self, root1, root2):
		list1 = []
		list2 = []

		def inorder(node, lst):
			if not node:
				return
			inorder(node.left, lst)
			lst.append(node.data)
			inorder(node.right, lst)
		inorder(root1, list1)
		inorder(root2, list2)
		i = j = 0
		merged_list = []
		while i < len(list1) and j < len(list2):
			if list1[i] < list2[j]:
				merged_list.append(list1[i])
				i += 1
			else:
				merged_list.append(list2[j])
				j += 1
		merged_list += list1[i:]
		merged_list += list2[j:]
		return merged_list


class Solution:

	def merge(self, root1, root2):
		l = []

		def fun(x):
			if x:
				fun(x.left)
				l.append(x.data)
				fun(x.right)
		fun(root1)
		fun(root2)
		l.sort()
		return l


class Solution:

	def merge(self, root1, root2):
		s1 = []
		s2 = []
		res = []
		cur1 = root1
		cur2 = root2
		while True:
			while cur1:
				s1.append(cur1)
				cur1 = cur1.left
			while cur2:
				s2.append(cur2)
				cur2 = cur2.left
			if not s1 and (not s2):
				break
			elif not s1:
				res.append(s2[-1].data)
				cur2 = s2.pop().right
			elif not s2:
				res.append(s1[-1].data)
				cur1 = s1.pop().right
			elif s1[-1].data < s2[-1].data:
				res.append(s1[-1].data)
				cur1 = s1.pop().right
			else:
				res.append(s2[-1].data)
				cur2 = s2.pop().right
		return res


class Solution:

	def merge(self, root1, root2):
		in1 = []
		in2 = []
		self.inorder(root1, in1)
		self.inorder(root2, in2)
		res = []
		m = len(in1)
		n = len(in2)
		i = 0
		j = 0
		while i < m and j < n:
			if in1[i] < in2[j]:
				res.append(in1[i])
				i += 1
			else:
				res.append(in2[j])
				j += 1
		while i < m:
			res.append(in1[i])
			i += 1
		while j < n:
			res.append(in2[j])
			j += 1
		return res

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


class Solution:

	def merge(self, root1, root2):
		res = []
		stk1 = []
		stk2 = []
		cur1 = root1
		while cur1:
			stk1.append(cur1)
			cur1 = cur1.left
		cur2 = root2
		while cur2:
			stk2.append(cur2)
			cur2 = cur2.left
		while stk1 and stk2:
			if stk1[-1].data < stk2[-1].data:
				cur = stk1.pop()
				res.append(cur.data)
				cur = cur.right
				while cur:
					stk1.append(cur)
					cur = cur.left
			else:
				cur = stk2.pop()
				res.append(cur.data)
				cur = cur.right
				while cur:
					stk2.append(cur)
					cur = cur.left
		while stk1:
			cur = stk1.pop()
			res.append(cur.data)
			cur = cur.right
			while cur:
				stk1.append(cur)
				cur = cur.left
		while stk2:
			cur = stk2.pop()
			res.append(cur.data)
			cur = cur.right
			while cur:
				stk2.append(cur)
				cur = cur.left
		return res


class Solution:

	def inorder(self, root, path):
		if not root:
			return
		self.inorder(root.left, path)
		path.append(root.data)
		self.inorder(root.right, path)

	def merge(self, root1, root2):
		(path1, path2) = ([], [])
		self.inorder(root1, path1)
		self.inorder(root2, path2)
		(i, j, n, m) = (0, 0, len(path1), len(path2))
		res = []
		while i < n and j < m:
			if path1[i] <= path2[j]:
				res.append(path1[i])
				i += 1
			else:
				res.append(path2[j])
				j += 1
		while i < n:
			res.append(path1[i])
			i += 1
		while j < m:
			res.append(path2[j])
			j += 1
		return res


class Solution:

	def merge(self, root1, root2):
		inorder1 = self.InorderIterative(root1)
		inorder2 = self.InorderIterative(root2)
		merged_array = self.mergeSortedArray(inorder1, len(inorder1), inorder2, len(inorder2))
		return merged_array
		root = self.sortedArrayToBST(merged_array)
		return self.InorderIterative(root)

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

	def mergeSortedArray(self, nums1, m, nums2, n):
		(i, j) = (0, 0)
		ans = []
		while i < m and j < n:
			if nums1[i] >= nums2[j]:
				ans.append(nums2[j])
				j += 1
			else:
				ans.append(nums1[i])
				i += 1
		while i < m:
			ans.append(nums1[i])
			i += 1
		while j < n:
			ans.append(nums2[j])
			j += 1
		return ans

	def sortedArrayToBST(self, nums):
		if not nums:
			return None
		mid = len(nums) // 2
		node = Node(nums[mid])
		node.left = self.sortedArrayToBST(nums[:mid])
		node.right = self.sortedArrayToBST(nums[mid + 1:])
		return node


class Solution:

	def merge(self, root1, root2):

		def inorder(root):
			nonlocal arr
			if root:
				inorder(root.left)
				arr.append(root.data)
				inorder(root.right)
		arr = []
		inorder(root1)
		p = len(arr)
		inorder(root2)
		res = []
		(i, j) = (0, p)
		while i < p and j < len(arr):
			if arr[i] < arr[j]:
				res.append(arr[i])
				i += 1
			else:
				res.append(arr[j])
				j += 1
		while i < p:
			res.append(arr[i])
			i += 1
		while j < len(arr):
			res.append(arr[j])
			j += 1
		return res