Community Problem
Two Sum IV - Input is a BST
Difficulty: Easy
Decide whether two distinct BST nodes sum to a target, ideally in O(n) time and O(h) extra space.
Two Sum IV - Input is a BST
Decide whether two distinct BST nodes sum to a target, ideally in O(n) time and O(h) extra space.
By @owentoure
February 28, 2026
·
Updated May 20, 2026
418 views
9
Rate
I had a candidate freeze on this one because they pattern-matched to Two Sum on an array and reached for a hash set, ignoring the BST structure entirely. That works (it is the canonical answer most people give), but the follow-up question is the actual interview signal: can you solve it in O(h) extra space using ordered traversal and the two-pointers idea? That second solution is what the practice catalog skipped, so it is what this entry is really about.
Two Sum IV - Input is a BST
Given the root of a binary search tree and a target integer k, return true if there exist two distinct nodes in the BST whose values sum to k, and false otherwise.
Examples
Example 1:
- Input:
root = [5, 3, 6, 2, 4, null, 7],k = 9 - Output:
true - Explanation: Nodes
2and7sum to9.
Example 2:
- Input:
root = [5, 3, 6, 2, 4, null, 7],k = 28 - Output:
false - Explanation: No two values in the tree sum to
28.
Example 3:
- Input:
root = [2, 1, 3],k = 4 - Output:
true - Explanation: Nodes
1and3sum to4.
Example 4:
- Input:
root = [1],k = 2 - Output:
false - Explanation: A single node cannot pair with itself; the problem requires two distinct nodes.
Constraints
- The number of nodes in the tree is in the range
[1, 10^4]. -10^4 <= Node.val <= 10^4.- The tree is guaranteed to be a valid BST.
-10^5 <= k <= 10^5.
Follow-up
The hash-set solution is O(n) time and O(n) space. Can you keep O(n) time but cut space to O(h)? Hint: in-order traversal of a BST yields a sorted sequence, and Two Sum on a sorted sequence has a two-pointer answer.
Solution
Hints
Solution Walkthrough
Approach: In-Order Traversal Plus Two Pointers (O(n) time, O(n) space)
The two natural answers are:
- Hash set: traverse, for each node check whether
k - node.valis already in a set; otherwise insertnode.val. O(n) time, O(n) space, ignores the BST. - Sorted in-order + two pointers: leverage the BST. In-order traversal yields a sorted sequence. Two Sum on a sorted sequence is two pointers from both ends. Same O(n) / O(n), but it teaches the BST-as-sorted-sequence pattern.
We show solution 2 because it is the answer to the interview's follow-up.
Algorithm
- Iterative in-order traversal: push left children until null, pop, record value, descend right.
- After traversal,
sortedis the values in ascending order. - Two pointers
i = 0,j = sorted.length - 1. Whilei < j:sum = sorted[i] + sorted[j].- If
sum == k, returntrue. - If
sum < k, advancei(need a larger value). - If
sum > k, retreatj(need a smaller value).
- Return
falseif the pointers cross.
Why It Works
In-order traversal of a BST emits values in non-decreasing order; this is the defining property of BSTs. On a sorted array, the two-pointer scan is correct because at each step, the smallest possible sum is sorted[i] + sorted[j] if we keep both ends; advancing i is the only way to grow the sum, retreating j is the only way to shrink it. Distinctness is enforced by the strict i < j condition.
Complexity
Sample BST
5
/ \
3 6
/ \ \
2 4 7
In-order: [2, 3, 4, 5, 6, 7]Metric Value
Time O(n) traversal + O(n) two-pointer scan = O(n)
Space O(n) for the sorted buffer + O(h) for the in-order stackPitfalls
- Allowing the same node twice. If
k = 2 * node.val, the answer istrueonly when there are TWO different nodes with that value. Thei < jstrictness in the two-pointer scan handles this for distinct slots, and the BST invariant in this problem says values are typically distinct anyway. - Forgetting the BST link. A pre-order or post-order traversal also collects all values, but the resulting sequence is NOT sorted, so the two-pointer scan would be wrong. Only in-order yields the sorted sequence.
- Iterative vs recursive in-order. Both work. The iterative version uses an explicit stack; the recursive version uses the call stack. Either is O(h) extra space for the traversal control flow.
Solution Code