Given two Binary Search Trees. Find the nodes that are common in both of them, ie- find the intersection of the two BSTs.
Example 1:
Input:
BST1:
                  5
               /     \
             1        10
           /   \      /
          0     4    7
                      \
                       9
BST2:
                10 
              /    \
             7     20
           /   \ 
          4     9
Output: 4 7 9 10
Example 2:
Input:
BST1:
     10
    /  \
   2   11
  /  \
 1   3
BST2:
       2
     /  \
    1    3
Output: 1 2 3
Your Task:
You don't need to read input or print anything. Your task is to complete the function findCommon() that takes roots of the two BSTs as input parameters and returns a list of integers containing the common nodes in sorted order. 
Expected Time Complexity: O(N1 + N2) where N1 and N2 are the sizes of the 2 BSTs.
Expected Auxiliary Space: O(H1 + H2) where H1 and H2 are the heights of the 2 BSTs.
Constraints:
1 <= Number of Nodes <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3


class Solution:
    
    #Function to find the nodes that are common in both BST.
    def findCommon(self, root1, root2):
        # code here

Solutions:
def slove(root, l):
	if root is None:
		return
	slove(root.left, l)
	l.append(root.data)
	slove(root.right, l)
	return l

class Solution:

	def findCommon(self, root1, root2):
		list1 = []
		slove(root1, list1)
		list2 = []
		slove(root2, list2)
		t = list1[:]
		t = set(t)
		l1 = set(list1)
		l2 = set(list2)
		l = l1 - l2
		res = t - l
		res = list(res)
		res.sort()
		return res


class Solution:

	def findCommon(self, root1, root2):

		def t(rt, re):
			if rt is None:
				return None
			t(rt.left, re)
			t(rt.right, re)
			re.append(rt.data)
		(r1, r2) = ([], [])
		t(root1, r1)
		t(root2, r2)
		l = list(set(r1).intersection(set(r2)))
		l.sort()
		return l


class Solution:

	def getN(self, root, arr):
		if not root:
			return
		arr[root.data] = 1
		self.getN(root.left, arr)
		self.getN(root.right, arr)

	def findCommon(self, root1, root2):
		arr1 = {}
		arr2 = {}
		arr = []
		self.getN(root1, arr1)
		self.getN(root2, arr2)
		for (i, v) in arr1.items():
			try:
				if arr2[i] == 1:
					arr.append(i)
			except:
				continue
		arr.sort()
		return arr


from collections import defaultdict

class Solution:

	def s(self):
		return -1

	def findCommon(self, root1, root2):
		d = defaultdict(self.s)
		list = []
		self.sol(root1, d, 0, list)
		self.sol(root2, d, 1, list)
		return list

	def sol(self, root, dic, i, list):
		if root:
			self.sol(root.left, dic, i, list)
			if i == 0 and dic[root.data] == -1:
				dic[root.data] = 1
			if i == 1 and dic[root.data] != -1:
				list.append(root.data)
			self.sol(root.right, dic, i, list)


class Solution:

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

	def findCommon(self, root1, root2):
		a = []
		a.extend(self.levelorder(root1))
		b = []
		b.extend(self.levelorder(root2))
		a1 = set(a)
		b1 = set(b)
		if len(a1.intersection(b1)) > 0:
			return sorted(list(a1.intersection(b1)))
		else:
			return []


class Solution:

	def t(self, root, path, ans):
		if root == None:
			return -1
		if path.get(root.data) != None:
			ans.append(root.data)
		path[root.data] = 1
		self.t(root.left, path, ans)
		self.t(root.right, path, ans)

	def findCommon(self, root1, root2):
		path = dict()
		ans = []
		self.t(root1, path, ans)
		ans.clear()
		self.t(root2, path, ans)
		return sorted(ans)


class Solution:

	def findCommon(self, root1, root2):
		d1 = dict()
		d2 = dict()
		temp = [root1]
		d1[root1.data] = 1
		while temp:
			r = []
			for i in temp:
				if i.left:
					r.append(i.left)
					if i.left.data in d1:
						d1[i.left.data] += 1
					else:
						d1[i.left.data] = 1
				if i.right:
					r.append(i.right)
					if i.right.data in d1:
						d1[i.right.data] += 1
					else:
						d1[i.right.data] = 1
			temp = r
		res = []

		def helper(root, res):
			if root == None:
				return
			helper(root.left, res)
			if root.data in d1:
				res.append(root.data)
			helper(root.right, res)
		helper(root2, res)
		return res


class Solution:

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

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

	def findCommon(self, root1, root2):
		(l1, l2) = ([], [])
		self.fun1(root1, l1)
		self.fun2(root2, l2)
		t = l1[:]
		t = set(t)
		(l1, l2) = (set(l1), set(l2))
		l = l1 - l2
		res = t - l
		res = list(res)
		res.sort()
		return res


class Solution:

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

	def findCommon(self, root1, root2):
		num1 = []
		num2 = []
		self.inorder(root1, num1)
		self.inorder(root2, num2)
		num1 = set(num1)
		num2 = set(num2)
		num3 = num1.intersection(num2)
		num3 = list(num3)
		num3.sort()
		return num3


