Two Sum IV - BST — Hash Set + In-Order Traversal

Problem 184 · Two Sum IV — BST

Difficulty: Medium · Pattern: Hash Set + DFS

Given a BST root and target k, return true if any two nodes sum to k.

Intuition

DFS the tree, maintaining a set of visited values. At each node check if k - node.val is already seen.

Solutions

// C++
bool findTarget(TreeNode* root, int k) {
    unordered_set<int> seen;
    function<bool(TreeNode*)> dfs = [&](TreeNode* node) -> bool {
        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);
}

// Java
Set<Integer> seen = new HashSet<>();
public boolean findTarget(TreeNode root, int k) {
    if (root == null) return false;
    if (seen.contains(k - root.val)) return true;
    seen.add(root.val);
    return findTarget(root.left, k) || findTarget(root.right, k);
}

// JavaScript
var findTarget = function(root, k) {
    const seen = new Set();
    const 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);
};

# Python
def findTarget(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)

Complexity

Time: O(n)
Space: O(n)