Two Sum IV - Input is a BST
Last Updated: April 2, 2026
Understanding the Problem
This is the classic 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.
The interesting thing here is that we have two angles to work with. First, this is a "find two numbers that sum to a target" problem, which we know how to solve with a hash set. Second, the input is a BST, which means the values are sorted if we do an inorder traversal. That sorted property opens the door to a two-pointer approach.
The key question is: do we treat this as a generic tree problem (ignoring the BST property) and use a hash set, or do we exploit the BST's sorted order for a two-pointer solution? Both work, and each teaches something different.
Key Constraints:
Number of nodes in [1, 10^4]-- With up to 10,000 nodes, O(n) and O(n log n) solutions are both fine. Even O(n^2) would pass, though it is unnecessary.Node values in [-10^4, 10^4]-- Values can be negative. The targetkcan also be negative. Our solution needs to handle negative complements.At least 1 node-- We do not need to handle an empty tree, but a single-node tree should return false since we need two distinct nodes.
Approach 1: DFS with Hash Set
Intuition
Let's start with the simplest idea. Forget that the input is a BST for a moment. Treat it as a regular tree and apply the same logic we would use for the original Two Sum problem on an array.
For each node we visit, we compute its complement: k - node.val. If that complement is already in a set of values we have seen so far, we found our pair. If not, we add the current node's value to the set and keep traversing.
This is a direct application of the hash set technique. The tree traversal (DFS or BFS, either works) replaces the array iteration from the original Two Sum. The hash set does the heavy lifting of O(1) 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 can be up to O(h) where h is the height of the tree, but the hash set dominates, giving us O(n) overall.
This solution is already O(n) in time, but we completely ignored the BST property. The BST gives us something valuable: an inorder traversal produces a sorted sequence. Can we exploit that sorted order to use a two-pointer approach instead?
Approach 2: Inorder Traversal + Two Pointers
Intuition
Here is where the BST property becomes useful. If we do an inorder traversal of a BST, we get all the values in sorted order. And finding two numbers in a sorted array that sum to a target is a classic two-pointer problem (Two Sum II).
So the plan is straightforward: flatten the BST into a sorted list via inorder traversal, then run two pointers from both ends. If the sum of the two pointed values is too small, move the left pointer right. If too large, move the right pointer left. If equal, we found our pair.
This approach makes the BST connection to sorted arrays explicit. It is a good demonstration of how recognizing the underlying structure of your input can unlock familiar techniques.
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:
a. Compute sum = list[left] + list[right].
b. If sum == k, return true.
c. If sum < k, increment left (we need a larger sum).
d. If sum > k, decrement right (we need a smaller sum).
- If the pointers meet without finding a pair, return false.
Example Walkthrough
Code
The two-pointer technique works on sorted arrays because of a simple invariant. If the sum of the smallest remaining element and the largest remaining element is less than the target, the smallest element cannot be part of any valid pair (even pairing it with the largest is not enough), so we discard it by moving left forward. Symmetrically, if the sum is too large, the largest element is too big for any remaining pair, so we discard it by moving right backward. This guarantees we never skip a valid pair.
- 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), but the list dominates.
Both approaches so far use O(n) extra space. Is there a way to do the two-pointer scan without materializing the entire sorted list? If we could walk the BST from both ends simultaneously, we could run the two-pointer logic directly on the tree.
Approach 3: BST Iterator Two Pointers
Intuition
This approach takes the two-pointer idea from Approach 2 and applies it directly on the BST, without first collecting all values into a list. The trick is to use two iterators: one that produces values in ascending order (normal inorder: left, root, right) and another that produces values in descending order (reverse inorder: right, root, left).
Think of it like having two fingers on the tree. One finger starts at the leftmost node (the smallest value) and moves right. The other starts at the rightmost node (the largest value) and moves left. At each step, we compare their sum to k and decide which finger to advance, exactly like the two-pointer technique on a sorted array.
We implement each iterator using an explicit stack. The forward iterator pushes all left children to get to the minimum, then steps to the right subtree. The reverse iterator does the mirror: pushes all right children to get to the maximum, then steps to 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:
a. Compute sum = leftVal + rightVal.
b. If sum == k, return true.
c. 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.
d. 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
This is conceptually identical to Approach 2, but instead of materializing the entire sorted list, we lazily produce values on demand. The forward stack always has the next smallest value ready to pop, and the reverse stack always has the next largest value ready. We only explore as much of the tree as needed. The termination condition leftNode != rightNode works because in a BST, the forward and reverse iterators will eventually converge on the same node. When they point to the same node, we have exhausted all possible pairs without finding 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 O(h) nodes at a time. For a balanced BST, this is O(log n). For a skewed tree, this is O(n). Crucially, we do not store the entire sorted list, so this is better than Approach 2 when the tree is balanced.