Two Sum IV - Input is a BST

Description

Two Sum IV - Input is a BST

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 is equal to k, or false otherwise.

Example 1:

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

Example 2:

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

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -104 <= Node.val <= 104
• root is guaranteed to be a valid binary search tree.
• -105 <= k <= 105

Primary Approach: HashSet DFS ($O(N)$ Time, $O(N)$ Space)

Intuition

Adapt the classic Two Sum algorithm using a HashSet while traversing the tree:

1. Traverse the BST using DFS (or BFS).
2. For each node, check if the complement k - node.val already exists in the HashSet.
3. If it exists, return true.
4. Otherwise, add node.val to the set and continue searching left and right subtrees.

import java.util.HashSet;
import java.util.Set;
 
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        return dfs(root, k, set);
    }
 
    private boolean dfs(TreeNode node, int k, Set<Integer> set) {
        if (node == null) return false;
 
        // Check if complement exists in set
        if (set.contains(k - node.val)) return true;
        set.add(node.val);
 
        return dfs(node.left, k, set) || dfs(node.right, k, set);
    }
}
 

Complexity

• Time Complexity: $O(N)$ — In the worst case, every node in the BST is visited once.
• Space Complexity: $O(N)$ — HashSet stores up to $N$ elements, and recursion stack takes $O(H)$ space.

---

Optimal Space Approach: BST Iterator / Two Pointers ($O(N)$ Time, $O(H)$ Space)

Intuition

In a sorted 1D array, Two Sum is solved using standard two pointers (left moving forward, right moving backward). We can simulate two pointers directly on the BST without flattening it into an array by using two BST Iterators (stacks):

1. Next Iterator: Yields values in ascending order ($\text{Left}\to \text{Node}\to \text{Right}$).
2. Before Iterator: Yields values in descending order ($\text{Right}\to \text{Node}\to \text{Left}$).
3. Maintain i = left.next() and j = right.next().
4. While i < j:
   • If i + j == k: return true.
   • If i + j < k: advance i = left.next().
   • If i + j > k: retreat j = right.next().

import java.util.ArrayDeque;
import java.util.Deque;
 
class BSTIterator {
    private Deque<TreeNode> stack = new ArrayDeque<>();
    private boolean isReverse; // false = next() (ascending), true = before() (descending)
 
    public BSTIterator(TreeNode root, boolean isReverse) {
        this.isReverse = isReverse;
        pushAll(root);
    }
 
    public int next() {
        TreeNode node = stack.pop();
        if (!isReverse) {
            pushAll(node.right);
        } else {
            pushAll(node.left);
        }
        return node.val;
    }
 
    private void pushAll(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = !isReverse ? node.left : node.right;
        }
    }
}
 
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) return false;
 
        BSTIterator left = new BSTIterator(root, false); // Smallest element forward
        BSTIterator right = new BSTIterator(root, true);  // Largest element backward
 
        int i = left.next();
        int j = right.next();
 
        while (i < j) {
            if (i + j == k) return true;
            if (i + j < k) {
                i = left.next();
            } else {
                j = right.next();
            }
        }
 
        return false;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Each node is pushed and popped from iterator stacks at most once.
• Space Complexity: $O(H)$ — Stacks hold at most $H$ nodes at any time ($O(\log N)$ for balanced, $O(N)$ for skewed).

---

Key Interview Discussion Points

• Start with HashSet Solution: Implement HashSet DFS first as it takes 10 lines and demonstrates solid foundational coding.
• Proactively Offer Space Optimization: Highlight to the interviewer: “We can reduce auxiliary space from $O(N)$ to $O(H)$ by using two custom BST Iterators to simulate two pointers on the tree dynamically.”

---

Easy Memory Rule

“HashSet DFS = Easy $O(N)$ Space $\to$ Two BST Iterators (next() & before()) = Optimal $O(H)$ Space!”