Problem Summary

You are given the root of a Binary Search Tree (BST) and an integer k.
Your task is to determine whether the tree contains two distinct nodes 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 (2 + 7).
For k = 28, output is false.

Constraints:
The BST may contain a few thousand nodes. The values may be negative or positive.

---

Approach 1: HashSet During DFS (Simple and Efficient)

This is the most common and straightforward solution.

Key Idea

As you traverse the tree, store all node values in a HashSet.
For each node with value x, check whether k - x is already in the set.

If yes, you found a valid pair.
If not, insert x and continue.

Why this works

A HashSet supports constant-time lookup.
You only need to check one complement per node.
The traversal explores each node once, giving an optimal time complexity.

Steps

1. Create an empty HashSet.
2. Traverse the tree using DFS (any order: preorder, inorder, postorder).
3. For every node value val, check:
   • If (k - val) exists in the set → return true.
   • Else insert val into the set.
4. If traversal finishes and no pair is found → return false.

Time and Space

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

---

Approach 2: Inorder Traversal + Two Pointer

This approach uses the fact that an inorder traversal of a BST produces a sorted list.

Key Idea

Convert the BST into a sorted list using inorder traversal.
Then apply the classic two-pointer technique used in sorted arrays.

Why this works

The inorder traversal guarantees sorted order.
Two pointers let you scan for the target pair in linear time.

Steps

1. Perform inorder traversal to get a sorted list.
2. Use left and right pointers:
   • If sum < k, move left pointer.
   • If sum > k, move right pointer.
   • If sum == k, return true.
3. If pointers meet without finding a match, return false.

Time and Space

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 HashSet Approach)

Consider:

    5
   / \
  3   6
 / \   \
2   4   7

k = 9

Traversal Steps

Start at node 5:

• seen = {}
• Complement = 4 (not in seen), add 5 → seen = {5}

Move to node 3:

• Complement = 6 (not in seen), add 3 → seen = {3, 5}

Move to node 2:

• Complement = 7 (not in seen), add 2 → seen = {2, 3, 5}

Move to node 4:

• Complement = 5 (found in seen) → return true

Pair found: 4 + 5 = 9