Given two BSTs containing N1 and N2 distinct nodes respectively and given a value x. Your task is to complete the function countPairs(), that returns the count of all pairs from both the BSTs whose sum is equal to x.
Example 1:
Input:
BST1:
       5
     /   \
    3     7
   / \   / \
  2   4 6   8
BST2:
       10
     /    \
    6      15
   / \    /  \
  3   8  11   18
x = 16
Output:
3
Explanation:
The pairs are: (5, 11), (6, 10) and (8, 8)
 
Example 2:
Input:
BST1:
  1
   \
    3
   /
  2
BST2:
    3
   / \
  2   4
 /     
1
x = 4
Output:
3
Explanation:
The pairs are: (2, 2), (3, 1) and (1, 3)
Your Task:
You don't need to read input or print anything. Your task is to complete the function countPairs(), which takes 2 BST's as parameter in form of root1 and root2 and the integer x, that returns the count of all pairs from both the BSTs whose sum is equal to x.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ Number of nodes ≤ 10^{5}
1 ≤ Data of a node ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Graph traversal

Range queries

Starter code: #User function Template for python3

'''
# Tree Node
class Node:
    def __init__(self, val):
        self.right = None
        self.data = val
        self.left = None
'''

class Solution:
    def countPairs(self, root1, root2, x): 
        #code here.

Solutions:
class Solution:

	def inorder(self, root):
		ans = []
		curr = root
		while curr:
			if curr.left is None:
				ans.append(curr.data)
				curr = curr.right
			else:
				pred = curr.left
				while pred.right and pred.right != curr:
					pred = pred.right
				if pred.right is None:
					pred.right = curr
					curr = curr.left
				else:
					pred.right = None
					ans.append(curr.data)
					curr = curr.right
		return ans

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


class Solution:

	def countPairs(self, root1, root2, x):

		def Inorder(root):
			if root == None:
				return
			Inorder(root.left)
			ans.append(root.data)
			Inorder(root.right)
		ans = []
		Inorder(root1)
		ans1 = ans
		ans = []
		Inorder(root2)
		ans2 = ans[::-1]
		(cnt, i, j) = (0, 0, 0)
		while i < len(ans1) and j < len(ans2):
			sum_val = ans1[i] + ans2[j]
			if sum_val == x:
				cnt += 1
				i += 1
				j += 1
			elif sum_val > x:
				j += 1
			else:
				i += 1
		return cnt


class Solution:

	def countPairs(self, root1, root2, x):
		in1 = []
		in2 = []
		c = 0

		def inorder1(root):
			if root is None:
				return
			inorder1(root.left)
			in1.append(root.data)
			inorder1(root.right)

		def inorder2(root):
			if root is None:
				return
			inorder2(root.left)
			in2.append(root.data)
			inorder2(root.right)
		inorder1(root1)
		inorder2(root2)
		i = 0
		j = len(in2) - 1
		while i < len(in1) and j >= 0:
			if in1[i] + in2[j] == x:
				c += 1
				i += 1
				j -= 1
			elif in1[i] + in2[j] < x:
				i += 1
			else:
				j -= 1
		return c


class Solution:

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

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


class Solution:

	def countPairs(self, root1, root2, x):

		def inorder(root, y):
			if root == None:
				return
			inorder(root.left, y)
			y.append(root.data)
			inorder(root.right, y)
		a = []
		b = []
		inorder(root1, a)
		inorder(root2, b)
		i = 0
		j = len(b) - 1
		c = 0
		while i < len(a) and j >= 0:
			if a[i] + b[j] == x:
				c = c + 1
				i = i + 1
				j = j - 1
			elif a[i] + b[j] > x:
				j = j - 1
			else:
				i = i + 1
		return c


class Solution:

	def countPairs(self, root1, root2, x):
		stack1 = []
		stack2 = []
		count = 0
		while 1:
			while root1 is not None:
				stack1.append(root1)
				root1 = root1.left
			while root2 is not None:
				stack2.append(root2)
				root2 = root2.right
			if len(stack1) == 0 or len(stack2) == 0:
				return count
			top1 = stack1[-1]
			top2 = stack2[-1]
			if top1.data + top2.data == x:
				count += 1
				stack1.pop()
				stack2.pop()
				root1 = top1.right
				root2 = top2.left
			elif top1.data + top2.data < x:
				stack1.pop()
				root1 = top1.right
			else:
				stack2.pop()
				root2 = top2.left
		return count


def in_order_util(root: Node, dict_map: {}):
	if root is None:
		return
	in_order_util(root.left, dict_map)
	dict_map[root.data] = 1
	in_order_util(root.right, dict_map)

class Solution:

	def countPairs(self, root_1, root_2, sum_value):
		dict_map_1 = {}
		in_order_util(root_1, dict_map_1)
		dict_map_2 = {}
		in_order_util(root_2, dict_map_2)
		count = 0
		for key in dict_map_1:
			need = sum_value - key
			if need in dict_map_2:
				count = count + 1
		return count


class Solution:

	def store(self, root, d):
		if root is None:
			return
		d[root.data] = 1
		self.store(root.left, d)
		self.store(root.right, d)

	def countPairs(self, root1, root2, x):
		out = []
		d1 = {}
		d2 = {}
		self.store(root1, d1)
		self.store(root2, d2)
		for itr in d2.keys():
			if d1.get(x - itr):
				out.append([x - itr, itr])
		return len(out)


