135. Find a Pair With a Given Sum in a BST

Given a binary search tree and a target sum, print 'Yes' if two distinct nodes exist whose values add up to the target, otherwise print 'No'. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N). The target is given on the next line.

Input: First line contains space-separated level-order tokens describing the BST ('N' marks an absent child). Second line contains the target sum. Output: Print 'Yes' if two distinct nodes sum to the target, otherwise print 'No'.

1 <= number of nodes <= 10^5

The problem explicitly requires two DISTINCT nodes - a value that happens to equal exactly half the target should not be paired with itself unless it genuinely appears twice in the tree.

Check whether two distinct nodes in a BST have values that add up to a given target. Brute force: Check every possible pair of nodes directly - this costs O(n²), unnecessary given the BST's inherent sorted structure once traversed. Optimised: Converting the BST into its sorted inorder sequence turns this into the classic 'pair with given sum in a sorted array' problem, solvable with a simple two-pointer sweep in linear time after the traversal - alternatively, a hash-set approach works in a single pass without even needing the values sorted first.

Traverse the BST with any traversal order (e.g. in-order) to collect all node values into an array. Then use two nested loops to check every distinct pair of values in that array, printing 'Yes' as soon as a pair sums exactly to the target and 'No' if no such pair is found after checking them all. This ignores the BST's ordering property entirely once the values are extracted, treating it as a plain array two-sum problem solved the slow way. Time: O(n^2) Space: O(n)

Perform an in-order traversal of the BST, which yields all values already in fully sorted order into an array (a property specific to BSTs). Then apply the standard two-pointer technique on this sorted array: one pointer starts at the beginning, another at the end; if their sum equals the target, print 'Yes'; if the sum is too small, advance the left pointer; if too large, retreat the right pointer; if the pointers cross without a match, print 'No'. This exploits the BST's ordering to avoid the brute approach's nested comparison, needing only one traversal and one linear scan. Time: O(n) Space: O(n)

Instead of building a full sorted array first, maintain two lazy BST iterators directly over the tree: one performs an in-order walk using an explicit stack to produce the next-smallest unvisited value on demand, and the other performs a reverse in-order walk with its own stack to produce the next-largest unvisited value on demand. Advance the 'smallest' iterator when the current sum is too small and the 'largest' iterator when it's too large, exactly mirroring the two-pointer logic, stopping as soon as a match is found or the two iterators meet. Because each stack only ever needs to hold nodes along a root-to-current path, this needs space proportional to the tree's height rather than a full copy of all n values. Time: O(n) worst case, often less Space: O(h) (h = tree height)

1. Perform an inorder traversal to get all values in sorted (ascending) order. 2. Use two pointers, one starting from the smallest value, one from the largest, moving them toward each other based on whether the current sum is too small or too big. 3. Alternatively, walk the tree once and use a hash set: for each value, check if (target - value) has already been seen.

Time: O(n) - one traversal to gather values (or check via hash set), plus a linear two-pointer sweep if using that approach. Space: O(n), for storing the traversed values (or the hash set).

Test with a single-node tree (no pair is possible, expect 'No'), a target only reachable via the tree's minimum and maximum values, and a tree with 10^5 nodes for performance.

Be ready to present both approaches (two-pointer on sorted inorder values, or a single-pass hash set) and discuss their tradeoffs - the hash-set approach avoids needing the values sorted at all, at the cost of similar extra space.