class Solution:

	def helper(self, root1, d, li):
		if root1 == None:
			return root1
		self.helper(root1.left, d, li)
		if root1.data in d:
			li.append(root1.data)
		else:
			d[root1.data] = 1
		self.helper(root1.right, d, li)

	def findCommon(self, root1, root2):
		d = {}
		li = []
		self.helper(root1, d, li)
		self.helper(root2, d, li)
		return li


class Solution:

	def solve(self, root, ans, dic):
		if root == None:
			return
		if root.data not in dic:
			dic[root.data] = 1
		else:
			ans.append(root.data)
		self.solve(root.left, ans, dic)
		self.solve(root.right, ans, dic)

	def findCommon(self, root1, root2):
		dic = {}
		ans = []
		self.solve(root1, ans, dic)
		self.solve(root2, ans, dic)
		ans.sort()
		return ans


class Solution:

	def findCommon(self, root1, root2):
		lis1 = set(self.inorder(root1, []))
		lis2 = set(self.inorder(root2, []))
		lis = list(lis1 & lis2)
		lis.sort()
		return lis

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


class Solution:

	def findCommon(self, root1, root2):

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			res[root.data] = 1
			inorder(root.right)

		def check(root):
			if not root:
				return
			check(root.left)
			if root.data in res:
				ans.append(root.data)
			check(root.right)
		res = {}
		inorder(root1)
		ans = []
		check(root2)
		return ans


def func(root, a, tr, ans):
	if root is None:
		return
	func(root.left, a, tr, ans)
	if tr == 1:
		a.add(root.data)
	elif root.data in a:
		ans.append(root.data)
	func(root.right, a, tr, ans)

class Solution:

	def findCommon(self, root1, root2):
		t = set()
		ans = []
		func(root1, t, 1, ans)
		func(root2, t, 2, ans)
		return ans


class Solution:

	def findCommon(self, root1, root2):
		b = set()
		Solution.bst(root1, b)
		c = set()
		Solution.bst(root2, c)
		return list(sorted(b & c))

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

	def common(root, b, c):
		if root.data in b and root.data not in c:
			c.append(root.data)
		if root.left:
			Solution.common(root.left, b, c)
		if root.right:
			Solution.common(root.right, b, c)


class Solution:

	def findCommon(self, root1, root2):
		v1 = []
		v2 = []
		ans = []
		self.inorder(root1, v1)
		self.inorder(root2, v2)
		i = 0
		j = 0
		while i < len(v1) and j < len(v2):
			if v1[i] == v2[j]:
				ans.append(v1[i])
				i += 1
				j += 1
			elif v1[i] < v2[j]:
				i += 1
			else:
				j += 1
		return ans

	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 solve(self, root, dic, li):
		if root is None:
			return
		self.solve(root.left, dic, li)
		if root.data in dic:
			li.append(root.data)
		else:
			dic[root.data] = 1
		self.solve(root.right, dic, li)

	def findCommon(self, root1, root2):
		q = [root2]
		li = []
		dic = {}
		self.solve(root1, dic, li)
		self.solve(root2, dic, li)
		return li


class Solution:

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


class Solution:

	def findCommon(self, root1, root2):
		s1 = set()
		self.inorder(root1, s1)
		res = []
		self.inorderCheck(root2, s1, res)
		return res

	def inorder(self, root, s):
		if not root:
			return
		self.inorder(root.left, s)
		s.add(root.data)
		self.inorder(root.right, s)

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


class Solution:

	def findCommon(self, root1, root2):
		(s1, s2) = (set(), set())

		def fun(root, x):
			if not root:
				return
			x.add(root.data)
			fun(root.left, x)
			fun(root.right, x)
		fun(root1, s1)
		fun(root2, s2)
		a = list(s1.intersection(s2))
		return sorted(a)


class Solution:

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

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


class Solution:

	def findCommon(self, root1, root2):
		s1 = set()
		s2 = set()

		def solve1(root):
			if root:
				s1.add(root.data)
				solve1(root.left)
				solve1(root.right)

		def solve2(root):
			if root:
				s2.add(root.data)
				solve2(root.left)
				solve2(root.right)
		solve1(root1)
		solve2(root2)
		l = list(s1.intersection(s2))
		return sorted(l)


class Solution:

	def findCommon(self, root1, root2):

		def Inorder(root, arr):
			if root:
				Inorder(root.left, arr)
				arr.append(root.data)
				Inorder(root.right, arr)
			return arr
		arr1 = []
		arr2 = []
		Inorder(root1, arr1)
		Inorder(root2, arr2)
		arr = list(set(arr1).intersection(set(arr2)))
		return sorted(arr)


class Solution:

	def findCommon(self, root1, root2):

		def find(root, hash):
			if root == None:
				return
			find(root.left, hash)
			hash.add(root.data)
			find(root.right, hash)

		def common(root, ans, hash):
			if root == None:
				return
			common(root.left, ans, hash)
			if root.data in hash:
				ans.append(root.data)
			common(root.right, ans, hash)
		hash = set()
		find(root2, hash)
		ans = []
		common(root1, ans, hash)
		return ans