class Solution:

	def countPairs(self, root1, root2, x):
		mp = dict()

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			if root.data not in mp:
				mp[root.data] = 1
			else:
				mp[root.data] += 1
			inorder(root.right)
		inorder(root1)
		count = [0]

		def inorder2(root, x):
			if root == None:
				return
			inorder2(root.left, x)
			if x - root.data in mp:
				count[0] += 1
			inorder2(root.right, x)
		inorder2(root2, x)
		return count[0]


import sys
sys.setrecursionlimit(50000)

class Solution:

	def __init__(self):
		self.count = 0

	def countPairs(self, root1, root2, x):

		def inorder(root, a):
			if root:
				inorder(root.left, a)
				a.append(root.data)
				inorder(root.right, a)
		(l1, l2) = ([], [])
		inorder(root1, l1)
		inorder(root2, l2)
		i = 0
		j = len(l2) - 1
		while i < len(l1) and j >= 0:
			summ = l1[i] + l2[j]
			if summ == x:
				self.count += 1
				i += 1
			elif summ < x:
				i += 1
			else:
				j -= 1
		return self.count


class Solution:

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

	def count(self, arr1, arr2, x):
		cnt = 0
		(i, j) = (0, len(arr2) - 1)
		(n1, n2) = (len(arr1), len(arr2))
		while i < n1 and j >= 0:
			if arr1[i] + arr2[j] == x:
				cnt += 1
				i += 1
				j -= 1
			elif arr1[i] + arr2[j] < x:
				i += 1
			else:
				j -= 1
		return cnt

	def countPairs(self, root1, root2, x):
		l = []
		self.inorder(root1, l)
		t = []
		self.inorder(root2, t)
		return self.count(l, t, x)


class Solution:

	def countPairs(self, root1, root2, x):
		count = 0
		s1 = []
		s2 = []
		while 1:
			while root1 != None:
				s1.append(root1)
				root1 = root1.left
			while root2 != None:
				s2.append(root2)
				root2 = root2.right
			if len(s1) == 0 or len(s2) == 0:
				break
			top1 = s1[-1]
			top2 = s2[-1]
			if top1.data + top2.data == x:
				count += 1
				s1.pop(-1)
				s2.pop(-1)
				root1 = top1.right
				root2 = top2.left
			elif top1.data + top2.data > x:
				s2.pop(-1)
				root2 = top2.left
			else:
				s1.pop(-1)
				root1 = top1.right
		return count


class Solution:

	def generatedict(self, root, d):
		if root == None:
			return d
		d[root.data] = 1
		d = self.generatedict(root.left, d)
		d = self.generatedict(root.right, d)
		return d

	def f(self, root2, x, d, count):
		if root2 == None:
			return count
		if x - root2.data in d:
			count[0] += 1
		self.f(root2.left, x, d, count)
		self.f(root2.right, x, d, count)

	def countPairs(self, root1, root2, x):
		count = [0]
		d = dict()
		d = self.generatedict(root1, d)
		self.f(root2, x, d, count)
		return count[0]


class Solution:

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

	def countPairs(self, root1, root2, x):
		inord1 = []
		inord2 = []
		self.inorder(root1, inord1)
		self.inorder(root2, inord2)
		i = 0
		j = len(inord2) - 1
		count = 0
		while i < len(inord1) and j >= 0:
			add = inord1[i] + inord2[j]
			if add == x:
				count += 1
				i += 1
				j -= 1
			elif add < x:
				i += 1
			else:
				j -= 1
		return count


class Solution:

	def inorder(self, root, node_map):
		if root:
			self.inorder(root.left, node_map)
			node_map[root.data] = 1
			self.inorder(root.right, node_map)

	def countPairs(self, root1, root2, x):
		map_1 = {}
		map_2 = {}
		self.inorder(root1, map_1)
		self.inorder(root2, map_2)
		count = 0
		for (k, v) in map_1.items():
			a = x - k
			if map_2.get(a):
				count += 1
		return count


class Solution:

	def countPairs(self, root1, root2, x):
		if root1 is None or root2 is None:
			return 0
		st1 = []
		st2 = []
		top1 = Node(-1)
		top2 = Node(-1)
		count = 0
		while 1:
			while root1 != None:
				st1.append(root1)
				root1 = root1.left
			while root2 != None:
				st2.append(root2)
				root2 = root2.right
			if len(st1) == 0 or len(st2) == 0:
				break
			top1 = st1[len(st1) - 1]
			top2 = st2[len(st2) - 1]
			if top1.data + top2.data == x:
				count = count + 1
				st1.pop()
				st2.pop()
				root1 = top1.right
				root2 = top2.left
			elif top1.data + top2.data < x:
				st1.pop()
				root1 = top1.right
			else:
				st2.pop()
				root2 = top2.left
		return count


class Solution:

	def solve(self, root, dic):
		if root is None:
			return
		dic[root.data] = 1
		self.solve(root.left, dic)
		self.solve(root.right, dic)

	def solve1(self, root, dic, li, X):
		if root is None:
			return
		if X - root.data in dic:
			li.append(root.data)
		self.solve1(root.left, dic, li, X)
		self.solve1(root.right, dic, li, X)

	def countPairs(self, root1, root2, x):
		dic = {}
		li = []
		self.solve(root1, dic)
		self.solve1(root2, dic, li, x)
		return len(li)


