Two Sum IV - Input is a BST
Easy · Graphs · Explanation and code example
Opposite BST Iterators
How it works
Inorder traversal of a BST gives sorted values. Use one iterator ascending and another descending, then apply a two-pointer sum search without storing every node. Each iterator keeps only its current root-to-node traversal stack.
Steps
- Initialize ascending and descending iterators.
- Compare their sum with the target.
- Advance the low side for a small sum or the high side for a large sum, stopping when they meet.
Complexity
- Time: O(n) worst case.
- Space: O(h) for the two traversal stacks.
Things to watch for
- Do not reuse the same node for both summands.
- The adapted iterators return node identities, so equal-valued distinct nodes can form a pair.
- A single-node tree cannot form a pair.
Python code example
class BSTIterator:
def __init__(self, root: TreeNode | None, leftToRight: bool):
self.stack = []
self.leftToRight = leftToRight
self._pushUntilNone(root)
def next(self) -> TreeNode:
node = self.stack.pop()
if self.leftToRight:
self._pushUntilNone(node.right)
else:
self._pushUntilNone(node.left)
return node
def _pushUntilNone(self, root: TreeNode | None):
while root:
self.stack.append(root)
root = root.left if self.leftToRight else root.right
class Solution:
def findTarget(self, root: TreeNode | None, k: int) -> bool:
if not root:
return False
left = BSTIterator(root, True)
right = BSTIterator(root, False)
l = left.next()
r = right.next()
while l is not r:
summ = l.val + r.val
if summ == k:
return True
if summ < k:
l = left.next()
else:
r = right.next()
return False
C++ code example
class BSTIterator {
public:
BSTIterator(TreeNode* root, bool leftToRight) : leftToRight(leftToRight) {
pushUntilNull(root);
}
TreeNode* next() {
TreeNode* root = nodes.top();
nodes.pop();
pushUntilNull(leftToRight ? root->right : root->left);
return root;
}
private:
std::stack<TreeNode*> nodes;
bool leftToRight;
void pushUntilNull(TreeNode* root) {
while (root != nullptr) {
nodes.push(root);
root = leftToRight ? root->left : root->right;
}
}
};
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
if (root == nullptr)
return false;
BSTIterator left(root, true);
BSTIterator right(root, false);
for (TreeNode* l = left.next(), *r = right.next(); l != r;) {
const int sum = l->val + r->val;
if (sum == k)
return true;
if (sum < k)
l = left.next();
else
r = right.next();
}
return false;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.