class Solution:

	def findCommon(self, root1, root2):
		C = []
		A = []
		B = []
		self.x(root1, A)
		self.x(root2, B)
		r = len(B) - 1
		for i in range(len(A)):
			if self.binarySearch(B, 0, r, A[i]) != -1:
				C.append(A[i])
		return C

	def binarySearch(self, arr, l, r, x):
		if r >= l:
			mid = l + (r - l) // 2
			if arr[mid] == x:
				return mid
			elif arr[mid] > x:
				return self.binarySearch(arr, l, mid - 1, x)
			else:
				return self.binarySearch(arr, mid + 1, r, x)
		else:
			return -1

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


class Solution:

	def findCommon(self, root1, root2):
		arr1 = set(self.helper(root1))
		arr2 = set(self.helper(root2))
		li = sorted(list(arr1.intersection(arr2)))
		return li

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


class Solution:

	def findCommon(self, root1, root2):
		arr1 = []
		arr2 = []
		if not root1 or not root2:
			return []
		arr1 = self.inorder(root1)
		arr2 = self.inorder(root2)
		arr3 = set(arr1).intersection(set(arr2))
		return sorted(arr3)

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


class Solution:

	def findCommon(self, root1, root2):
		l1 = []
		l2 = []
		r = []
		while 1:
			if root1 != None:
				l1.append(root1)
				root1 = root1.left
			elif root2 != None:
				l2.append(root2)
				root2 = root2.left
			elif len(l1) > 0 and len(l2) > 0:
				n = len(l1) - 1
				m = len(l2) - 1
				root1 = l1[n]
				root2 = l2[m]
				if root1.data == root2.data:
					r.append(root1.data)
					n = len(l1) - 1
					m = len(l2) - 1
					l1.pop()
					l2.pop()
					root1 = root1.right
					root2 = root2.right
				elif root1.data > root2.data:
					l2.pop()
					root1 = None
					root2 = root2.right
				else:
					l1.pop()
					root2 = None
					root1 = root1.right
			else:
				break
		return r


class Solution:

	def inorder(self, root1, d, l):
		if root1 == None:
			return
		self.inorder(root1.left, d, l)
		if root1.data not in d:
			d[root1.data] = 1
		else:
			l.append(root1.data)
		self.inorder(root1.right, d, l)

	def findCommon(self, root1, root2):
		d = {}
		l = []
		self.inorder(root1, d, l)
		self.inorder(root2, d, l)
		return l


class Solution:

	def findCommon(self, root1, root2):
		s = set()
		ans = []

		def fun(root):
			if root == None:
				return
			s.add(root.data)
			fun(root.left)
			fun(root.right)

		def fun1(root):
			if root == None:
				return
			if root.data in s:
				ans.append(root.data)
			fun1(root.left)
			fun1(root.right)
		fun(root1)
		fun1(root2)
		if len(ans) > 0:
			ans.sort()
		return ans


class Solution:

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

		def solve(root, lis):
			if root == None:
				return
			lis.append(root.data)
			solve(root.left, lis)
			solve(root.right, lis)
			return lis
		res = solve(root1, lis)
		lis = []
		ans = solve(root2, lis)
		lid = []
		res = set(res)
		ans = set(ans)
		for i in ans:
			if i in res:
				lid.append(i)
		lid.sort()
		return lid


class Solution:

	def findCommon(self, root1, root2):
		nums = []

		def inorder(root):
			nonlocal nums
			if root:
				inorder(root.left)
				nums.append(root.data)
				inorder(root.right)
		inorder(root1)
		s = len(nums)
		inorder(root2)
		return self.intersection(nums, s)

	def intersection(self, nums, s):
		t = len(nums)
		(i, j) = (0, s)
		res = []
		while i < s and j < t:
			if nums[i] < nums[j]:
				i += 1
			elif nums[i] > nums[j]:
				j += 1
			else:
				res.append(nums[i])
				i += 1
				j += 1
		return res


class Solution:

	def __init__(self):
		self.list1 = []
		self.list2 = []

	def findCommon(self, root1, root2):

		def traversal(root, list1):
			if root == None:
				return None
			list1.append(root.data)
			if root.left:
				traversal(root.left, list1)
			if root.right:
				traversal(root.right, list1)
		list1 = []
		list2 = []
		traversal(root1, list1)
		traversal(root2, list2)
		return sorted(list(set(list1).intersection(set(list2))))


class Solution:

	def findCommon(self, root1, root2):
		s1 = []
		s2 = []
		result = []
		while (root1 is not None or len(s1) > 0) and (root2 is not None or len(s2) > 0):
			while root1:
				s1.append(root1)
				root1 = root1.left
			while root2:
				s2.append(root2)
				root2 = root2.left
			root1 = s1[-1]
			root2 = s2[-1]
			if root1.data < root2.data:
				s1.pop(-1)
				root1 = root1.right
				root2 = None
			elif root1.data > root2.data:
				s2.pop()
				root2 = root2.right
				root1 = None
			else:
				result.append(root1.data)
				s1.pop()
				s2.pop()
				root1 = root1.right
				root2 = root2.right
		return result


