The O(n) Club: Path Sum and the Java Leaf-Hunting Gauntlet

The O(n) Club: Path Sum and the Java Leaf-Hunting Gauntlet

⚡ TL;DR

Loyal binary searchers, here’s the deal: You want to know if any root-to-leaf path in your binary tree adds up to a specific sum. (No, not “any node to any node,” not “find all of them,” and not “look impressive with 100 lines of code.”) Just find one, drop the mic, and go get a coffee. Here’s the barebones Java everyone wishes they wrote before overengineering:

// Java. Direct. No nonsense.
public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == targetSum;
    return hasPathSum(root.left, targetSum - root.val)
        || hasPathSum(root.right, targetSum - root.val);
}

🧠 How Devs Usually Mess This Up

Let’s get real: most developers treat “leaf” like a suggestion instead of the law. So, enjoy these classic faceplants:

• Thinking any path is fair game: Sorry, only root-to-leaf counts. Those halfway pit stops are invalid. Leaf == both kids null. Period.
• Trigger-happy sum checks: Don’t check at every node! Only at the leaf. Trees don’t grade you for effort.
• Collecting every possible path: No points for thoroughness. Return true the second you strike gold. Computers appreciate laziness here.
• Dragging in fancy data structures: Unless you like debugging stack traces, recursion suffices. BFS? Stack? For this? Why?

🔍 What’s Actually Going On

Imagine spelunking through a tree-cave, torch in hand, subtracting treasure as you go. The quest is simple: if you find a leaf AND your subtraction magic equals zero, you’ve won. No need to plunder every cave—just the first with loot.

Think of it like a filesystem: Is there a file (leaf) in the tree whose permissions sum to your desired number? If yes, return true, close your laptop, and claim victory.

🛠️ PseudoCode

• Check if node is null.
  

  if (node == null) return false;

• If you’re at a leaf (left and right null), see if node.val == targetSum.
  

  if (node.left == null && node.right == null)
      return node.val == targetSum;

• Otherwise, call recursively on left and right (each with target reduced by node.val), and return true if either works.
  

  return hasPathSum(node.left, targetSum - node.val)
      || hasPathSum(node.right, targetSum - node.val);

💻 The Code

// If you get this right in an interview, celebrate in public.
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    return hasPathSum(root.left, targetSum - root.val) ||
           hasPathSum(root.right, targetSum - root.val);
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Null trees: Don’t try to be a hero—check for root == null first.
• Leaf confusion: Remember: true leaf = both left and right are null, not just one.
• Negative values: Problem doesn’t say positive only. Some nodes are saboteurs and reduce your sum. Handle negatives!
• Efficiency: O(n) time, O(tree height) space for recursion. That’s as good as it gets unless you want to be “clever” and iterative for fun.

🧠 Interviewer Brain-Tattoo

DFS, subtract as you traverse, check leaves only. If you can solve this with recursion, you’re officially smarter than an enterprise framework.