Log inSign up
easyLeetCodeNot Started

Two Sum IV - Input is a BST

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -104 <= Node.val <= 104
  • root is guaranteed to be a valid binary search tree.
  • -105 <= k <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Connect array Two-Pointer technique with BST traversals.
  • Design dual iterators (forward and reverse) for simultaneous two-pointer tree navigation.
  • Achieve O(H) space complexity.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Two Sum on Binary Search Tree.
  • Find pair with sum k.
  • Two pointer simulation on tree.

Algorithmic Decision Tree:

  • If O(N) space permitted -> Hash set or inorder array.
  • If O(H) space requested -> Dual BST iterators.

Connected Patterns:

Binary Search Tree IteratorTwo SumTwo Sum II - Input Array Is Sorted

1. BST Binary Search for Complement (O(N * H))

Intuition

Traverse every node in the tree using DFS. For each visited node curr, execute a binary search in the BST starting from root to look for a node with value k - curr.val. Ensure the found node is not curr itself. Takes O(N * H) time and O(H) recursion stack space.

When to apply: Baseline comparison without auxiliary arrays or sets.

Algorithm

  1. For each node curr, search the BST for k - curr.val starting from root.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11 bool search(TreeNode* root, TreeNode* curr, int val) {
12 TreeNode* p = root;
13 while (p) {
14 if (p->val == val && p != curr) return true;
15 if (val < p->val) p = p->left;
16 else p = p->right;
17 }
18 return false;
19 }
20
21 bool dfs(TreeNode* root, TreeNode* curr, int k) {
22 if (!curr) return false;
23 if (search(root, curr, k - curr->val)) return true;
24 return dfs(root, curr->left, k) || dfs(root, curr->right, k);
25 }
26public:
27 bool findTarget(TreeNode* root, int k) {
28 return dfs(root, root, k);
29 }
30};
31
32int main() {
33 TreeNode* root = new TreeNode(5);
34 root->left = new TreeNode(3);
35 root->right = new TreeNode(6);
36 root->left->left = new TreeNode(2);
37 root->left->right = new TreeNode(4);
38 root->right->right = new TreeNode(7);
39
40 Solution sol;
41 std::cout << "Target 9: " << (sol.findTarget(root, 9) ? "true" : "false") << std::endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N * H)
  • Space complexity: O(H) recursion stack space

2. Hash Set DFS / Inorder Array Two Pointers

Intuition

Traverse tree with DFS while maintaining a hash set seen. For each node, if seen.has(k - curr.val) return true. Otherwise add curr.val to seen. Runs in O(N) time and O(N) space.

When to apply: Standard approach when O(N) memory is acceptable.

Algorithm

  1. Traverse tree with a Hash Set of seen numbers, checking if k - curr.val exists.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_set>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 bool dfs(TreeNode* root, int k, std::unordered_set<int>& seen) {
13 if (!root) return false;
14 if (seen.count(k - root->val)) return true;
15 seen.insert(root->val);
16 return dfs(root->left, k, seen) || dfs(root->right, k, seen);
17 }
18public:
19 bool findTarget(TreeNode* root, int k) {
20 std::unordered_set<int> seen;
21 return dfs(root, k, seen);
22 }
23};
24
25int main() {
26 TreeNode* root = new TreeNode(5);
27 root->left = new TreeNode(3);
28 root->right = new TreeNode(6);
29 root->left->left = new TreeNode(2);
30 root->left->right = new TreeNode(4);
31 root->right->right = new TreeNode(7);
32
33 Solution sol;
34 std::cout << "Target 9: " << (sol.findTarget(root, 9) ? "true" : "false") << std::endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N) for hash set

3. Dual BST Iterators (O(H) Auxiliary Space)

Intuition

1. Create two stacks: s1 for forward inorder (next smallest) and s2 for reverse inorder (next largest). 2. Initialize s1 by pushing left spine, and s2 by pushing right spine. 3. Loop while s1.top() != s2.top(): - Let v1 = s1.top().val and v2 = s2.top().val. - If v1 + v2 == k, return true. - If v1 + v2 < k, pop s1 and advance s1 to the next smaller element (push right child's left spine). - If v1 + v2 > k, pop s2 and advance s2 to the next larger element (push left child's right spine). 4. Return false if pointers meet. Achieves O(N) runtime and strictly O(H) auxiliary space.