class Solution:

	def findCommon(self, root1, root2):
		list1 = []
		list2 = []
		res = []
		while 1:
			if root1:
				list1.append(root1)
				root1 = root1.left
			elif root2:
				list2.append(root2)
				root2 = root2.left
			elif list1 and list2:
				root1 = list1[-1]
				root2 = list2[-1]
				if root1.data == root2.data:
					res.append(root1.data)
					list1.pop()
					list2.pop()
					root1 = root1.right
					root2 = root2.right
				elif root1.data < root2.data:
					list1.pop()
					root1 = root1.right
					root2 = None
				elif root1.data > root2.data:
					list2.pop()
					root2 = root2.right
					root1 = None
			else:
				break
		return res


class Solution:

	def findCommon(self, root1, root2):
		res = []
		hset = set()
		self.ino(root1, hset)
		self.inorde(root2, hset, res)
		return res

	def ino(self, root, hset):
		if root:
			self.ino(root.left, hset)
			hset.add(root.data)
			self.ino(root.right, hset)

	def inorde(self, root, hset, res):
		if root:
			self.inorde(root.left, hset, res)
			if root.data in hset:
				res.append(root.data)
			self.inorde(root.right, hset, res)


class Solution:

	def __init__(self):
		self.inorder1 = []
		self.inorder2 = []
		self.temp = []

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

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

	def findCommon(self, root1, root2):
		self.InOrder1(root1)
		self.InOrder2(root2)
		p1 = 0
		p2 = 0
		while p1 < len(self.inorder1) and p2 < len(self.inorder2):
			node1 = self.inorder1[p1]
			node2 = self.inorder2[p2]
			if node1 == node2:
				self.temp.append(node1)
				p1 += 1
			elif node1 > node2:
				p2 += 1
			elif node1 < node2:
				p1 += 1
		return self.temp


class Solution:

	def findCommon(self, root1, root2):
		nodes_1 = []
		nodes_2 = []
		self._in_order(root1, nodes_1)
		self._in_order(root2, nodes_2)
		nodes_1 = set(nodes_1)
		nodes_2 = set(nodes_2)
		res = [_ for _ in nodes_1.intersection(nodes_2)]
		res.sort()
		return res

	def _in_order(self, root, nodes_list):
		if root:
			self._in_order(root.left, nodes_list)
			nodes_list.append(root.data)
			self._in_order(root.right, nodes_list)


class Solution:

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

	def findCommon(self, root1, root2):
		output = []
		arr1 = {}
		arr2 = {}
		self.inorder(root1, arr1)
		self.inorder(root2, arr2)
		for i in arr1:
			if i in arr2:
				output.append(i)
		output.sort()
		return output


class Solution:

	def findCommon(self, root1, root2):
		a = []
		b = []
		self.ans(a, root1)
		self.ans(b, root2)
		c = []
		d = {}
		for i in range(0, len(a)):
			if a[i] not in d:
				d[a[i]] = 1
		for j in range(0, len(b)):
			if b[j] not in d:
				d[b[j]] = 1
			elif b[j] in d:
				d[b[j]] = d[b[j]] + 1
		for x in d:
			if d[x] == 2:
				c.append(x)
		return sorted(c)

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


class Solution:

	def findCommon(self, root1, root2):
		setti1 = set()
		setti2 = set()
		self.myFunc(root1, setti1)
		self.myFunc(root2, setti2)
		return sorted(setti1.intersection(setti2))

	def myFunc(self, root, setti):
		if not root:
			return
		setti.add(root.data)
		self.myFunc(root.left, setti)
		self.myFunc(root.right, setti)
		return


class Solution:

	def __init__(self):
		self.list1 = []
		self.list2 = []

	def findCommon(self, root1, root2):

		def traversal(root, arr):
			if root == None:
				return None
			if root.left:
				traversal(root.left, arr)
			arr.append(root.data)
			if root.right:
				traversal(root.right, arr)
		(arr1, arr2) = ([], [])
		traversal(root1, arr1)
		traversal(root2, arr2)
		(length1, length2) = (len(arr1), len(arr2))
		(i, j) = (0, 0)
		list2 = []
		while i < length1 and j < length2:
			if arr1[i] < arr2[j]:
				i += 1
			elif arr2[j] < arr1[i]:
				j += 1
			else:
				list2.append(arr1[i])
				i += 1
				j += 1
		return list2


def populateDict(root, d):
	if root:
		if root.data in d.keys():
			d[root.data] += 1
		else:
			d[root.data] = 1
		d = populateDict(root.left, d)
		d = populateDict(root.right, d)
	return d

class Solution:

	def findCommon(self, root1, root2):
		d = {}
		d = populateDict(root1, d)
		d = populateDict(root2, d)
		return sorted([i for i in d.keys() if d[i] > 1])


