Two Sum In BST
HardTwo iterators, walking inwards
Problem
Given a BST and a target, return whether two nodes sum to the target.
Do an in-order walk to get sorted values, then two-pointer inward for a pair that sums to the target.
The idea
Run one in-order iterator forwards and one in reverse, giving the smallest and largest remaining values — exactly the two-pointer setup on a sorted array. Advance the appropriate side depending on whether the sum is short or over.
The trick
- Forward and reverse in-order iterators replace the two array pointers.
- Stop when the two iterators cross.
- O(n) time, O(height) space — better than flattening to a list.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — BST {5,3,6,2,4,null,7}, target=9 Values: 5, 3, 6, 2, 4, 7, 9.
1use two BST iterators: smallest-forward and largest-backward2while lo<hi:3 s=lo.val+hi.val; if s==t: true; if s<t: lo=next; else hi=prevInput
- array
- [5, 3, 6, 2, 4, 7, 9]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- bst = [5,3,6,2,4,null,7], target = 9
- Output:
- true
- Explanation:
- 2 + 7 = 9 exists.
Example 2
- Input:
- bst = [5,3,6,2,4,null,7], target = 28
- Output:
- false
- Explanation:
- No pair sums to 28 → false.
Example 3
- Input:
- bst = [2,1,3], target = 4
- Output:
- true
- Explanation:
- 1 + 3 = 4.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.