Problem Summary

You are given the root of a Binary Search Tree (BST) and an integer k.
Your task is to determine whether there exist two distinct nodes in the tree whose values sum to k.

Return true if such a pair exists; otherwise return false.

Example BST:

    5
   / \
  3   6
 / \   \
2   4   7

Example queries:
For k = 9, output is true because 2 + 7 = 9.
For k = 28, output is false.

---

Approach 1: HashSet During DFS (Most Common and Easiest)

This is the cleanest and fastest approach for interviews.

Key Idea

Traverse the BST. For each node with value x, check if k - x already exists in a HashSet.
If yes, you found your pair.
If not, insert x and continue searching.

Why This Works

A HashSet supports constant-time lookups.
You only need to store values seen so far.
Once you find a value whose complement is already in the set, the answer is immediately true.

This avoids converting the BST into another structure and works for any tree shape.

Steps

1. Create an empty HashSet.
2. Perform DFS (left, right order does not matter).
3. At each node:
   • If (k - node.val) is in the HashSet → return true.
   • Otherwise add node.val to the set.
4. After traversal, return false if no pair found.

Complexity

Time: O(n)
Space: O(n)

---

Approach 2: Inorder Traversal + Two Pointers

This approach makes use of BST’s inherent sorted structure.

Key Idea

1. Inorder traversal of a BST produces values in sorted order.
2. Use two pointers on the sorted list to find two numbers that sum to k.

Why This Works

This converts the problem into the classic Two Sum on a sorted array.
Two-pointer scanning is efficient and deterministic.

Steps

1. Do an inorder traversal and store values in an ArrayList.
2. Use two indexes:
   • left = 0
   • right = list.size() – 1
3. While left < right:
   • If sum == k → return true
   • If sum < k → left++
   • If sum > k → right–
4. If finished without match → return false

Complexity

Time: O(n)
Space: O(n)

---

Java Code (HashSet DFS Approach)

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> seen = new HashSet<>();
        return dfs(root, k, seen);
    }

    private boolean dfs(TreeNode node, int k, Set<Integer> seen) {
        if (node == null) return false;

        if (seen.contains(k - node.val)) {
            return true;
        }

        seen.add(node.val);

        return dfs(node.left, k, seen) || dfs(node.right, k, seen);
    }
}

---

Java Code (Inorder + Two Pointer Approach)

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);

        int left = 0;
        int right = list.size() - 1;

        while (left < right) {
            int sum = list.get(left) + list.get(right);

            if (sum == k) return true;
            if (sum < k) left++;
            else right--;
        }
        return false;
    }

    private void inorder(TreeNode node, List<Integer> list) {
        if (node == null) return;
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }
}

---

Dry Run (Using the HashSet Approach)

Consider the BST:

    5
   / \
  3   6
 / \   \
2   4   7

k = 9

Step-by-step

1. Visit node 5
   seen = {}
   Complement needed = 4 (not in set)
   Add 5 → seen = {5}
2. Visit node 3
   Complement needed = 6 (not in set)
   Add 3 → seen = {3, 5}
3. Visit node 2
   Complement needed = 7 (not in set)
   Add 2 → seen = {2, 3, 5}
4. Visit node 4
   Complement needed = 5 (found in set)
   Return true immediately

Pair found: 4 + 5 = 9