TreeEasyO(n) time · O(n) space

Two Sum IV - BST

Mahabharata — The Paired Warriors — Do Two Values in the BST Sum to the Target?

BST में दो योद्धा — जिनका योग k। HashSet से जांचो — k-val पहले देखा था?॥

*Two warriors in the BST — whose sum is k. Check with HashSet — was k-val seen before?*

The Story

Given a BST root and integer k, determine if there exist two nodes whose values sum to k.

For BST `[5,3,6,2,4,null,7]`, k=9: true (2+7=9 or 3+6=9... actually 3+6=9 ✓). For same BST, k=28: false.

**Approach 1 — HashSet DFS (simplest):** - Traverse the tree (any order) - For each node, check if `k - node.val` is in the set - If yes → found! If no → add `node.val` to set

```java public boolean findTarget(TreeNode root, int k) { return find(root, k, new HashSet<>()); } boolean find(TreeNode root, int k, Set<Integer> set) { if (root == null) return false; if (set.contains(k - root.val)) return true; set.add(root.val); return find(root.left, k, set) || find(root.right, k, set); } ```

**Approach 2 — Inorder + Two Pointers:** - Get sorted list via inorder traversal - Apply two-pointer technique

```java List<Integer> list = new ArrayList<>(); inorder(root, list); // Gets sorted values int lo=0, hi=list.size()-1; while (lo < hi) { int sum = list.get(lo) + list.get(hi); if (sum == k) return true; if (sum < k) lo++; else hi--; } return false; ```

Both approaches are O(n) time, O(n) space. The HashSet approach works even for general binary trees. The two-pointer approach exploits BST's sorted inorder.

Trace BST `[5,3,6,2,4,null,7]`, k=9: - HashSet approach: visit 5, add 5. visit 3, 9-3=6 not in set. add 3. visit 2, 9-2=7 not in set, add 2. visit 4, 9-4=5 IN SET → return true ✓

The Nested DFS Approach

For each node, search the entire tree for k-val. O(n²).

java

// O(n²): for each node, search for complement
// HashSet approach is O(n) and already optimal

The HashSet Complement Check Wisdom

DFS any order. For each node: if k-val in set → true. Else add val to set. Or: inorder→list + two pointers.

java

public boolean findTarget(TreeNode root, int k) {
    return find(root, k, new HashSet<>());
}

boolean find(TreeNode root, int k, Set<Integer> set) {
    if (root == null) return false;
    if (set.contains(k - root.val)) return true;
    set.add(root.val);
    return find(root.left, k, set) || find(root.right, k, set);
}

Step-by-Step Walkthrough

BST=[2], k=4: find(2,4,{}). 4-2=2 not in {}. add 2. find(null)||find(null)=false. Return false ✅ (no two distinct nodes)

Deep Insight

**Two Sum on BST vs Array:** - Array: sort + two pointers or hashset - BST: inorder gives sorted array directly (exploit BST property) - HashSet approach: works for any binary tree, O(n) space

**Note on 'distinct' nodes:** The problem requires two different nodes (not the same node twice). The HashSet approach naturally handles this: we add `root.val` AFTER checking `k - root.val`. So even if k = 2*root.val, the check happens before the value is added, preventing double-counting.

**Two-pointer approach uses O(n) extra space** (the inorder list). The BST iterator approach (using two stack-based iterators going in opposite directions) achieves O(h) space.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²)	O(1)	Nested DFS
Optimal	O(n)	O(n)	HashSet or inorder list + two pointers

Pattern Recognition

✅ Two Sum in BST: HashSet DFS or inorder+two-pointer
✅ HashSet: add val after checking k-val (prevents self-match)
✅ Inorder gives sorted list for two-pointer
✅ BST iterator approach: O(h) space

**LeetCode Trigger Phrases:**
→ "two sum IV - input is a BST"
→ Find two nodes summing to target
→ Two Sum pattern on tree structure

Bhagavad Gita 15.16

द्वाविमौ पुरुषौ लोके क्षरश्चाक्षर एव च।

There are two types of beings in this world — the perishable and the imperishable.

Connection: The Two Sum IV problem seeks two values that together complete a whole — like two complementary forces whose union achieves the target. The HashSet approach embodies this: for each value encountered, it looks backward for its complement (k-val), the other half that would make the pair complete. Like the Gita's enumeration of pairs of opposites that together constitute reality, the algorithm seeks the one value that completes each partial sum.