The O(n) Club: Two Sum IV – The BST Showdown You Didn’t Know You Needed

The O(n) Club: Two Sum IV – The BST Showdown You Didn’t Know You Needed

⚡ TL;DR

Given a binary search tree and a target k, does any pair of different nodes add up to k? Brute force is O(n²) and a career bummer. HashSet plus DFS wins hearts and interviews:

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);
}

🧠 How Devs Usually Mess This Up

You’ve seen the carnage:

🔍 What’s Actually Going On

This isn’t just “Two Sum”—it’s “Two Sum with a Sorted Playground”. Your BST keeps everything in secret low-to-high order (like CPUs arrange their hopes and dreams).
HashSet+DFS is clean and works for any tree shape. But you could:

🛠️ PseudoCode

• DFS + HashSet:
  • If the tree is empty, return false and fake a phone call.
  • For each node you visit:
    • Check if (k – node.val) is in the set. If yes—Bam! Return true.
    • Otherwise, add node.val to the set.
    • Recurse left, then right (or right, then left—it’s DFS, not a soufflé).
  • If you never hit true, congrats, no such pair exists.
  • // Java: boolean dfs(TreeNode node, int k, Set<Integer> found)
• Inorder + Two Pointers:
  • Do an inorder traversal (left-root-right), toss values in a list.
  • Set left = 0, right = list.size() - 1.
  • While left < right:
  • If list[left]+list[right] == k, return true.
  • If sum < k, move left forward; else, move right back.
  • Fall off the loop? False.
  • // Java: List<Integer> nums = new ArrayList<>();

💻 The Code

// Java: DFS + HashSet
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);
}
 // If you really want: Inorder + Two Pointers
public boolean findTarget(TreeNode root, int k) {
    List<Integer> nums = new ArrayList<>();
    inorder(root, nums);
    int left = 0, right = nums.size() - 1;
    while(left < right) {
        int sum = nums.get(left) + nums.get(right);
        if(sum == k) return true;
        if(sum < k) left++;
        else right--;
    }
    return false;
}
private void inorder(TreeNode node, List<Integer> nums) {
    if(node == null) return;
    inorder(node.left, nums);
    nums.add(node.val);
    inorder(node.right, nums);
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t double-count. Pair must use different nodes, no matter how lonely your BST looks.
• Null root isn’t a freebie. Interviewers love edge cases; you should too.
• Time/Space: Both legit methods are O(n) time. DFS+HashSet is O(n) space, Inorder+Pointers is O(n) extra space. Two-stack is O(h) space (if implemented well) where h = tree height, but now we’re min/maxing like a boss.
• Super long left or right chains? (a.k.a. linked list cosplaying as BST) Watch your recursion depth.

🧠 Interviewer Brain-Tattoo

“Turning a BST into an array is like ordering gourmet takeout and blending it into a protein shake. Just don’t.”