Count pairs from two BSTs whose sum equals X
Problem
Count pairs (a from the first BST, b from the second) with a + b = x.
Example 1
Input: BST1 = {1, 3, 5, 6, 7, 8, 10}, BST2 = {2, 3, 4, 5, 6, 8, 9, 11}, x = 16
Output: 4(5, 11), (7, 9), (8, 8) and (10, 6).
Also asked as: Count pairs from 2 BST whose sum is equal to given value "X"
Test cases
Case 1
Input: [5,3,7,2,4,6,8], [10,6,15,3,8,11,18], 16 Expected: 3
Case 2
Input: [6,3,8,1,5,7,10], [5,3,8,2,4,6,9,null,null,null,null,null,null,null,11], 16 Expected: 4
Case 3
Input: [1], [2], 3 Expected: 1
Case 4
Input: [1], [2], 5 Expected: 0
View solutionHide solution1 approach
1. In-order of one, reverse in-order of the other, two pointers
Time O(n + m)Space O(h1 + h2)
Ascending stream from BST1, descending stream from BST2. Advance the streams like the two-pointer pair-sum on sorted arrays.
function countPairs(root1, root2, x) { const asc = [], desc = []; (function inL(n){ if(!n) return; inL(n.left); asc.push(n.val); inL(n.right); })(root1); (function inR(n){ if(!n) return; inR(n.right); desc.push(n.val); inR(n.left); })(root2); let i = 0, j = 0, count = 0; while (i < asc.length && j < desc.length) { const s = asc[i] + desc[j]; if (s === x) { count++; i++; j++; } else if (s < x) i++; else j++; } return count;}