Two Sum IV - Input is a BST: Hash Set Tree Traversal

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.

This is LeetCode 653: Two Sum IV - Input is a BST. It combines the classic Two Sum complement lookup with a tree traversal. If you already know how to solve Two Sum on an array, you are 90% of the way there. The only difference is that the values live in tree nodes instead of array slots, so you need a traversal to visit them.

The approach

The core idea: traverse the tree in any order (BFS or DFS, it does not matter), and maintain a hash set of values you have already seen. At each node, compute the complement k - node.val and check if it is in the set. If yes, you found a pair. If no, add node.val to the set and keep going.

This works because the hash set gives you O(1) lookup for any previously visited value. You do not need to search the tree for the complement. You already recorded it.

You might notice the input is a BST, not just any binary tree. That opens the door to a second approach: do an inorder traversal to get a sorted list, then use the two-pointer technique from Two Sum II. That also works, but it requires O(n) extra space for the sorted list (or a more complex in-place traversal with two iterators). The hash set approach is simpler and works on any binary tree, not just BSTs.

The solution

def find_target(root, k):
    seen = set()
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            continue
        if k - node.val in seen:
            return True
        seen.add(node.val)
        queue.append(node.left)
        queue.append(node.right)
    return False

Let's walk through each piece:

• seen = set() creates an empty hash set. This stores every node value we have visited so far.
• queue = [root] initializes a BFS queue with the root node.
• node = queue.pop(0) dequeues the next node to process.
• if node is None: continue skips null children. This handles leaf nodes cleanly without extra checks.
• if k - node.val in seen is the complement lookup. If the value we need to pair with the current node is already in the set, we found two nodes that sum to k.
• seen.add(node.val) records this node so future nodes can match against it.
• queue.append(node.left) and queue.append(node.right) enqueue both children for later processing.
• return False means we exhausted the entire tree without finding a valid pair.

Visual walkthrough

Let's trace through the BST [5, 3, 6, 2, 4, null, 7] with k = 9. Watch how the hash set builds up as BFS processes each level, and how the complement check finds the answer.

The traversal visits node 5 first, then its children 3 and 6. When we reach node 6, we compute the complement: 9 - 6 = 3. We check the set and find 3 is already there (added when we visited node 3 in the previous step). That means 3 + 6 = 9, so we return true immediately without visiting the rest of the tree.

Complexity analysis

Time is O(n) in the worst case. You visit each node at most once. At each node, the hash set lookup and insertion are O(1) on average. In the best case, you find the pair early and stop, but the worst case is scanning all n nodes.

Space is O(n). The hash set can hold up to n values. The BFS queue (or DFS stack) also holds up to O(n) nodes in the worst case (a completely lopsided tree for DFS, or the widest level for BFS).

The building blocks

This problem is built on two fundamental building blocks:

1. Complement lookup (complement-lookup). The idea of computing target - current and checking whether you have seen it before. This is the exact same technique from Two Sum: instead of searching for a matching value, you compute what value you need and check a hash set or hash map in O(1) time. The pattern works whether the data comes from an array, a linked list, a tree, or a stream.

2. Tree traversal with auxiliary state (tree-traversal-aux-state). Traversing a tree while maintaining a data structure alongside the traversal. Here the auxiliary state is a hash set. In other problems it might be a running sum, a frequency map, or a min/max tracker. The key idea is that the traversal handles visiting every node, and the auxiliary structure handles the per-node logic. Keeping these two concerns separate makes the code clean and reusable.

Edge cases to watch for

• Empty tree (root is None): return False. There are no nodes to form a pair.
• Single node: return False. You need two distinct nodes. A single node cannot pair with itself, and the complement check runs before adding the current node, so it naturally handles this.
• All nodes with the same value: if every node holds value v and k = 2v, the algorithm correctly returns True because it adds v to the set on the first visit and finds it on the second visit. Two distinct nodes with the same value count as a valid pair.
• Negative values: the complement formula k - node.val works identically with negative numbers. No special handling needed.

From understanding to recall

You just traced through a solution that traverses a BST with BFS, checks a hash set for the complement at every node, and returns as soon as a pair is found. The pattern is a direct extension of Two Sum to a tree data structure.

But in an interview, will you remember to check the complement before adding the current node to the set? Will you remember that BFS and DFS both work here, or will you waste time trying to exploit the BST ordering? Will you handle the null-child case cleanly, or will you add special checks everywhere?

Understanding is not recall. You understood the solution. Recall means you can write it cold, under pressure, without mixing up the order of operations or forgetting to handle null nodes.

Spaced repetition builds recall. You practice writing the solution from scratch at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the hash set initialization, the complement check, and the traversal loop from memory. After a few repetitions, the complement-lookup and tree-traversal-aux-state patterns become automatic.

Related posts

• Two Sum - The original complement lookup problem on an array. Master this first, then Two Sum IV is a natural extension.
• Binary Search Tree Iterator - A building block for the two-pointer approach: iterate the BST in sorted order without materializing the full list.
• Validate Binary Search Tree - Another BST traversal problem that teaches you how to carry state through a tree walk.