Two Sum IV - Input is a BST
Two Sum IV - Input is a BST is a easy trees & bst problem solved with the miscellaneous bst questions pattern.
The best approach, two bst iterators (o(h) space), runs in O(n) time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from hash set during dfs up.
Problem
Given the root of a BST and an integer k, return whether there are two different nodes whose values add up to k.
Examples
Example 1
- Input
root = [5, 3, 6, 2, 4, null, 7], k = 9- Output
true- Why
- 2 + 7, or 3 + 6, or 4 + 5.
Example 2
- Input
same tree, k = 28- Output
false
Constraints
- The tree has
1to10^4nodes. - The two values must come from different nodes.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Hash set during DFS | O(n) | O(n) |
| Two BST iterators (O(h) space) | O(n) | O(h) |
1Hash set during DFS
O(n)O(n)Traverse the tree; for each value, check whether k - value was already seen.
- DFS; if seen contains k - val return true; add val.
class Solution {
public boolean findTarget(TreeNode root, int k) {
return dfs(root, k, new HashSet<>());
}
private boolean dfs(TreeNode n, int k, Set<Integer> seen) {
if (n == null) return false;
if (seen.contains(k - n.val)) return true;
seen.add(n.val);
return dfs(n.left, k, seen) || dfs(n.right, k, seen);
}
}class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
return self.dfs(root, k, set())
def dfs(self, n: Optional[TreeNode], k: int, seen: Set[int]) -> bool:
if n is None:
return False
if k - n.val in seen:
return True
seen.add(n.val)
return self.dfs(n.left, k, seen) or self.dfs(n.right, k, seen)class Solution {
public:
bool findTarget(TreeNode* root, int k) {
unordered_set<int> seen;
return dfs(root, k, seen);
}
private:
bool dfs(TreeNode* n, int k, unordered_set<int>& seen) {
if (n == nullptr) return false;
if (seen.count(k - n->val)) return true;
seen.insert(n->val);
return dfs(n->left, k, seen) || dfs(n->right, k, seen);
}
};function findTarget(root, k) {
return dfs(root, k, new Set());
}
function dfs(n, k, seen) {
if (n === null) return false;
if (seen.has(k - n.val)) return true;
seen.add(n.val);
return dfs(n.left, k, seen) || dfs(n.right, k, seen);
}2Two BST iterators (O(h) space)
O(n)O(h)Run two iterative inorder traversals at once: one ascending from the smallest value and one descending from the largest. They act as the left and right pointers of Two Sum II without building a list.
- Left stack: push the left spine. Right stack: push the right spine.
- sum = left top + right top. Equal: true. Smaller: advance the left iterator. Larger: advance the right iterator.
- Stop when the two iterators meet.
class Solution {
public boolean findTarget(TreeNode root, int k) {
Deque<TreeNode> lo = new ArrayDeque<>(), hi = new ArrayDeque<>();
for (TreeNode n = root; n != null; n = n.left) lo.push(n);
for (TreeNode n = root; n != null; n = n.right) hi.push(n);
while (!lo.isEmpty() && !hi.isEmpty() && lo.peek() != hi.peek()) {
int sum = lo.peek().val + hi.peek().val;
if (sum == k) return true;
if (sum < k) {
TreeNode n = lo.pop();
for (n = n.right; n != null; n = n.left) lo.push(n);
} else {
TreeNode n = hi.pop();
for (n = n.left; n != null; n = n.right) hi.push(n);
}
}
return false;
}
}class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
lo, hi = [], []
n = root
while n is not None:
lo.append(n)
n = n.left
n = root
while n is not None:
hi.append(n)
n = n.right
while lo and hi and lo[-1] is not hi[-1]:
total = lo[-1].val + hi[-1].val
if total == k:
return True
if total < k:
n = lo.pop().right
while n is not None:
lo.append(n)
n = n.left
else:
n = hi.pop().left
while n is not None:
hi.append(n)
n = n.right
return Falseclass Solution {
public:
bool findTarget(TreeNode* root, int k) {
stack<TreeNode*> lo, hi;
for (TreeNode* n = root; n != nullptr; n = n->left) lo.push(n);
for (TreeNode* n = root; n != nullptr; n = n->right) hi.push(n);
while (!lo.empty() && !hi.empty() && lo.top() != hi.top()) {
int sum = lo.top()->val + hi.top()->val;
if (sum == k) return true;
if (sum < k) {
TreeNode* n = lo.top(); lo.pop();
for (n = n->right; n != nullptr; n = n->left) lo.push(n);
} else {
TreeNode* n = hi.top(); hi.pop();
for (n = n->left; n != nullptr; n = n->right) hi.push(n);
}
}
return false;
}
};function findTarget(root, k) {
const lo = [], hi = [];
for (let n = root; n !== null; n = n.left) lo.push(n);
for (let n = root; n !== null; n = n.right) hi.push(n);
while (lo.length > 0 && hi.length > 0 && lo[lo.length - 1] !== hi[hi.length - 1]) {
const sum = lo[lo.length - 1].val + hi[hi.length - 1].val;
if (sum === k) return true;
if (sum < k) {
let n = lo.pop();
for (n = n.right; n !== null; n = n.left) lo.push(n);
} else {
let n = hi.pop();
for (n = n.left; n !== null; n = n.right) hi.push(n);
}
}
return false;
}Edge cases to test
- k = 2 · (some value): the same node cannot be used twice
- Single node
Hints
Hint 1
An inorder list of a BST is sorted, so Two Sum II's two pointers apply.
FAQ
What is the best time complexity for Two Sum IV - Input is a BST?
Two BST iterators (O(h) space) runs in O(n) time and O(h) extra space.
Which pattern does Two Sum IV - Input is a BST use?
It is a trees & bst problem that uses the miscellaneous bst questions pattern. Other problems with the same pattern: Inorder Successor in BST, Inorder predecessor, Floor in BST.
Is there a brute force solution for Two Sum IV - Input is a BST?
Yes. Hash set during DFS takes O(n) time and O(n) space. Traverse the tree; for each value, check whether k - value was already seen.
Which edge cases should I test for Two Sum IV - Input is a BST?
k = 2 · (some value): the same node cannot be used twice; Single node.