class Solution:

	def findCommon(self, root1, root2):

		def inorder(node, d, ans):
			if not node:
				return
			inorder(node.left, d, ans)
			if node.data in d:
				ans.append(node.data)
			else:
				d[node.data] = 1
			inorder(node.right, d, ans)
			return
		d = {}
		ans = []
		inorder(root1, d, ans)
		inorder(root2, d, ans)
		return ans


import collections

class Solution:

	def solve(self, root):
		if root == None:
			return None
		else:
			if root.data in self.map_:
				self.res.append(root.data)
			self.map_[root.data] = True
			_ = self.solve(root.left)
			_ = self.solve(root.right)
			return None

	def findCommon(self, root1, root2):
		self.res = []
		self.map_ = collections.defaultdict(lambda : False)
		_ = self.solve(root1)
		_ = self.solve(root2)
		self.res.sort()
		return self.res


class Solution:

	def inorder(self, root):
		if not root:
			return []
		curr = root
		stack = [curr]
		while curr.left:
			stack.append(curr.left)
			curr = curr.left
		return stack

	def pop(self, stack):
		c = stack.pop()
		if c.right:
			stack.append(c.right)
			c = c.right
			while c.left:
				stack.append(c.left)
				c = c.left

	def findCommon(self, root1, root2):
		stack1 = self.inorder(root1)
		stack2 = self.inorder(root2)
		res = []
		while len(stack1) and len(stack2):
			a = stack1[len(stack1) - 1]
			b = stack2[len(stack2) - 1]
			if a.data == b.data:
				res.append(a.data)
				self.pop(stack1)
				self.pop(stack2)
			elif a.data > b.data:
				self.pop(stack2)
			else:
				self.pop(stack1)
		return res


class Solution:

	def findCommon2(self, root1, root2):
		ans = []

		def inorder(root):
			if root is None:
				return
			inorder(root.left)
			ans.append(root.data)
			inorder(root.right)
		inorder(root1)
		l1 = [x for x in ans]
		ans = []
		inorder(root2)
		l2 = [x for x in ans]
		sol = []
		(i, j, m, n) = (0, 0, len(l1), len(l2))
		while i < m and j < n:
			if l1[i] == l2[j]:
				sol.append(l1[i])
				i += 1
				j += 1
			elif l1[i] < l2[j]:
				i += 1
			else:
				j += 1
		return sol

	def findCommon(self, root1, root2):
		ans = []
		stack1 = []
		stack2 = []
		while True:
			if root1:
				stack1.append(root1)
				root1 = root1.left
			elif root2:
				stack2.append(root2)
				root2 = root2.left
			elif stack1 and stack2:
				root1 = stack1[-1]
				root2 = stack2[-1]
				if root1.data == root2.data:
					stack1.pop()
					stack2.pop()
					ans.append(root1.data)
					root1 = root1.right
					root2 = root2.right
				elif root1.data < root2.data:
					stack1.pop()
					root2 = None
					root1 = root1.right
				elif root1.data > root2.data:
					stack2.pop()
					root1 = None
					root2 = root2.right
			else:
				break
		return ans


class Solution:

	def findCommon(self, root1, root2):
		s1 = []
		s2 = []
		ans = []
		while True:
			while root1:
				s1.append(root1)
				root1 = root1.left
			while root2:
				s2.append(root2)
				root2 = root2.left
			if s1 and s2:
				root1 = s1[-1]
				root2 = s2[-1]
				if root1.data < root2.data:
					s1.pop()
					root1 = root1.right
					root2 = None
				elif root1.data > root2.data:
					s2.pop()
					root2 = root2.right
					cur1 = None
				else:
					ans.append(root1.data)
					s1.pop()
					s2.pop()
					root1 = root1.right
					root2 = root2.right
			else:
				break
		return ans


class Solution:

	def findCommon(self, root1, root2):
		a = leveltrav(root1)
		b = leveltrav(root2)
		a1 = set(a)
		b1 = set(b)
		c = list(a1.intersection(b1))
		c.sort()
		return c

class Queue:

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

	def __str__(self):
		values = []
		values = [str(x) for x in self.l]
		return ' '.join(values)

	def isEmpty(self):
		if self.l == []:
			return True
		else:
			return False

	def Enqueue(self, val):
		self.l.append(val)
		return 'Insertion is completed'

	def Dequeue(self):
		if self.isEmpty():
			return 'Queue is empty'
		else:
			return self.l.pop(0)

def leveltrav(Node):
	l = []
	if not Node:
		return
	else:
		customQueue = Queue()
		customQueue.Enqueue(Node)
		while not customQueue.isEmpty():
			root = customQueue.Dequeue()
			l.append(root.data)
			if root.left is not None:
				customQueue.Enqueue(root.left)
			if root.right is not None:
				customQueue.Enqueue(root.right)
		return l