class Solution:

	def countPairs(self, root1, root2, x):
		count = 0
		arr1 = []
		arr2 = []
		inorder(root1, arr1)
		inorder(root2, arr2)
		i = 0
		j = len(arr2) - 1
		while i < len(arr1) and j >= 0:
			if arr1[i] + arr2[j] == x:
				i += 1
				j -= 1
				count += 1
			elif arr1[i] + arr2[j] < x:
				i += 1
			else:
				j -= 1
		return count

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


class Solution:

	def countPairs(self, root1, root2, x):
		count = 0
		arr1 = []
		arr2 = []
		inorder(root1, arr1)
		inorder(root2, arr2)
		return countPairs(arr1, arr2, len(arr1), len(arr2), x)

def countPairs(arr1, arr2, m, n, x):
	count = 0
	us = set()
	for i in range(m):
		us.add(arr1[i])
	for j in range(n):
		if x - arr2[j] in us:
			count += 1
	return count

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


class Solution:

	def countPairs(self, root1, root2, x):
		inorder1 = []
		inorder2 = []
		cur = root1
		while cur:
			if not cur.left:
				inorder1.append(cur.data)
				cur = cur.right
			else:
				pred = cur.left
				while pred.right and pred.right != cur:
					pred = pred.right
				if not pred.right:
					pred.right = cur
					cur = cur.left
				else:
					pred.right = None
					inorder1.append(cur.data)
					cur = cur.right
		cur = root2
		while cur:
			if not cur.left:
				inorder2.append(cur.data)
				cur = cur.right
			else:
				pred = cur.left
				while pred.right and pred.right != cur:
					pred = pred.right
				if not pred.right:
					pred.right = cur
					cur = cur.left
				else:
					pred.right = None
					inorder2.append(cur.data)
					cur = cur.right
		count = 0
		(i, j) = (0, len(inorder2) - 1)
		while i < len(inorder1) and j > -1:
			temp = inorder1[i] + inorder2[j]
			if temp == x:
				count += 1
				i += 1
				j -= 1
			elif temp < x:
				i += 1
			else:
				j -= 1
		return count


class Solution:

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

	def countPairs(self, root1, root2, x):
		arr1 = self.inorder(root1, [])
		arr2 = self.inorder(root2, [])
		counter = 0
		i = 0
		j = len(arr2) - 1
		while i < len(arr1) and j >= 0:
			sum = arr1[i] + arr2[j]
			if sum > x:
				j = j - 1
			elif sum < x:
				i = i + 1
			else:
				counter = counter + 1
				i = i + 1
				j = j - 1
		return counter


from bisect import bisect_left

class Solution:

	def countPairs(self, root1, root2, x):
		arr = self.helper(root1, x)
		return self.helper2(root2, arr)

	def helper2(self, root, arr):
		if root is None:
			return 0
		output = 0
		i = bisect_left(arr, root.data)
		output += self.helper2(root.left, arr[:i])
		if i < len(arr):
			output += arr[i] == root.data
			output += self.helper2(root.right, arr[i:])
		return output

	def helper(self, root, x):
		if root is None:
			return []
		output = self.helper(root.right, x)
		if root.data < x:
			output.append(x - root.data)
		output += self.helper(root.left, x)
		return output


class Solution:

	def store(self, root, h):
		if root:
			self.store(root.left, h)
			h[root.data] = h.get(root.data, 0) + 1
			self.store(root.right, h)

	def findAns(self, root, h, x):
		if not root:
			return 0
		ans = 0
		if x - root.data in h:
			ans += h[x - root.data]
		return ans + self.findAns(root.left, h, x) + self.findAns(root.right, h, x)

	def countPairs(self, root1, root2, x):
		h = {}
		self.store(root1, h)
		return self.findAns(root2, h, x)


class Solution:

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

	def countPairs(self, root1, root2, x):
		l1 = self.solve(root1, [])
		l2 = self.solve(root2, [])
		(i, j) = (0, len(l2) - 1)
		c = 0
		while i < len(l1) and j > -1:
			if l1[i] + l2[j] > x:
				j -= 1
			elif l1[i] + l2[j] < x:
				i += 1
			else:
				c += 1
				if i < len(l1) - 1 and l1[i + 1] == l1[i]:
					i += 1
				else:
					j -= 1
		return c


class Solution:

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

	def countPairs(self, root1, root2, x):
		arr1 = []
		arr2 = []
		self.inorder(root1, arr1)
		self.inorder(root2, arr2)
		counter = 0
		ctr1 = 0
		ctr2 = len(arr2) - 1
		while ctr1 < len(arr1) and ctr2 >= 0:
			if arr1[ctr1] + arr2[ctr2] == x:
				counter += 1
				ctr1 += 1
				ctr2 -= 1
			elif arr1[ctr1] + arr2[ctr2] < x:
				ctr1 += 1
			else:
				ctr2 -= 1
		return counter


class Solution:

	def countPairs(self, root1, root2, x):

		def inorder(root, d):
			if root:
				inorder(root.left, d)
				d[root.data] = 1
				inorder(root.right, d)
		d1 = {}
		d2 = {}
		q1 = [root1]
		q2 = [root2]
		inorder(root1, d1)
		inorder(root2, d2)
		res = 0
		for i in d1:
			if x - i in d2:
				res += 1
		return res


