Two Sum IV - Input is a BST
Understanding the Problem
This is the Two Sum problem, but the input is a BST instead of an array. We need to find whether any two distinct nodes in the tree have values that add up to k.
There are two angles to work with. This is a "find two numbers that sum to a target" problem, which a hash set solves directly. It is also a BST, so an inorder traversal produces the values in sorted order, and finding a pair that sums to a target in a sorted sequence is a two-pointer problem.
So we can either treat this as a generic tree problem and use a hash set, or exploit the BST's sorted order with two pointers. Both run in O(n) time and differ in their space use.
Key Constraints:
Node values in [-10^4, 10^4], k in [-10^5, 10^5]-- Values and the target can be negative, so the complementk - node.valcan be negative. Any solution must handle negative values, but the magnitudes are small enough that a 32-bitintholds every value and every pairwise sum without overflow.Number of nodes in [1, 10^4]-- A single-node tree must return false, since a valid answer needs two distinct nodes. There is no empty-tree case to handle.
Approach 1: DFS with Hash Set
Intuition
The BST property is not needed for a correct solution. We can treat the input as an ordinary binary tree and apply the same hash-set logic that solves Two Sum on an array.
For each node we visit, we compute its complement k - node.val. If that complement is already in the set of values seen so far, the current node and the earlier one form a valid pair. Otherwise we add the current node's value to the set and continue traversing. The tree traversal (DFS or BFS, either order works) takes the place of the array iteration, and the hash set provides O(1) average lookups.
Algorithm
- Create an empty hash set to store node values we have visited.
- Start a DFS traversal from the root.
- At each node, compute the complement:
complement = k - node.val. - If the complement exists in the set, return true.
- Otherwise, add
node.valto the set. - Recursively check the left and right subtrees. If either returns true, return true.
- If we finish traversing the entire tree without finding a pair, return false.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once. At each node, the hash set lookup and insertion are both O(1) on average. So the total work is O(n).
- Space Complexity: O(n). The hash set stores up to n values. The recursion stack adds O(h), where h is the tree height (O(n) for a skewed tree), but the hash set dominates, so the total is O(n).
This solution runs in O(n) time but ignores the BST property entirely. An inorder traversal of a BST produces a sorted sequence, and a sorted sequence admits a two-pointer search. The next approach uses that.
Approach 2: Inorder Traversal + Two Pointers
Intuition
An inorder traversal of a BST visits nodes in ascending order, so collecting the values during inorder produces a sorted list. Finding two numbers in a sorted list that sum to a target is the two-pointer problem from Two Sum II.
The plan is to flatten the BST into a sorted list with an inorder traversal, then run two pointers from both ends. If the sum of the two values is smaller than k, move the left pointer right to increase it. If it is larger, move the right pointer left to decrease it. If it equals k, the pair is found.
Algorithm
- Perform an inorder traversal of the BST to collect all values into a sorted list.
- Initialize two pointers:
leftat the start of the list,rightat the end. - While
left < right: - Compute
sum = list[left] + list[right]. - If
sum == k, return true. - If
sum < k, incrementleft(we need a larger sum). - If
sum > k, decrementright(we need a smaller sum). - If the pointers meet without finding a pair, return false.
Example Walkthrough
Code
Each pointer move discards an element that cannot belong to any remaining pair. If list[left] + list[right] < k, then list[left] paired with the largest remaining value is already below k, so it is below k with every smaller value too. No valid pair uses list[left], so moving left forward loses nothing. The symmetric argument holds when the sum exceeds k: list[right] is too large for every remaining value, so moving right backward is safe. Since every discarded element provably has no valid partner, the scan never skips a pair that exists.
- Time Complexity: O(n). The inorder traversal visits every node once, taking O(n). The two-pointer scan over the sorted list is also O(n) in the worst case. Total is O(n).
- Space Complexity: O(n). We store all n values in the sorted list. The recursion stack for inorder traversal adds O(h) (O(n) for a skewed tree), but the list dominates.
Both approaches so far use O(n) extra space. The next approach runs the same two-pointer scan directly on the tree, walking it from both ends at once, so it never materializes the full sorted list and uses only O(h) space.
Approach 3: BST Iterator Two Pointers
Intuition
This approach runs the two-pointer idea from Approach 2 directly on the BST, without collecting values into a list. It uses two iterators: one that yields values in ascending order (inorder: left, root, right) and one that yields them in descending order (reverse inorder: right, root, left).
The ascending iterator plays the role of the left pointer, starting at the smallest value and stepping up. The descending iterator plays the right pointer, starting at the largest value and stepping down. At each step we compare their sum to k and advance whichever side the comparison calls for, exactly as the two-pointer scan does on a sorted array.
Each iterator is an explicit stack. The forward iterator pushes a node and all its left descendants, so the top of the stack is the next smallest value; after popping a node, it descends into that node's right subtree and again pushes all left descendants. The reverse iterator mirrors this: push all right descendants to reach the largest value, and after popping descend into the left subtree.
Algorithm
- Initialize a forward stack by pushing all left children starting from the root (this positions us at the smallest value).
- Initialize a reverse stack by pushing all right children starting from the root (this positions us at the largest value).
- Pop the top of each stack to get the current smallest (
leftVal) and largest (rightVal). - While
leftVal < rightVal: - Compute
sum = leftVal + rightVal. - If
sum == k, return true. - If
sum < k, advance the forward iterator: move to the right child of the current node, then push all its left children. Pop the next value. - If
sum > k, advance the reverse iterator: move to the left child of the current node, then push all its right children. Pop the next value. - If the pointers meet or cross, return false.
Example Walkthrough
Code
The two iterators produce the same ascending and descending sequences that Approach 2 reads off the sorted list, one value at a time, so the pointer logic is identical and the same discard argument applies. Termination relies on the two iterators meeting at the same node. The forward iterator walks values upward and the reverse iterator walks them downward through the same set of nodes, so they cross at one node. The check leftNode != rightNode stops the loop at that point, which means every distinct pair has been compared without a match.
- Time Complexity: O(n). In the worst case, both iterators together visit every node once. Each node is pushed onto a stack and popped once, so the total work is O(n).
- Space Complexity: O(h), where h is the height of the tree. Each stack holds at most one node per level along a root-to-leaf path, so O(h) nodes at a time. This is O(log n) for a balanced BST and O(n) for a skewed tree. Because we never store the full sorted list, this uses less space than Approach 2 on a balanced tree.