On this page
Description
The question is whether a BST has two values that add up to a target. On an unsorted array the usual answer is a hash set, which needs O(n) extra space. A BST already keeps its values in order, though, and sorted order allows the two-pointer sweep: start at the smallest and largest values and move inward. This skill covers the sweep over an inorder list and then the version that keeps only two small stacks, one walking up from the smallest value and one walking down from the largest.
We'll go from simple to more technical:
- The pattern: the inorder list and a two-pointer sweep.
- A second flavor: two lazy iterators instead of the list.
- Where it runs in production (matching across two sorted indexes).
- What breaks it: a node pairing with itself, and paying for a full copy.
The approach
Java
boolean findTarget(TreeNode root, int target) {
List<Integer> inorder = new ArrayList<>();
traverse(root, inorder); // inorder = values in ascending order
int left = 0, right = inorder.size() - 1;
while (left < right) {
int sum = inorder.get(left) + inorder.get(right);
if (sum == target) return true;
if (sum < target) left++; // everything left of `left` is smaller still - useless
else right--; // everything right of `right` is larger still - useless
}
return false;
}
Python
def find_target(root: TreeNode, target: int) -> bool:
inorder = []
traverse(root, inorder) # inorder = values in ascending order
left, right = 0, len(inorder) - 1
while left < right:
total = inorder[left] + inorder[right]
if total == target:
return True
if total < target:
left += 1 # everything left of `left` is smaller still - useless
else:
right -= 1 # everything right of `right` is larger still - useless
return False
When the sum is too small, the smallest value can't be part of any answer: its best possible partner is already the largest remaining value, and that wasn't enough. So left moves up. The mirror argument moves right down. Each step discards one value for good, so the sweep is O(n). The strict left < right stops a single node from pairing with itself.
A second flavor: two iterators instead of a list
The list costs O(n) extra space - no better than the hash set. The sweep only ever looks at the smallest and largest remaining values, so two lazy iterators can supply them without building the list: an ascending iterator (a stack of the left spine) and a descending one (a stack of the right spine), each holding O(h) nodes.
Java
Deque<TreeNode> asc = new ArrayDeque<>(), desc = new ArrayDeque<>();
pushLeft(asc, root); // smallest on top
pushRight(desc, root); // largest on top
while (!asc.isEmpty() && !desc.isEmpty() && asc.peek() != desc.peek()) {
int sum = asc.peek().val + desc.peek().val;
if (sum == target) return true;
if (sum < target) pushLeft(asc, asc.pop().right); // advance the ascending side
else pushRight(desc, desc.pop().left); // advance the descending side
}
return false;
Python
def find_target(root: TreeNode, target: int) -> bool:
asc, desc = [], []
push_left(asc, root) # smallest on top
push_right(desc, root) # largest on top
while asc and desc and asc[-1] is not desc[-1]:
total = asc[-1].val + desc[-1].val
if total == target:
return True
if total < target:
push_left(asc, asc.pop().right) # advance the ascending side
else:
push_right(desc, desc.pop().left) # advance the descending side
return False
The two iterators meeting at the same node plays the role of left < right. It's the same O(n) time with O(h) space, and it works across two different BSTs too - ascending on one and descending on the other counts pairs with one value from each.
Where you'll see it
Matching across two ordered sets - a buy order and a sell order whose prices sum to a budget, two sorted indexes joined on a sum or difference - is the two-iterator sweep: walk one index forward and the other backward, never materializing either. It's a merge join over two sorted inputs, with one side walked backward because the match condition is a sum rather than equality.
Which tool for which job?
| You need | Use |
|---|---|
| A pair summing to a target, simplest code | the inorder list plus a two-pointer sweep |
| The same in O(h) space | two iterators: ascending and descending stacks |
| Pairs across two BSTs | ascending on one, descending on the other |
| Order doesn't matter, any input | a hash set of values seen so far |
| Sums that can pass 2^31 in Java | compare in long |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
left <= right | a node pairs with itself (one 5, target 10 returns true) | left < right, or stop when the iterators meet |
| Thinking the list saves space over a hash set | both are O(n) | two iterators, O(h) |
Searching for target - v from every node | O(n * h), up to O(n^2) | the sweep, O(n) |
An int sum of two large values | the sum wraps and the sweep moves the wrong pointer | add in long |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. The sum of the smallest and largest remaining values is below the target. Why is it safe to drop the smallest value for good?
Show answer
Its best possible partner is the largest remaining value - and even that sum falls short. Every other partner is smaller, so no pair involving the smallest value can reach the target. Dropping it never loses an answer.
2. Is extracting the inorder list more space-efficient than a hash set?
Show answer
No - both hold every value, O(n). The list's advantage is only that it's sorted, which allows the two-pointer sweep. To actually save space, replace the list with two iterators (ascending and descending), each an O(h) stack.
3. How would you count pairs with one value from BST A and one from BST B that sum to x?
Show answer
Run an ascending iterator over A and a descending iterator over B. If the sum is too small, advance A's iterator; if too large, advance B's; on a match, count it and advance both (values are distinct within each tree). O(n + m) time, O(h_A + h_B) space.
Key takeaways
- Two pointers need sorted order; a BST's inorder provides it, so pair-sum questions reduce to the sorted-array sweep.
- Each step drops one value for good: the smallest when the sum is too small, the largest when it's too big.
left < right(or "the iterators haven't met") keeps a node from pairing with itself.- The extracted list is O(n) space, the same as a hash set; two iterators get it to O(h).
- Ascending on one tree and descending on another counts cross-tree pairs the same way.