class Solution:

	def countPairs(self, root1, root2, x):
		count = 0
		bst1Nodes = set()

		def findpairs(root):
			nonlocal count
			if x - root.data in bst1Nodes:
				count += 1
			if root.left:
				findpairs(root.left)
			if root.right:
				findpairs(root.right)

		def traverse(root):
			bst1Nodes.add(root.data)
			if root.left:
				traverse(root.left)
			if root.right:
				traverse(root.right)
		traverse(root1)
		findpairs(root2)
		return count


class Solution:

	def countPairs(self, root1, root2, x):
		global a, b
		(a, b) = ([], [])

		def sol1(root1):
			global a
			if root1:
				sol1(root1.left)
				a.append(root1.data)
				sol1(root1.right)
		sol1(root1)

		def sol2(root2):
			global b
			if root2:
				sol2(root2.left)
				b.append(root2.data)
				sol2(root2.right)
		sol2(root2)
		i = 0
		j = len(b) - 1
		c = 0
		while i < len(a) and j >= 0:
			if a[i] + b[j] == x:
				c = c + 1
				i = i + 1
			elif a[i] + b[j] > x:
				j = j - 1
			else:
				i = i + 1
		return c


class Solution:

	def countPairs(self, root1, root2, x):
		c = []
		l = []
		d = {}
		self.inorder(root1, x, c, l)
		self.helpe1(l, d)
		self.helper(root2, d, c)
		return sum(c)

	def inorder(self, root1, x, c, l):
		if root1.left:
			if root1.left.data < x:
				self.inorder(root1.left, x, c, l)
			elif root1.left.left:
				self.inorder(root1.left.left, x, c, l)
		a = x - root1.data
		l.append(a)
		if root1.right:
			if root1.right.data < x:
				self.inorder(root1.right, x, c, l)
			elif root1.right.left:
				self.inorder(root1.right.left, x, c, l)

	def helpe1(self, l, d):
		for i in l:
			if i not in d:
				d[i] = [1]
			else:
				d[i] += [1]

	def helper(self, root2, d, c):
		if not root2:
			return
		try:
			a = sum(d[root2.data])
			if a >= 1:
				c += [a]
				return
		except:
			pass
		finally:
			if root2.left:
				self.helper(root2.left, d, c)
			if root2.right:
				self.helper(root2.right, d, c)


class Solution:

	def countPairs(self, root1, root2, x):
		d = dict()
		c = [0]

		def s1(root1):
			if not root1:
				return
			if root1.left:
				s1(root1.left)
			d[root1.data] = 1
			if root1.right:
				s1(root1.right)

		def s2(root2):
			if not root2:
				return
			if root2.left:
				s2(root2.left)
			if x - root2.data in d.keys():
				c[0] += 1
			if root2.right:
				s2(root2.right)
		s1(root1)
		s2(root2)
		return c[0]


def inorder(roots, l):
	if roots != None:
		inorder(roots.left, l)
		l.append(roots.data)
		inorder(roots.right, l)

class Solution:

	def countPairs(self, root1, root2, x):
		c = 0
		l1 = []
		inorder(root1, l1)
		l2 = []
		inorder(root2, l2)
		c = 0
		p1 = 0
		p2 = len(l2) - 1
		while p1 < len(l1) and p2 >= 0:
			s = l1[p1] + l2[p2]
			if s == x:
				c = c + 1
				p1 = p1 + 1
				p2 = p2 - 1
			elif s > x:
				p2 = p2 - 1
			else:
				p1 = p1 + 1
		return c


class Solution:

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

	def countPairs(self, root1, root2, x):
		(arr1, arr2) = ([], [])
		if root1 is None or root2 is None:
			return count
		self.inorder(root1, arr1)
		self.inorder(root2, arr2)
		(n1, n2) = (len(arr1), len(arr2))
		i = 0
		j = n2 - 1
		count = 0
		while i < n1 and j >= 0:
			val = arr1[i] + arr2[j]
			if val == x:
				count += 1
				j -= 1
				i += 1
			elif val > x:
				j -= 1
			else:
				i += 1
		return count


class Solution:

	def countPairs(self, root1, root2, x):

		def inorder(node, arr):
			if not node:
				return
			inorder(node.left, arr)
			arr.append(node.data)
			inorder(node.right, arr)
			return
		arr1 = []
		arr2 = []
		inorder(root1, arr1)
		inorder(root2, arr2)
		ptr1 = 0
		ptr2 = len(arr2) - 1
		count = 0
		while ptr1 < len(arr1) and ptr2 >= 0:
			Sum = arr1[ptr1] + arr2[ptr2]
			if Sum == x:
				count += 1
				ptr1 += 1
				ptr2 -= 1
			elif Sum > x:
				ptr2 -= 1
			else:
				ptr1 += 1
		return count


class Solution:

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

	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 countPairs(self, root1, root2, x):
		self.InOrder1(root1)
		self.InOrder2(root2)
		p1 = 0
		p2 = len(self.inorder2) - 1
		count = 0
		while p1 < len(self.inorder1) and p2 > -1:
			SUM = self.inorder1[p1] + self.inorder2[p2]
			if SUM == x:
				count += 1
				p1 += 1
			elif SUM < x:
				p1 += 1
			elif SUM > x:
				p2 -= 1
		return count


