Two Sum in BST in DSA Java

Mental Model

We want to find two numbers in a tree that add up to a target by checking pairs efficiently.

Analogy: Imagine a sorted list of prices in a store. You want to find two items that together cost exactly your budget. You look from the cheapest and the most expensive, moving inward to find the perfect pair.

    5
   / \
  3   7
 / \   \
2   4   8

We want to find two nodes whose values add up to target.

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, target = 9

Goal: Find if there exist two nodes in BST whose values sum to 9

Step 1: Initialize two pointers: left at smallest (2), right at largest (8)

Left pointer at 2, Right pointer at 8

Why: Start with smallest and largest to check sums efficiently

Step 2: Sum values: 2 + 8 = 10, which is greater than 9

Sum=10 > target=9, move right pointer left

Why: Sum too big, decrease sum by moving right pointer to next smaller value

Step 3: Right pointer moves to 7

Left pointer at 2, Right pointer at 7

Why: Try smaller value to reduce sum

Step 4: Sum values: 2 + 7 = 9, equals target

Sum=9 == target=9, pair found

Why: Found two nodes that sum to target

Result:

2 -> ... -> 7
Pair found: 2 + 7 = 9

Annotated Code

DSA Java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class TwoSumInBST {

    // Helper to get next smallest or largest value in BST iterator
    static class BSTIterator {
        Stack<TreeNode> stack = new Stack<>();
        boolean forward;

        BSTIterator(TreeNode root, boolean forward) {
            this.forward = forward;
            pushAll(root);
        }

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

        int next() {
            TreeNode node = stack.pop();
            if (forward) pushAll(node.right);
            else pushAll(node.left);
            return node.val;
        }

        private void pushAll(TreeNode node) {
            while (node != null) {
                stack.push(node);
                node = forward ? node.left : node.right;
            }
        }
    }

    public static boolean findTarget(TreeNode root, int k) {
        if (root == null) return false;
        BSTIterator leftIter = new BSTIterator(root, true);  // smallest to largest
        BSTIterator rightIter = new BSTIterator(root, false); // largest to smallest

        int i = leftIter.next();
        int j = rightIter.next();

        while (i < j) {
            int sum = i + j;
            if (sum == k) return true;
            else if (sum < k) {
                if (leftIter.hasNext()) i = leftIter.next();
                else break;
            } else {
                if (rightIter.hasNext()) j = rightIter.next();
                else break;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(8);

        int target = 9;
        System.out.println(findTarget(root, target));
    }
}

BSTIterator leftIter = new BSTIterator(root, true); // smallest to largest

Initialize iterator to get next smallest values

BSTIterator rightIter = new BSTIterator(root, false); // largest to smallest

Initialize iterator to get next largest values

int i = leftIter.next();

Get smallest value from BST

int j = rightIter.next();

Get largest value from BST

while (i < j) {

Loop until pointers cross

int sum = i + j;

Calculate sum of current pair

if (sum == k) return true;

If sum matches target, return true

else if (sum < k) { if (leftIter.hasNext()) i = leftIter.next(); else break; }

Sum too small, move left pointer forward to increase sum if possible

else { if (rightIter.hasNext()) j = rightIter.next(); else break; }

Sum too big, move right pointer backward to decrease sum if possible

Output

true

Complexity Analysis

Time: O(n) because in worst case we may visit all nodes once with two iterators

Space: O(h) where h is tree height due to stack space in iterators

vs Alternative: Naive approach checks all pairs O(n^2), this uses BST properties and two iterators to reduce to O(n)

Edge Cases

Empty tree

Returns false immediately as no nodes exist

DSA Java

if (root == null) return false;

Single node tree

Returns false because we need two distinct nodes

DSA Java

while (i < j) { ... } ensures pointers do not cross or equal

No pair sums to target

Returns false after exhausting all pairs

DSA Java

while (i < j) loop ends without return true

When to Use This Pattern

When asked to find two elements summing to a target in a BST, use two-pointer technique with BST iterators to efficiently find the pair.

Common Mistakes

Mistake: Trying to convert BST to array first, losing O(h) space advantage
Fix: Use BST iterators to traverse without full conversion

Mistake: Not handling case when pointers cross, causing infinite loop
Fix: Use condition while (i < j) to stop when pointers meet or cross

Summary

Finds if two nodes in BST sum to a target using two iterators from smallest and largest.

Use when you need to check pairs summing to a value efficiently in BST.

The key insight is using two BST iterators moving inward to find the sum without extra space.

Practice

1. What is the main goal of the Two Sum in BST problem?

easy

A. Count the total number of nodes in the BST.

B. Find the maximum value in the BST.

C. Find two nodes in the BST whose values add up to a target sum.

D. Check if the BST is balanced.

Solution

1. Step 1: Understand the problem statement

   The problem asks to find if there exist two nodes in the BST such that their values add up to a given target.

2. Step 2: Identify the goal

   The goal is to check for the existence of such a pair, not to find max, balance, or count nodes.

3. Final Answer:

   Find two nodes in the BST whose values add up to a target sum. -> Option C

4. Quick Check:

   Two Sum in BST means finding two nodes summing to target [OK]

Hint: Remember Two Sum means pair sums to target [OK]

Common Mistakes:

• Confusing Two Sum with finding max value
• Thinking problem is about BST balance
• Counting nodes instead of finding pairs

2. Which of the following Java method signatures correctly represents a function to solve Two Sum in BST?

easy

A. public int findSum(TreeNode root, int k)

B. public boolean findTarget(TreeNode root, int k)

C. public void findTarget(TreeNode root, int k)

D. public TreeNode findPair(TreeNode root, int k)

Solution

1. Step 1: Understand the return type needed

   The function should return true or false if a pair exists, so return type is boolean.

2. Step 2: Check method signatures

   public boolean findTarget(TreeNode root, int k) returns boolean and accepts root and target, matching the problem requirements.

3. Final Answer:

   public boolean findTarget(TreeNode root, int k) -> Option B

4. Quick Check:

   Boolean return for existence check [OK]

Hint: Two Sum returns true/false, so use boolean return [OK]

Common Mistakes:

• Using void return type instead of boolean
• Returning int instead of boolean
• Returning TreeNode instead of boolean

3. Given the BST below and target = 9, what will the output of findTarget(root, 9) be?

      5
     / \
    3   6
   / \   \
  2   4   7

medium

A. true

B. false

C. null

D. Runtime Error

Solution

1. Step 1: Identify pairs that sum to 9

   Check pairs: 2+7=9, 3+6=9, 4+5=9. All valid pairs exist.

2. Step 2: Confirm function returns true if any pair found

   Since pairs exist, function returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Pairs 2+7 or 3+6 sum to 9 [OK]

Hint: Check pairs adding to target in BST nodes [OK]

Common Mistakes:

• Ignoring valid pairs and returning false
• Confusing output with node values
• Assuming null or error without reason

4. Consider this buggy code snippet for Two Sum in BST:

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;
    if (set.contains(k - node.val)) return true;
    set.add(node.val);
    dfs(node.left, k, set);
    dfs(node.right, k, set);
    return false;
}

What is the main bug causing incorrect results?

medium

A. Using HashSet instead of ArrayList.

B. Adding node values after checking set.

C. Not checking if root is null in findTarget.

D. Missing return statements from recursive calls in dfs.

Solution

1. Step 1: Analyze dfs recursive calls

   dfs calls itself on left and right but ignores their return values.

2. Step 2: Understand impact of missing returns

   Without returning results of recursive calls, function always returns false unless first node matches.

3. Step 3: Correct fix

   Return true if either left or right dfs call returns true.

4. Final Answer:

   Missing return statements from recursive calls in dfs. -> Option D

5. Quick Check:

   Return recursive calls to propagate true [OK]

Hint: Always return recursive call results in DFS [OK]

Common Mistakes:

• Ignoring return values of recursive calls
• Using wrong data structure for lookup
• Not handling null root properly

5. You want to optimize Two Sum in BST to use O(h) space, where h is tree height. Which approach is best?

hard

A. Use two iterators: one in-order and one reverse in-order traversal.

B. Store all node values in a list and use two pointers.

C. Use a HashSet to store visited nodes during DFS.

D. Convert BST to sorted array and binary search for complements.

Solution

1. Step 1: Understand space complexity of approaches

   Storing all nodes uses O(n) space; HashSet also O(n); array conversion O(n).

2. Step 2: Two iterator approach

   Using two iterators (in-order and reverse in-order) simulates two pointers with O(h) space.

3. Step 3: Choose best approach

   Use two iterators: one in-order and one reverse in-order traversal. uses O(h) space and is optimal for BST Two Sum.

4. Final Answer:

   Use two iterators: one in-order and one reverse in-order traversal. -> Option A

5. Quick Check:

   Two iterators give O(h) space [OK]

Hint: Two pointers in BST use two iterators for O(h) space [OK]

Common Mistakes:

• Using full list storage causing O(n) space
• Relying on HashSet which uses O(n) space
• Ignoring BST properties for optimization