On this page

Two Sum IV Input Is a Bst

Given the root of a BST and an integer k, return true if there exist two distinct nodes whose values add up to k, and false otherwise.

Constraints:

  • The number of nodes is in the range [1, 10^4].
  • -10^4 <= Node.val <= 10^4, the tree is a valid BST, and -10^5 <= k <= 10^5.

Intuition

1 8
2 / \
3 4 12
4 / \ / \
5 2 6 10 14

For k = 18 the answer is true (4 + 14). For k = 5 it is false.

The inorder traversal of a BST is a sorted array. On a sorted array, the classic two-pointer technique solves two-sum: one pointer at the smallest value, one at the largest, move the left pointer up if the sum is too small and the right pointer down if it is too big.

The simple way is to dump the inorder traversal into an array first. That costs O(n) extra memory. We can do the same two-pointer walk directly on the tree using two iterators.

Approach: Two BST Iterators

Reuse the idea from the BST Iterator problem, with a flag to run it in reverse:

  • A forward iterator (left spine, then right children) yields values in ascending order.
  • A reverse iterator (right spine, then left children) yields values in descending order.

Steps:

  1. Create both iterators. Let i = forward.next() (the smallest) and j = reverse.next() (the largest).
  2. While i < j:
    • If i + j == k, return true.
    • If i + j < k, advance the small side: i = forward.next().
    • Otherwise advance the large side: j = reverse.next().
  3. If the pointers meet, return false.

The condition i < j guarantees that the next value always exists, and it also makes sure we never pair a node with itself.

Code

class BSTIterator {
stack<TreeNode*> st;
bool reverse;
void pushAll(TreeNode* node) {
while (node != nullptr) {
st.push(node);
node = reverse ? node->right : node->left;
}
}
public:
BSTIterator(TreeNode* root, bool isReverse) : reverse(isReverse) {
pushAll(root);
}
int next() {
TreeNode* node = st.top();
st.pop();
pushAll(reverse ? node->left : node->right);
return node->val;
}
};
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
if (root == nullptr) return false;
BSTIterator forward(root, false);
BSTIterator backward(root, true);
int i = forward.next();
int j = backward.next();
while (i < j) {
if (i + j == k) return true;
if (i + j < k) i = forward.next();
else j = backward.next();
}
return false;
}
};

Complexity

Time: O(n)

Each node is pushed and popped at most once per iterator, and the two pointers meet in at most n steps in total.

Space: O(h)

Each iterator holds one root-to-node path. The array-based solution would use O(n).

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"The inorder traversal of a BST is sorted, and two sum on a sorted array is the classic two-pointer problem. Instead of copying the tree into an array, I use two BST iterators, one that yields values in ascending order and one in descending order using the mirror traversal. I take the smallest and the largest value and loop while the small one is less than the large one. If their sum equals k I return true. If it is too small I advance the ascending iterator, and if it is too big I advance the descending one. The i less than j condition keeps me from pairing a node with itself. Time is O of n and space is O of h, because each iterator only stores a path."
Next TopicRecover Binary Search Tree