class Solution:

	def find(self, root1, root2, x):
		if not root1:
			return False
		if root1.data == x:
			return True
		if root1.data > x:
			return self.find(root1.left, root2, x)
		else:
			return self.find(root1.right, root2, x)

	def util(self, root1, root2, x, ans):
		if not root2:
			return
		y = x - root2.data
		if self.find(root1, root2, y):
			ans.append((y, x))
		self.util(root1, root2.left, x, ans)
		self.util(root1, root2.right, x, ans)

	def countPairs(self, root1, root2, x):
		ans = []
		self.util(root1, root2, x, ans)
		return len(ans)


class Solution:

	def countPairs(self, root1, root2, x):

		def helper(root):
			d = []
			if not root:
				return d
			d.append(root.data)
			d += helper(root.left)
			d += helper(root.right)
			return d
		a = helper(root1)
		b = helper(root2)
		c = {}
		for i in b:
			c[i] = 1
		count = 0
		for i in a:
			t = x - i
			if t in c:
				count += 1
		return count


class Solution:

	def countPairs(self, root1, root2, x):
		arr1 = []
		arr2 = []
		a1 = self.inorder(root1, arr1)
		a2 = self.inorder(root2, arr2)
		count = 0
		hash = {}
		for i in a2:
			hash[i] = True
		for i in a1:
			if x - i in hash:
				count += 1
		return count

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


import collections

class Solution:

	def countPairs(self, root1, root2, x):
		mp = collections.defaultdict(int)

		def inorder1(root):
			if not root:
				return
			inorder1(root.left)
			mp[x - root.data] += 1
			inorder1(root.right)
		inorder1(root1)
		count = [0]

		def inorder2(root, count):
			if not root:
				return
			inorder2(root.left, count)
			if mp[root.data] > 0:
				count[0] += 1
				mp[root.data] -= 1
			inorder2(root.right, count)
		inorder2(root2, count)
		return count[0]


class Solution:

	def countPairs(self, root1, root2, x):
		s = set()
		dfs_set(root1, s)
		cnt = dfs_count_matches(root2, x, s)
		return cnt

def dfs_set(n, s):
	if not n:
		return
	s.add(n.data)
	dfs_set(n.left, s)
	dfs_set(n.right, s)

def dfs_count_matches(n, x, s):
	if not n:
		return 0
	cnt = 1 if x - n.data in s else 0
	l = dfs_count_matches(n.left, x, s)
	r = dfs_count_matches(n.right, x, s)
	return cnt + l + r


class Solution:

	def countPairs(self, root1, root2, x):

		def inorder(node, arr):
			if not node:
				return
			inorder(node.left, arr)
			arr.append(node.data)
			inorder(node.right, arr)
			return
		arr1 = []
		arr2 = []
		inorder(root1, arr1)
		inorder(root2, arr2)
		i = 0
		j = len(arr2) - 1
		cnt = 0
		while i < len(arr1) and j >= 0:
			if arr1[i] + arr2[j] == x:
				cnt += 1
				i += 1
				j -= 1
			elif arr1[i] + arr2[j] > x:
				j -= 1
			else:
				i += 1
		return cnt


class Solution:

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

	def countPairs(self, root1, root2, x):
		(list1, list2) = ([], [])
		self.inorder(root1, list1)
		self.inorder(root2, list2)
		count = 0
		(i, j) = (0, len(list2) - 1)
		while i < len(list1) and j >= 0:
			sumv = list1[i] + list2[j]
			if sumv == x:
				count += 1
				i += 1
				j -= 1
			elif sumv > x:
				j -= 1
			else:
				i += 1
		return count