class Solution:

	def __init__(self):
		(self.stack1, self.stack2) = (list(), list())
		self.ans = list()

	def findCommon(self, root1, root2):
		(self.curr1, self.curr2) = (root1, root2)
		(val1, val2) = (self.inorder1(), self.inorder2())
		ans = []
		while val1 and val2:
			if val1 == val2:
				ans.append(val1)
				(val1, val2) = (self.inorder1(), self.inorder2())
			elif val1 < val2:
				val1 = self.inorder1()
			else:
				val2 = self.inorder2()
		return ans

	def inorder1(self):
		while self.stack1 or self.curr1:
			if self.curr1:
				self.stack1.append(self.curr1)
				self.curr1 = self.curr1.left
			else:
				self.curr1 = self.stack1.pop(-1)
				tempval = self.curr1.data
				self.curr1 = self.curr1.right
				return tempval

	def inorder2(self):
		while self.stack2 or self.curr2:
			if self.curr2:
				self.stack2.append(self.curr2)
				self.curr2 = self.curr2.left
			else:
				self.curr2 = self.stack2.pop(-1)
				tempval = self.curr2.data
				self.curr2 = self.curr2.right
				return tempval


class Solution:

	def __init__(self):
		(self.stack1, self.stack2) = (list(), list())
		self.ans = list()

	def findCommon(self, root1, root2):
		self.stack1.append(root1)
		self.stack2.append(root2)
		TOP = -1
		while self.stack1 and self.stack2:
			(top1, top2) = (self.stack1[TOP], self.stack2[TOP])
			if top1.left:
				temp = top1.left
				top1.left = None
				self.stack1.append(temp)
			elif top2.left:
				temp = top2.left
				top2.left = None
				self.stack2.append(temp)
			elif top1.data == top2.data:
				(temp1, temp2) = (top1.right, top2.right)
				self.ans.append(top1.data)
				self.stack1.pop(TOP)
				self.stack2.pop(TOP)
				if temp1:
					self.stack1.append(temp1)
				if temp2:
					self.stack2.append(temp2)
			elif top1.data < top2.data:
				temp = top1.right
				self.stack1.pop(TOP)
				if temp:
					self.stack1.append(temp)
			else:
				temp = top2.right
				self.stack2.pop(TOP)
				if temp:
					self.stack2.append(temp)
		return self.ans


class Solution:

	def findCommon(self, root1, root2):

		def traverse(root, arr):
			if root == None:
				return
			traverse(root.left, arr)
			arr.append(root.data)
			traverse(root.right, arr)
		arr1 = []
		arr2 = []
		traverse(root1, arr1)
		traverse(root2, arr2)
		if len(arr1) > len(arr2):
			(arr1, arr2) = (arr2, arr1)
		result = []
		for val in arr1:
			i = 0
			j = len(arr2) - 1
			found = False
			while i <= j:
				mid = (i + j) // 2
				if arr2[mid] == val:
					found = True
					break
				elif arr2[mid] < val:
					i = mid + 1
				else:
					j = mid - 1
			if found:
				result.append(val)
		return result


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

class Solution:

	def findCommon(self, root1, root2):
		res1 = []
		res2 = []
		inord(root1, res1)
		inord(root2, res2)
		ans = []
		i = 0
		j = 0
		n = len(res1)
		m = len(res2)
		minn = min(n, m)
		while i < n and j < m:
			if res1[i] == res2[j]:
				ans.append(res1[i])
				i += 1
				j += 1
			elif res1[i] < res2[j]:
				i += 1
			else:
				j += 1
		return ans


class Solution:

	def findCommon(self, root1, root2):

		def traverse(root, res):
			if root:
				traverse(root.left, res)
				res.append(root.data)
				traverse(root.right, res)
		res1 = []
		res2 = []
		ans = []
		traverse(root1, res1)
		traverse(root2, res2)
		mp = {}
		res1.extend(res2)
		for i in res1:
			if i in mp:
				ans.append(i)
			else:
				mp[i] = 0
		return ans


class Solution:

	def solveFirst(self, root):
		res = []
		if root != None:
			res += self.solveFirst(root.left)
			res.append(root.data)
			res += self.solveFirst(root.right)
		return res

	def solveSecond(self, root, hashMap, res):
		if root != None:
			self.solveSecond(root.left, hashMap, res)
			if root.data in hashMap:
				res.append(root.data)
			self.solveSecond(root.right, hashMap, res)
		return res

	def findCommon(self, root1, root2):
		sett = self.solveFirst(root1)
		res2 = self.solveSecond(root2, set(sett), [])
		return res2


class Solution:

	def findCommon(self, root1, root2):
		Aset = set()
		Bset = set()
		mod = 1000000007

		def _dfsA(node):
			if not node:
				return
			Aset.add(node.data)
			_dfsA(node.left)
			_dfsA(node.right)

		def _dfsB(node):
			if not node:
				return
			Bset.add(node.data)
			_dfsB(node.left)
			_dfsB(node.right)
		_dfsA(root1)
		_dfsB(root2)
		total_sum = []
		for i in Bset:
			if i in Aset:
				total_sum.append(i)
		total_sum.sort()
		return total_sum


