Two Sum in BST (Check if Exists a Pair with Sum K)

1. Problem Statement and Objective

The objective of the Two Sum in BST problem is to determine whether there exist two distinct integer nodes in a given Binary Search Tree (BST) whose values sum up to a specified target value $K$.

• Input: A Binary Search Tree and an integer target $K$.
• Output: A boolean value (true if such a pair exists, false otherwise).
• Condition: The two integers must be distinct nodes within the tree.

Real-Life Analogy

Mental Hook: Imagine walking down a sorted hallway of lockers numbered in ascending order. If you want two locker numbers to add up to an exact combined locker sum $K$, you station one person at the very beginning (looking for small numbers) and another person at the very end (looking for large numbers). As they walk towards each other, if their combined sum is too large, the person at the end steps backward. If the combined sum is too small, the person at the beginning steps forward.

2. Naive Approach: In-Order Traversal + Two-Pointer Technique

The most straightforward way to solve this problem is to extract the sorted sequence of elements from the BST and then apply a standard two-pointer search.

Step-by-Step Mechanism

1. Generate In-Order Traversal: Perform an in-order traversal (Left, Node, Right) on the BST. Because it is a BST, the resulting traversal array is always strictly sorted in ascending order.
2. Store in Array: Collect these elements into a linear array (e.g., size $N$).
3. Apply Two-Pointer Technique:
   • Place a left pointer (i) at the start (index 0) representing the smallest element.
   • Place a right pointer (j) at the end (index N - 1) representing the largest element.
   • Evaluate arr[i] + arr[j]:
     • If equal to $K$, return true.
     • If less than $K$, increment the left pointer (i++) to increase the sum.
     • If greater than $K$, decrement the right pointer (j--) to decrease the sum.
   • Repeat until the pointers cross.

Sorted In-Order Array: [ 2, 3, 4, 5, 6, 7 ]
                        ^              ^
                        |              |
                     Left (i)       Right (j)

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ to generate the in-order traversal plus $\mathcal{O}(N)$ to scan with two pointers $\rightarrow$ Total $\mathcal{O}(N)$.
• Space Complexity: $\mathcal{O}(N)$ to store the in-order traversal elements in an auxiliary array.

While this approach easily passes online coding platforms, interviewers at top product-based companies often demand an optimal solution that reduces auxiliary space.

3. The Optimal Approach: BST Iterator (Next & Before)

To optimize the space complexity down to $\mathcal{O}(H)$ (where $H$ is the height of the tree), we can avoid storing the entire in-order array in memory. Instead, we use two separate BST Iterators:

1. Next Iterator (Ascending Order): Generates elements from smallest to largest (standard in-order: Left $\rightarrow$ Node $\rightarrow$ Right).
2. Before/Reverse Iterator (Descending Order): Generates elements from largest to smallest (reverse in-order: Right $\rightarrow$ Node $\rightarrow$ Left).

Core Concept

By running both iterators simultaneously from opposite ends, we achieve the exact same behavior as the two-pointer technique on a sorted array—without ever actually building or storing the array.

4. Designing the Unified BST Iterator

Rather than writing two separate classes for ascending and descending traversals (which leads to code duplication), we design a single configurable BSTIterator class using a reverse boolean flag.

Iterator State & Operations

5. C++ and Java Implementation

Below is the production-grade, highly structured code utilizing a single parameterized iterator class to handle both forward (next) and backward (before) traversals.

C++ Implementation

class BSTIterator {
private:
    stack<TreeNode*> myStack;
    bool reverse = true; // true -> before (descending), false -> next (ascending)

    void pushAll(TreeNode* node) {
        while (node != nullptr) {
            myStack.push(node);
            if (reverse) {
                node = node->right; // For descending, go right first
            } else {
                node = node->left;  // For ascending, go left first
            }
        }
    }

public:
    BSTIterator(TreeNode* root, bool isReverse) {
        reverse = isReverse;
        pushAll(root);
    }

    bool hasNext() {
        return !myStack.empty();
    }

    int next() {
        TreeNode* tmpNode = myStack.top();
        myStack.pop();
        if (reverse) {
            pushAll(tmpNode->left);   // Move left for descending order
        } else {
            pushAll(tmpNode->right);  // Move right for ascending order
        }
        return tmpNode->val;
    }
};

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        if (!root) return false;

        // L initialized for normal in-order (ascending)
        BSTIterator l(root, false);
        // R initialized for reverse in-order (descending)
        BSTIterator r(root, true);

        int i = l.next();
        int j = r.next();

        while (i < j) {
            if (i + j == k) return true;
            else if (i + j < k) {
                i = l.next();
            } else {
                j = r.next();
            }
        }
        return false;
    }
};

Java Implementation

class BSTIterator {
    private Stack<TreeNode> stack = new Stack<>();
    private boolean reverse = true; // true -> before (descending), false -> next (ascending)

    public BSTIterator(TreeNode root, boolean isReverse) {
        reverse = isReverse;
        pushAll(root);
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

    public int next() {
        TreeNode tmpNode = stack.pop();
        if (reverse) {
            pushAll(tmpNode.left);   // Move left for descending order
        } else {
            pushAll(tmpNode.right);  // Move right for ascending order
        }
        return tmpNode.val;
    }

    private void pushAll(TreeNode node) {
        while (node != null) {
            stack.push(node);
            if (reverse) {
                node = node.right; // For descending, push right
            } else {
                node = node.left;  // For ascending, push left
            }
        }
    }
}

public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) return false;

        // Left iterator for ascending order (next)
        BSTIterator l = new BSTIterator(root, false);
        // Right iterator for descending order (before)
        BSTIterator r = new BSTIterator(root, true);

        int i = l.next();
        int j = r.next();

        while (i < j) {
            if (i + j == k) {
                return true;
            } else if (i + j < k) {
                i = l.next();
            } else {
                j = r.next();
            }
        }
        return false;
    }
}

6. Step-by-Step Execution Flow Walkthrough

Consider a BST with values [5, 3, 6, 2, 4, 7] and target $K = 9$.

         5
       /   \
      3     6
     / \     \
    2   4     7

1. Initialization:
   • l iterator starts at minimum element: i = 2
   • r iterator starts at maximum element: j = 7
2. Iteration 1:
   • Check sum: i + j = 2 + 7 = 9.
   • Matches target $K = 9$.
   • Result: Returns true immediately.

What if target $K = 10$?

1. Initialization: i = 2, j = 7 (Sum = 9, $9 < 10$).
   • Action: i moves to next element (3).
2. Iteration 2: i = 3, j = 7 (Sum = 10).
   • Matches target $K = 10$.
   • Result: Returns true.

7. Complexity Summary & Comparison

8. Summary and Key Takeaways

• Problem Reduction: Two Sum in a BST can be viewed as the classic Two-Pointer Two Sum problem on a sorted array.
• In-Order Traversal Property: A standard in-order traversal of a BST naturally yields elements in ascending sorted order.
• Reverse In-Order Traversal: Visiting nodes in Right -> Node -> Left order yields elements in descending sorted order.
• Unified Iterator Pattern: Using a boolean reverse flag inside a single BSTIterator class prevents code duplication and demonstrates clean object-oriented design during technical interviews.
• Optimal Space Efficiency: By utilizing explicit stacks mirroring the height of the tree, space complexity is reduced from $\mathcal{O}(N)$ to $\mathcal{O}(H)$.
• Pointer Convergence: The iteration halts when the two pointers cross (i >= j), guaranteeing all valid pairs have been checked without redundant work.