class Solution:

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

	def revIno(self, root):
		curr = root
		stack = []
		stack.append(curr)
		while curr.right:
			stack.append(curr.right)
			curr = curr.right
		return stack

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

	def popIno(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 countPairs(self, root1, root2, x):
		stack1 = self.revIno(root1)
		stack2 = self.inorder(root2)
		res = 0
		while len(stack1) and len(stack2):
			a = stack1[len(stack1) - 1]
			b = stack2[len(stack2) - 1]
			if a.data + b.data == x:
				self.popRev(stack1)
				self.popIno(stack2)
				res += 1
			elif a.data + b.data > x:
				self.popRev(stack1)
			else:
				self.popIno(stack2)
		return res


class Solution:

	def countPairs(self, root1, root2, x):
		res = [0]
		hm = {}

		def dfs(root):
			if not root:
				return
			dfs(root.left)
			hm[root.data] = hm.get(root.data, 0) + 1
			dfs(root.right)

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			if x - root.data in hm:
				res[0] += 1
			inorder(root.right)
		dfs(root1)
		inorder(root2)
		return res[0]


class Solution:

	def countPairs(self, root1, root2, x):
		count = 0
		st1 = deque()
		st2 = deque()
		current1 = root1
		current2 = root2
		while True:
			while current1:
				st1.append(current1)
				current1 = current1.left
			while current2:
				st2.append(current2)
				current2 = current2.right
			if not st1 or not st2:
				break
			nd1 = st1.pop()
			nd2 = st2.pop()
			if nd1.data + nd2.data == x:
				count += 1
				current1 = nd1.right
				current2 = nd2.left
			elif nd1.data + nd2.data < x:
				current1 = nd1.right
				st2.append(nd2)
			else:
				current2 = nd2.left
				st1.append(nd1)
		return count


def countPairs1(root1, root2, x):
	if root1 == None or root2 == None:
		return 0
	st1 = []
	st2 = []
	count = 0
	c = 0
	while 1:
		while root1 != None:
			st1.append(root1)
			root1 = root1.left
		while root2 != None:
			st2.append(root2)
			root2 = root2.right
		if len(st1) == 0 and root1 == None or (len(st2) == 0 and root2 == None):
			break
		top1 = st1[len(st1) - 1]
		top2 = st2[len(st2) - 1]
		if top1.data + top2.data == x:
			count += 1
			st1.remove(st1[len(st1) - 1])
			st2.remove(st2[len(st2) - 1])
			root1 = top1.right
			root2 = top2.left
		elif top1.data + top2.data < x:
			st1.remove(st1[len(st1) - 1])
			root1 = top1.right
		else:
			st2.remove(st2[len(st2) - 1])
			root2 = top2.left
	return count

class Solution:

	def countPairs(self, root1, root2, x):
		return countPairs1(root1, root2, x)


def inorder(root):
	res = []
	if root is None:
		return res
	q = []
	cur = root
	while True:
		if cur is not None:
			q.append(cur)
			cur = cur.left
		elif q:
			cur = q.pop()
			res.append(cur.data)
			cur = cur.right
		else:
			break
	return res

class Solution:

	def countPairs(self, root1, root2, x):
		c = 0
		ar1 = inorder(root1)
		ar2 = inorder(root2)
		i = 0
		j = len(ar2) - 1
		while i < len(ar1) and j >= 0:
			jk = ar1[i] + ar2[j]
			if jk == x:
				c += 1
				i += 1
				j -= 1
			elif jk > x:
				j -= 1
			else:
				i += 1
		return c


class Solution:

	def countPairs(self, root1, root2, x):

		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)
		count = 0
		(length1, length2) = (len(arr1), len(arr2))
		dict2 = {i: 1 for i in arr2}
		for i in range(length1):
			if x - arr1[i] in dict2:
				count += 1
		return count


class Solution:

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

	def countPairs(self, root1, root2, x):
		if not root1 or not root2:
			return -1
		l1 = []
		l2 = []
		ans = []
		self.inorder(root1, l1)
		self.inorder(root2, l2)
		i = 0
		j = len(l2) - 1
		while i < len(l1) and j > -1:
			if l1[i] + l2[j] == x:
				ans.append([l1[i], l2[j]])
				i += 1
				j -= 1
			elif l1[i] + l2[j] > x:
				j -= 1
			else:
				i += 1
		return len(ans)


class Solution:

	def countPairs(self, root1, root2, x):
		d = {}
		self.inorder(root1, d)
		ino = []
		self.inorderarr(root2, ino)
		out = []
		c = 0
		for i in range(len(ino)):
			temp = x - ino[i]
			if temp in d:
				c += 1
		return c

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

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


class Solution:

	def countPairs(self, root1, root2, x):
		self.pairs = {}
		self.res = 0
		self.ltraverse(root1)
		self.checkpairs(root2, x)
		return self.res

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

	def checkpairs(self, root, x):
		if not root:
			return
		if x - root.data in self.pairs:
			self.res += 1
		self.checkpairs(root.left, x)
		self.checkpairs(root.right, x)


class Solution:

	def countPairs(self, root1, root2, x):
		arr = []
		arr1 = []
		count = 0

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

		def tree2(root):
			if not root:
				return
			tree2(root.left)
			arr1.append(root.data)
			tree2(root.right)
		tree1(root1)
		tree2(root2)
		(i, j) = (0, len(arr1) - 1)
		while i < len(arr) and j >= 0:
			if arr[i] + arr1[j] == x:
				count += 1
				j -= 1
			elif arr[i] + arr1[j] < x:
				i += 1
			else:
				j -= 1
		return count


class Solution:

	def countPairs(self, root1, root2, x):
		if root1 == None or root2 == None:
			return 0
		cnt = 0
		s1 = []
		s2 = []
		while True:
			while root1:
				s1.append(root1)
				root1 = root1.left
			while root2:
				s2.append(root2)
				root2 = root2.right
			if len(s1) == 0 or len(s2) == 0:
				break
			top1 = s1[-1]
			top2 = s2[-1]
			s = top1.data + top2.data
			if s == x:
				cnt += 1
				s1.remove(top1)
				s2.remove(top2)
				root1 = top1.right
				root2 = top2.left
			elif s < x:
				s1.remove(top1)
				root1 = top1.right
			else:
				s2.remove(top2)
				root2 = top2.left
		return cnt


class Solution:

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

	def inorder_final(self, root, x, st, count):
		if root is None:
			return
		self.inorder_final(root.left, x, st, count)
		if x - root.data in st:
			count[0] += 1
		self.inorder_final(root.right, x, st, count)

	def countPairs(self, root1, root2, x):
		st = set()
		self.inorder(root1, st)
		count = [0]
		self.inorder_final(root2, x, st, count)
		return count[0]