class Solution:

	def findCommon(self, root1, root2):
		a = inorder(root1)
		b = inorder(root2)
		i = 0
		j = 0
		ans = []
		while i < len(a) and j < len(b):
			if a[i] == b[j]:
				ans.append(a[i])
				i += 1
				j += 1
			elif a[i] > b[j]:
				j += 1
			else:
				i += 1
		return ans

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


class Solution:

	def findCommon(self, root1, root2):

		def helper(x):
			l = []
			if x:
				l += helper(x.left)
				l.append(x.data)
				l += helper(x.right)
			return l
		a = helper(root1)
		b = helper(root2)
		c = {}
		for i in b:
			c[i] = 1
		ans = []
		for i in a:
			if i in c:
				ans.append(i)
		return ans


from collections import deque

class Solution:

	def moveLeft(self, root, stack):
		tmp = root.right
		while tmp:
			stack.append(tmp)
			tmp = tmp.left

	def findCommon(self, root1, root2):
		ans = []
		stack1 = deque()
		stack2 = deque()
		tmp = root1
		while tmp:
			stack1.append(tmp)
			tmp = tmp.left
		tmp = root2
		while tmp:
			stack2.append(tmp)
			tmp = tmp.left
		while len(stack1) and len(stack2):
			x1 = stack1[-1].data
			x2 = stack2[-1].data
			if x1 == x2:
				ans.append(x1)
				tmp1 = stack1.pop()
				tmp2 = stack2.pop()
				self.moveLeft(tmp1, stack1)
				self.moveLeft(tmp2, stack2)
			elif x1 < x2:
				tmp1 = stack1.pop()
				self.moveLeft(tmp1, stack1)
			else:
				tmp2 = stack2.pop()
				self.moveLeft(tmp2, stack2)
		return ans


class Solution:

	def findCommon(self, root1, root2):
		l = []
		if root1 is None:
			return
		l = first(root1, root2, l)
		return l

def first(root1, root2, l):
	if root1 is None:
		return
	first(root1.left, root2, l)
	l = second(root2, root1.data, l)
	first(root1.right, root2, l)
	return l

def second(root2, data, l):
	if root2 is None:
		return l
	if root2.data == data:
		l.append(data)
		return l
	elif data < root2.data:
		l = second(root2.left, data, l)
	else:
		l = second(root2.right, data, l)
	return l


class Solution:

	def findCommon(self, root1, root2):
		itr1 = Iterator(root1)
		itr2 = Iterator(root2)
		res = []
		while itr1.has_el() and itr2.has_el():
			if itr1.peek() == itr2.peek():
				res.append(itr1.pop())
				itr2.pop()
			elif itr1.peek() < itr2.peek():
				itr1.pop()
			else:
				itr2.pop()
		return res

class Iterator:

	def __init__(self, root):
		self.stack = []
		self.push_all_left(root)

	def pop(self):
		if not self.has_el():
			return
		top = self.stack.pop()
		self.push_all_left(top.right)
		return top.data

	def peek(self):
		if self.has_el():
			return self.stack[-1].data

	def has_el(self):
		return len(self.stack) > 0

	def push_all_left(self, node):
		while node:
			self.stack.append(node)
			node = node.left


class Solution:

	def findCommon(self, root1, root2):

		def inorder(root, l):
			if root == None:
				return
			inorder(root.left, l)
			l.append(root.data)
			inorder(root.right, l)
		res1 = []
		res2 = []
		inorder(root1, res1)
		inorder(root2, res2)
		result = []
		i = 0
		j = 0
		while i < len(res1) and j < len(res2):
			if res1[i] == res2[j]:
				result.append(res1[i])
				i += 1
				j += 1
			elif res1[i] > res2[j]:
				j += 1
			else:
				i += 1
		return result


class Solution:

	def findCommon(self, root1, root2):
		self.stk1 = []
		self.stk2 = []
		self.result = []
		self.inorder(root1, self.stk1)
		self.inorder(root2, self.stk2)
		while self.stk1 and self.stk2:
			if self.stk1[0] == self.stk2[0]:
				self.result.append(self.stk1[0])
				self.stk1.pop(0)
				self.stk2.pop(0)
			elif self.stk1[0] < self.stk2[0]:
				self.stk1.pop(0)
			else:
				self.stk2.pop(0)
		return self.result

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


class Solution:

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

	def findCommon(self, root1, root2):
		l1 = []
		l2 = []
		self.inorder(root1, l1)
		self.inorder(root2, l2)
		res = []
		(i, j) = (0, 0)
		while i < len(l1) and j < len(l2):
			if l1[i] == l2[j]:
				res.append(l1[i])
				i += 1
				j += 1
			elif l1[i] > l2[j]:
				j += 1
			else:
				i += 1
		return res


class Solution:

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

	def findCommon(self, root1, root2):
		arr = set(self.inorder(root1)) & set(self.inorder(root2))
		arr = list(arr)
		return sorted(arr)


