433. Count Pairs From Two BSTs Whose Sum Equals a Given Value

Given two binary search trees and a target value X, count how many pairs (one node from each tree) have values summing to exactly X, and print that count. Each tree is given as its own line of level-order tokens, followed by X on a third line.

Input: First line contains space-separated level-order tokens for the first BST. Second line contains space-separated level-order tokens for the second BST. Third line contains the target value X. Output: Print a single integer - the count of node pairs (one from each tree) summing to X.

1 <= number of nodes in each tree <= 10^5

Each pair is counted exactly ONCE naturally, since you're checking one tree's values against the OTHER tree's hash set in a single direction - no risk of double-counting a pair from both directions.

Given two separate BSTs and a target X, count how many pairs (one node from each tree) add up to exactly X. Brute force: Check every possible pair (one node from each tree) directly - this costs O(n1 * n2), too slow for large trees. Optimised: Putting one tree's values into a hash set lets every check against the other tree's values become an O(1) lookup - a single pass over the second tree's values (via any traversal) then finds all matching pairs in O(n1 + n2) total, with no nested comparison needed.

Traverse the first BST fully collecting all its node values (any traversal order works), then for every value from the first tree, traverse the entire second BST checking whether (X - value) exists as a node value, counting all matches. This checks every possible pair by brute force and is trivially correct, but it repeats a full traversal of tree 2 for every single node of tree 1. Time: O(n * m) Space: O(n) for storing tree 1's values (or O(1) if re-traversing tree 1 each time)

Traverse the first tree once, inserting every value into a hash set. Then traverse the second tree once; for each node's value v, check whether (X - v) is present in the hash set and increment the count if so. Since hash set membership checks are O(1) on average, this turns the nested O(n*m) brute-force scan into two single linear passes, one over each tree. Time: O(n + m) average Space: O(n)

Exploit that inorder traversal of a BST yields values in sorted order: create two iterative in-order 'cursors' using explicit stacks, one walking tree 1 in ascending order and one walking tree 2 in descending order (i.e., a reverse-inorder). Advance the ascending cursor if the current pair's sum is less than X, the descending cursor if it's greater, and count a match (advancing both) when it equals X - exactly the classic sorted two-pointer technique, but generating the 'array' values lazily from each tree instead of storing them. This keeps the same O(n+m) time as the hashing approach while dropping auxiliary space from a full hash set down to just the O(height) stack space each iterator needs. Time: O(n + m) Space: O(h1 + h2)

1. Get the sorted (inorder) values of each BST separately. 2. Put one tree's values into a hash set. 3. For every value v in the OTHER tree, check whether (X - v) exists in that hash set - each such match is one valid pair.

Time: O(n1 + n2) - one traversal per tree, with O(1) hash lookups. Space: O(n1) or O(n2) (whichever tree's values are placed in the hash set).

Test with no valid pair existing (answer 0), a target achievable via multiple distinct pairs, and both trees at the maximum size of 10^5 nodes for performance.

Be ready to mention the alternative two-pointer approach (get both trees' sorted inorder values, then use two pointers - one from the smallest of tree 1, one from the largest of tree 2) as a way to solve this with O(n1+n2) time but without needing extra hash-set space, at the cost of needing both full sorted lists.