class Solution:

	def srchinright(self, root, val):
		if root is None:
			return False
		while root:
			if val < root.data:
				root = root.left
			elif val > root.data:
				root = root.right
			elif val == root.data:
				self.c[0] += 1
				break

	def trav_left(self, root, S):
		if root is None:
			return None
		self.srchinright(self.root2, S - root.data)
		self.trav_left(root.left, S)
		self.trav_left(root.right, S)

	def countPairs(self, root1, root2, S):
		self.root1 = root1
		self.root2 = root2
		self.S = S
		self.c = [0]
		self.trav_left(root1, S)
		return self.c[0]


class Solution:

	def countPairs(self, root1, root2, x):

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


from collections import deque

class Solution:

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

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

	def countPairs(self, root1, root2, x):
		count = 0
		stack1 = deque()
		stack2 = deque()
		tmp = root1
		while tmp:
			stack1.append(tmp)
			tmp = tmp.left
		tmp = root2
		while tmp:
			stack2.append(tmp)
			tmp = tmp.right
		while len(stack1) and len(stack2):
			x1 = stack1[-1].data
			x2 = stack2[-1].data
			if x1 + x2 == x:
				count += 1
				tmp1 = stack1.pop()
				tmp2 = stack2.pop()
				self.moveLeft(tmp1, stack1)
				self.moveRight(tmp2, stack2)
			elif x1 + x2 > x:
				tmp2 = stack2.pop()
				self.moveRight(tmp2, stack2)
			else:
				tmp1 = stack1.pop()
				self.moveLeft(tmp1, stack1)
		return count


class Solution:

	def countPairs(self, root1, root2, x):

		def findele(root, x):
			while root:
				if root.data == x:
					return root.data
				if root.data > x:
					root = root.left
				else:
					root = root.right
			return -1
		self.c = 0

		def solve(root):
			if root == None:
				return
			y = x - root.data
			find = findele(root2, x - root.data)
			if find != -1:
				self.c += 1
			solve(root.left)
			solve(root.right)
		solve(root1)
		return self.c


class Solution:

	def countPairs(self, root1, root2, x):
		target = x
		arr1 = []
		inorder(root1, arr1)
		arr2 = []
		inorder(root2, arr2)
		cnt = 0
		start = 0
		end = len(arr2) - 1
		while start < len(arr1) and end > -1:
			sm = arr1[start] + arr2[end]
			if sm == target:
				cnt += 1
				start += 1
				end -= 1
			elif sm > target:
				end -= 1
			else:
				start += 1
		return cnt

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


class Solution:

	def countPairs(self, root1, root2, x):
		arr1 = []
		arr2 = []

		def inorder(root, arr):
			if not root:
				return
			inorder(root.left, arr)
			arr.append(root.data)
			inorder(root.right, arr)
		inorder(root1, arr1)
		inorder(root2, arr2)
		(m, n) = (len(arr1), len(arr2))
		(i, j) = (0, n - 1)
		ans = 0
		while i < m and j >= 0:
			if arr1[i] + arr2[j] > x:
				j -= 1
			elif arr1[i] + arr2[j] < x:
				i += 1
			else:
				ans += 1
				i += 1
		return ans


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

class Solution:

	def countPairs(self, root1, root2, x):
		arr1 = inorder(root1, [])
		arr2 = inorder(root2, [])
		for i in range(len(arr1)):
			arr1[i] = x - arr1[i]
		set1 = set(arr1)
		set2 = set(arr2)
		set3 = set1.intersection(set2)
		arr3 = list(set3)
		return len(arr3)


class Solution:

	def countPairs(self, root1, root2, x):
		dic = dict()
		count = [0]

		def store(root1):
			if not root1:
				return
			store(root1.left)
			dic[root1.data] = 1
			store(root1.right)

		def search(root2):
			if not root2:
				return
			search(root2.left)
			if x - root2.data in dic.keys():
				count[0] += 1
			search(root2.right)
		store(root1)
		search(root2)
		return count[0]


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

class Solution:

	def countPairs(self, root1, root2, x):
		l1 = []
		l2 = []
		solve(root1, l1)
		solve(root2, l2)
		count = 0
		i = 0
		j = len(l2) - 1
		while i < len(l1) and j >= 0:
			sum = l1[i] + l2[j]
			if sum == x:
				count += 1
				i += 1
				j -= 1
			elif sum < x:
				i += 1
			else:
				j -= 1
		return count


class Solution:

	def countPairs(self, root1, root2, x):

		def traverse(root1):
			if not root1:
				return
			traverse(root1.left)
			if root1.data in self.dict:
				self.dict[root1.data] += 1
			else:
				self.dict[root1.data] = 1
			traverse(root1.right)

		def travel(root, x):
			if not root:
				return
			travel(root.left, x)
			if x - root.data in self.dict:
				self.count += self.dict[x - root.data]
			travel(root.right, x)
		self.count = 0
		self.dict = {}
		traverse(root1)
		travel(root2, x)
		return self.count


class Solution:

	def countPairs(self, root1, root2, x):
		map1 = {}
		map2 = {}

		def inorder(root1, map1):
			if root1 == None:
				return
			inorder(root1.left, map1)
			map1[root1.data] = 1
			inorder(root1.right, map1)
		inorder(root1, map1)
		inorder(root2, map2)
		count = 0
		for i in map1:
			if x - i in map2:
				count += 1
		return count


def storeVals(root, mp):
	if root is None:
		return
	mp[root.data] = 1
	storeVals(root.left, mp)
	storeVals(root.right, mp)