class Solution:

	def findCommon(self, root1, root2):
		final = []
		if root1 is None and root2 is None:
			return final
		lst1 = self.PreOrderTravl(root1, [])
		lst2 = self.PreOrderTravl(root2, [])
		a_set = set(lst1)
		b_set = set(lst2)
		if a_set & b_set:
			lstres = list(a_set & b_set)
			lstres.sort()
			return lstres
		return final

	def PreOrderTravl(self, root, lst):
		if root is None:
			return lst
		lst.append(root.data)
		lst = self.PreOrderTravl(root.left, lst)
		lst = self.PreOrderTravl(root.right, lst)
		return lst


class Solution:

	def findCommon(self, root1, root2):
		set1 = set()
		set2 = set()

		def dfs(root, s):
			if not root:
				return
			dfs(root.left, s)
			s.add(root.data)
			dfs(root.right, s)
		dfs(root1, set1)
		dfs(root2, set2)
		res = list(set1.intersection(set2))
		res.sort()
		return res


class Solution:

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

	def findCommon(self, root1, root2):
		s1 = self.lot(root1)
		s2 = self.lot(root2)
		l = list(s1.intersection(s2))
		l.sort()
		return l


class Solution:

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

		def inorder(rt1, t):
			if rt1.left:
				inorder(rt1.left, t)
			t.append(rt1.data)
			if rt1.right:
				inorder(rt1.right, t)
		inorder(root1, l1)
		inorder(root2, l2)
		num1 = set(l1)
		num2 = set(l2)
		num3 = num1.intersection(num2)
		num3 = list(num3)
		num3.sort()
		return num3


class Solution:

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

	def findCommon(self, root1, root2):
		l = []
		t = []
		self.inorder(root1, l)
		self.inorder(root2, t)
		return sorted(list(set(t).intersection(l)))


class Solution:

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

	def findCommon(self, root1, root2):
		l1 = set(self.inorder(root1))
		l2 = set(self.inorder(root2))
		return sorted(list(l1.intersection(l2)))


class Solution:

	def findCommon(self, root1, root2):
		s1 = set()
		s2 = set()

		def traverse(root, s):
			if root == None:
				return
			traverse(root.left, s)
			s.add(root.data)
			traverse(root.right, s)
		traverse(root1, s1)
		traverse(root2, s2)
		return sorted(s1 & s2)


class Solution:

	def __init__(self):
		self.d = {}
		self.res = []

	def f(self, root, l):
		if root == None:
			return
		self.f(root.left, l)
		self.d[root.data] = 0
		self.f(root.right, l)

	def f2(self, root, l):
		if root == None:
			return
		self.f2(root.left, l)
		if root.data in self.d.keys():
			self.res.append(root.data)
		self.f2(root.right, l)

	def findCommon(self, root1, root2):
		self.f(root1, None)
		self.f2(root2, None)
		return self.res


class Solution:

	def findCommon(self, root1, root2):
		n1 = []
		n2 = []
		inorder(root1, n1)
		inorder(root2, n2)
		ans = []
		i = j = 0
		while i < len(n1) and j < len(n2):
			if n1[i] == n2[j]:
				ans.append(n1[i])
				i += 1
				j += 1
			elif n1[i] < n2[j]:
				i += 1
			else:
				j += 1
		return ans

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


class Solution:

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

		def inorder(root1):
			if root1 is None:
				return []
			else:
				inorder(root1.left)
				l1.append(root1.data)
				inorder(root1.right)
				return l1

		def postorder(root2):
			if root2 is None:
				return []
			else:
				postorder(root2.left)
				postorder(root2.right)
				l2.append(root2.data)
				return l2
		lst1 = inorder(root1)
		lst2 = postorder(root2)
		s1 = set()
		s2 = set()
		for x in lst1:
			s1.add(x)
		for x in lst2:
			s2.add(x)
		s3 = s1.intersection(s2)
		ans = []
		for x in s3:
			ans.append(x)
		ans.sort()
		return ans


class Solution:

	def helper(self, root, d, l):
		if not root:
			return root
		self.helper(root.left, d, l)
		if root.data in d:
			l.append(root.data)
		else:
			d[root.data] = 1
		self.helper(root.right, d, l)

	def findCommon(self, root1, root2):
		d = {}
		l = []
		self.helper(root1, d, l)
		self.helper(root2, d, l)
		return l


from collections import deque

class Solution:

	def findCommon(self, root1, root2):
		hash = {}
		q = deque()
		q.append(root1)
		while q:
			count = len(q)
			while count > 0:
				a = q.pop()
				if a.data not in hash:
					hash[a.data] = 1
				if a.left != None:
					q.append(a.left)
				if a.right != None:
					q.append(a.right)
				count -= 1
		q = deque()
		q.append(root2)
		sol = []
		while q:
			count = len(q)
			while count > 0:
				a = q.pop()
				if a.data in hash:
					sol.append(a.data)
				if a.left != None:
					q.append(a.left)
				if a.right != None:
					q.append(a.right)
				count -= 1
		sol.sort()
		return sol