Two Sum IV - Input is a BST
Problem
Given the root of a binary search tree and an integer k, return true iff there exist two different elements in the BST whose sum equals k.
root = [5,3,6,2,4,null,7], k = 9truedef find_target(root, k):
seen = set()
def dfs(node):
if not node:
return False
if k - node.val in seen:
return True
seen.add(node.val)
return dfs(node.left) or dfs(node.right)
return dfs(root)function findTarget(root, k) {
const seen = new Set();
function dfs(node) {
if (!node) return false;
if (seen.has(k - node.val)) return true;
seen.add(node.val);
return dfs(node.left) || dfs(node.right);
}
return dfs(root);
}class Solution {
public boolean findTarget(TreeNode root, int k) {
Set<Integer> seen = new HashSet<>();
return dfs(root, k, seen);
}
private boolean dfs(TreeNode node, int k, Set<Integer> seen) {
if (node == null) return false;
if (seen.contains(k - node.val)) return true;
seen.add(node.val);
return dfs(node.left, k, seen) || dfs(node.right, k, seen);
}
}bool findTarget(TreeNode* root, int k) {
unordered_set<int> seen;
function<bool(TreeNode*)> dfs = [&](TreeNode* node) {
if (!node) return false;
if (seen.count(k - node->val)) return true;
seen.insert(node->val);
return dfs(node->left) || dfs(node->right);
};
return dfs(root);
}Explanation
This is the classic two-sum idea applied to a tree. We walk the tree once and remember every value we have already seen in a hash set called seen, which gives instant lookups.
For the current node, the partner we need is k - node.val. The check if k - node.val in seen asks: have we already met the number that completes the pair? If yes, two different nodes sum to k and we return True.
If no partner is waiting yet, we drop node.val into seen and keep exploring with dfs(node.left) or dfs(node.right). The or means a single match anywhere makes the whole answer true.
Example: [5,3,6,2,4,null,7], k = 9. We visit 5 (store it), then 3, 2, 4. At 4 the needed partner is 9 - 4 = 5, which is already in seen, so we return True.
Each node is visited once and set lookups are constant, so the runtime is O(n).