Solution: Two Sum IV – Input Is a BST

Statement

Given the root of a binary search tree and an integer k, determine whether there are two elements in the BST whose sum equals k. Return TRUE if such elements exist or FALSE otherwise.

Constraints:

• The number of nodes in the tree is in the range $[1, 10^3]$.

• $-10^3 \leq$ Node.data $\leq 10^3$

• root is guaranteed to be a valid binary search tree.

• $-10^4 \leq$ k $\leq 10^4$

Solution

The core intuition behind solving this problem is to use a set to track values encountered during a breadth-first search of the binary search tree (BST). We calculate each node’s complement (i.e., the difference between k and the node’s value) and check if this complement already exists in the set. If it does, it means there is another node in the BST whose value, when added to the current node’s value, equals k, and we return TRUE. Otherwise, we add the current node’s value to the set. If no two nodes with the required sum are found by the end of the traversal, we return FALSE.

Using the intuition above, the solution can be implemented as follows:

1. If the BST is empty, return FALSE.

2. Define a set, seen, to store the visited node values.

3. Define a queue, q, to perform the level-order traversal of the BST.

   1. Enqueue root to q to start the traversal from the root node.

4. While the queue is not empty, repeat the following steps:

   1. Dequeue a node from the front of the queue.

   2. Check if the complement of the current node’s value exists in the seen set. If yes, return TRUE.

   3. Add the current node’s value to the seen set.

   4. Enqueue its left and right children.

5. If no two nodes with the required sum are found, return FALSE.

Let’s look at the following illustration to get a better understanding of the solution: