Two Sum IV BST — Finding Pairs in a Tree With a Hash Set

Problem Statement#

Given the root of a Binary Search Tree and an integer k, return true if there exist two elements in the BST such that their sum equals k.

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].
• -10^4 <= Node.val <= 10^4
• root is guaranteed to be a valid BST.
• -10^5 <= k <= 10^5

Input:  root = [5,3,6,2,4,null,7], k = 9
Output: true

Input:  root = [5,3,6,2,4,null,7], k = 28
Output: false

Why This Problem Matters#

LeetCode 653 is a classic FAANG warm-up. Google, Facebook, and Amazon use it on phone screens because it tests two skills at once: tree traversal and the canonical Two Sum hash-set pattern. Candidates who only know DFS will brute-force pair every node with every other node in O(n^2). Candidates who only know Two Sum will not realize that the data lives in a tree, not an array.

The real signal interviewers want is whether you can fuse the two patterns: do one traversal of the tree, and during that traversal use a hash set to record values you have seen. The moment you visit a node whose complement k - node.val already lives in the set, you can return true immediately.

This problem also opens the door to the BST-aware follow-up: "Can you do it in O(1) extra space?" That answer uses two iterators and the in-order traversal property of BSTs.

The Core Insight#

A BST is just a container of n integers. The Two Sum trick still applies: for each value v, ask whether k - v has been seen. The only twist is that we must visit nodes in some order that lets us check before insertion. Any traversal works (preorder, inorder, postorder, BFS) because order does not affect set membership.

Visual Dry Run#

Tree [5,3,6,2,4,null,7], target k = 9. We use DFS preorder.

Solution (Optimal)#

class Solution:
    def findTarget(self, root, k: int) -> bool:
        seen = set()
 
        def dfs(node) -> bool:
            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)

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);
};

Time: O(n) — each node is visited at most once and set operations are O(1) average. Space: O(n) — the hash set may hold every node value, plus O(h) recursion stack.

Common Mistakes#

• Adding the current value to the set before checking the complement, which can cause false positives when k = 2 * node.val.
• Reaching for nested DFS to pair every node with every other node, producing O(n^2) work.
• Ignoring the BST property entirely and missing the O(1) space follow-up.
• Forgetting that values can be negative, so k - node.val can fall below the typical positive-only assumption.
• Returning false from the helper but never short-circuiting the parent recursion when a match is found.

Interview Tips#

• State the pattern by name: "This is Two Sum I, just delivered through a tree."
• Ask early whether duplicate values are allowed; the BST definition matters.
• After solving with a hash set, volunteer the BST-iterator follow-up to demonstrate depth.
• Mention that any traversal order works, and pick the one that is shortest to write (DFS preorder).

Follow-up Questions#

• Can you solve it in O(h) extra space using BST iterators? Hint: two iterators, one increasing, one decreasing, two-pointer style.
• What if the BST is balanced and you need O(log n) space? Hint: same iterator approach plus an explicit stack.
• How would you adapt this to "are there three values that sum to k"? Hint: fix one node, then run Two Sum on the remaining values.
• What if the tree is not a BST? Hint: hash-set DFS still works; only the iterator follow-up depends on BST ordering.
• Can you return all pairs that sum to k? Hint: do not short-circuit; collect matches into a list during DFS.

Key Takeaways#

• LeetCode 653 fuses BST traversal with the Two Sum hashmap pattern.
• Check k - node.val in the set before adding node.val to avoid spurious self-pair matches.
• Time is O(n) and space is O(n) when using a hash set on top of DFS.
• The BST property unlocks an O(h) space follow-up using two iterators.
• Any traversal order works because hash-set membership is order-agnostic.
• This is a phone-screen favorite at Google, Facebook, and Amazon.
• Recognize the pattern of "Two Sum delivered through a different container" — it shows up in linked lists, streams, and graphs.