def countSumX(root, x, mp, c=[0]):
	if root is None:
		return
	if x - root.data in mp:
		c[0] += 1
	countSumX(root.left, x, mp, c)
	countSumX(root.right, x, mp, c)

class Solution:

	def countPairs(self, root1, root2, x):
		st1 = []
		st2 = []
		res = []
		while (len(st1) or root1) and (len(st2) or root2):
			while root1:
				st1.append(root1)
				root1 = root1.left
			while root2:
				st2.append(root2)
				root2 = root2.right
			top1 = st1[-1]
			top2 = st2[-1]
			if top1.data + top2.data == x:
				res.append([top1.data, top2.data])
				st1.pop()
				st2.pop()
				if top1.right:
					root1 = top1.right
				if top2.left:
					root2 = top2.left
			elif top1.data + top2.data > x:
				st2.pop()
				if top2.left:
					root2 = top2.left
			else:
				st1.pop()
				if top1.right:
					root1 = top1.right
		return len(res)


def storeVals(root, mp):
	if root is None:
		return
	mp[root.data] = 1
	storeVals(root.left, mp)
	storeVals(root.right, mp)

def countSumX(root, x, mp, c=[0]):
	if root is None:
		return
	if x - root.data in mp:
		c[0] += 1
	countSumX(root.left, x, mp, c)
	countSumX(root.right, x, mp, c)

class Solution:

	def countPairs(self, root1, root2, x):
		mp = {}
		count = [0]
		storeVals(root1, mp)
		countSumX(root2, x, mp, count)
		return count[0]


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

class Solution:

	def countPairs(self, root1, root2, x):
		lst1 = inorder(root1)
		lst2 = inorder(root2)
		count = 0
		i = 0
		j = len(lst2) - 1
		while i < len(lst1) and j >= 0:
			if lst1[i] + lst2[j] == x:
				count += 1
				j -= 1
			elif lst1[i] + lst2[j] < x:
				i += 1
			else:
				j -= 1
		return count


class Solution:

	def countPairs(self, root1, root2, x):
		arr1 = []
		arr2 = []

		def inorder1(root1):
			if root1 == None:
				return
			inorder1(root1.left)
			arr1.append(root1.data)
			inorder1(root1.right)
		inorder1(root1)

		def inorder2(root2):
			if root2 == None:
				return
			inorder2(root2.left)
			arr2.append(root2.data)
			inorder2(root2.right)
		inorder2(root2)
		i = 0
		j = len(arr2) - 1
		count = 0
		while i < len(arr1) and j >= 0:
			if arr1[i] + arr2[j] == x:
				count += 1
				j -= 1
			elif arr1[i] + arr2[j] < x:
				i += 1
			else:
				j -= 1
		return count


class Solution:

	def countPairs(self, root1, root2, x):
		global setx, ans
		setx = set()
		ans = 0
		finda(root1)
		solve(root2, x)
		return ans

def finda(root):
	global setx
	if not root:
		return
	setx.add(root.data)
	finda(root.left)
	finda(root.right)

def solve(root, x):
	global ans, setx
	if not root:
		return
	if x - root.data in setx:
		ans += 1
	solve(root.left, x)
	solve(root.right, x)


class Solution:

	def ino(self, r, s):
		if r is None:
			return
		self.ino(r.left, s)
		s[r.data] = 1
		self.ino(r.right, s)

	def ino1(self, r, s, x, l):
		if r is None:
			return
		self.ino1(r.left, s, x, l)
		if x - r.data in s:
			l[0] += 1
		self.ino1(r.right, s, x, l)

	def countPairs(self, root1, root2, x):
		s = {}
		self.ino(root1, s)
		l = [0]
		self.ino1(root2, s, x, l)
		return l[0]


class Solution:

	def countPairs(self, root1, root2, x):
		bst1 = []
		bst2 = []
		ans = 0

		def inorderbst(node, flag):
			nonlocal bst1, bst2
			if node is None:
				return node
			inorderbst(node.left, flag)
			if flag == 1:
				bst1.append(node.data)
			if flag == 2:
				bst2.append(node.data)
			inorderbst(node.right, flag)
		inorderbst(root1, 1)
		inorderbst(root2, 2)
		s = set(bst2)
		for i in range(len(bst1)):
			if x - bst1[i] in s:
				ans += 1
		return ans


class Solution:

	def countPairs(self, root1, root2, x):
		q1 = []
		q2 = []
		c = 0
		self.inor(root1, q1)
		self.inor(root2, q2)
		i = 0
		j = len(q2) - 1
		while i < len(q1) and j >= 0:
			if q1[i] + q2[j] == x:
				c += 1
				i += 1
				j -= 1
			elif q1[i] + q2[j] < x:
				i += 1
			else:
				j -= 1
		return c

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


class Solution:

	def countPairs(self, root1, root2, x):
		(stack1, stack2) = ([], [])
		count = 0
		while 1:
			while root1:
				stack1.append(root1)
				root1 = root1.left
			while root2:
				stack2.append(root2)
				root2 = root2.right
			if not stack1 or not stack2:
				break
			(f1, f2) = (stack1[-1], stack2[-1])
			summ = f1.data + f2.data
			if summ == x:
				count += 1
				root1 = f1.right
				root2 = f2.left
				stack1.pop()
				stack2.pop()
			elif summ > x:
				root2 = f2.left
				stack2.pop()
			else:
				root1 = f1.right
				stack1.pop()
		return count