When to apply: Optimal in both time and auxiliary space. Ideal when O(H) space is mandated.

Algorithm

  1. Use two BST iterators (one forward, one reverse) to simulate the two-pointer technique directly on the tree.

Dual BST Iterator Two-Sum Trace

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
l = 2, r = 7
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
leftIt.next() yields 2; rightIt.next() yields 7
Decision / next transition
1
Why this step matters

l = 2, r = 7. Sum = 2 + 7 = 9.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class BSTIterator {
12 std::stack<TreeNode*> st;
13 bool forward; // true for ascending, false for descending
14
15 void pushAll(TreeNode* node) {
16 while (node) {
17 st.push(node);
18 node = forward ? node->left : node->right;
19 }
20 }
21public:
22 BSTIterator(TreeNode* root, bool isForward) : forward(isForward) {
23 pushAll(root);
24 }
25
26 bool hasNext() {
27 return !st.empty();
28 }
29
30 int next() {
31 TreeNode* top = st.top();
32 st.pop();
33 if (forward) pushAll(top->right);
34 else pushAll(top->left);
35 return top->val;
36 }
37};
38
39class Solution {
40public:
41 bool findTarget(TreeNode* root, int k) {
42 if (!root) return false;
43
44 BSTIterator leftIt(root, true);
45 BSTIterator rightIt(root, false);
46
47 int l = leftIt.next();
48 int r = rightIt.next();
49
50 while (l < r) {
51 int sum = l + r;
52 if (sum == k) return true;
53 if (sum < k) {
54 if (leftIt.hasNext()) l = leftIt.next();
55 else break;
56 } else {
57 if (rightIt.hasNext()) r = rightIt.next();
58 else break;
59 }
60 }
61 return false;
62 }
63};
64
65int main() {
66 TreeNode* root = new TreeNode(5);
67 root->left = new TreeNode(3);
68 root->right = new TreeNode(6);
69 root->left->left = new TreeNode(2);
70 root->left->right = new TreeNode(4);
71 root->right->right = new TreeNode(7);
72
73 Solution sol;
74 std::cout << "Target 9: " << (sol.findTarget(root, 9) ? "true" : "false") << std::endl;
75 return 0;
76}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(H) auxiliary space for two iterator stacks

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.BST Binary Search for Complement (O(N * H))O(N * H)O(H) recursion stack spaceFor each node curr, search the BST for k - curr.val starting from root.O(N * H)
2.Hash Set DFS / Inorder Array Two PointersO(N)O(N) for hash setTraverse tree with a Hash Set of seen numbers, checking if k - curr.val exists.O(N)
3.Dual BST Iterators (O(H) Auxiliary Space)OptimalO(N)O(H) auxiliary space for two iterator stacksUse two BST iterators (one forward, one reverse) to simulate the two-pointer technique directly on the tree.O(N)

Common Pitfalls & Crucial Edge Cases

Using the same node twice

Inserting into set before checking complement allows k - val == val to self-match.

Array two-pointer when O(H) space is required

Forgetting the dual iterator technique.

Stack underflow on iterator

Missing hasNext() check.

Crucial Edge Cases to Validate:

  • Pair exists at root + leaf — Successfully matches.
  • Target k is sum of single element doubled (e.g. k = 10, node 5 exists once) — Correctly returns false (cannot reuse same node).
  • Tree with 2 nodes — Returns true if sum matches, false otherwise.
  • Negative node values — Handled seamlessly by sum comparison.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the Hash Set solution first (quick, O(N) time and space).
  2. Then offer the Dual BST Iterators approach to demonstrate advanced mastery of O(H) space optimization.
  3. Explain how the two iterators map to left and right pointers in sorted array Two Sum.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How do Dual BST Iterators achieve O(H) auxiliary space instead of O(N)?

2.Why does the forward iterator push node.right's left spine after popping?

3.Can root.val * 2 == k count as a valid pair if only one such node exists in the BST?

Back to DSA Sheet