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 82 / \3 4 124 / \ / \5 2 6 10 14For 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:
- Create both iterators. Let
i = forward.next()(the smallest) andj = reverse.next()(the largest). - 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().
- If
- 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
Each node is pushed and popped at most once per iterator, and the two pointers meet in at most n steps in total.
Each iterator holds one root-to-node path. The array-based solution would use O(n).