Count pairs from two BSTs whose sum equals X

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}