The O(n) Club: Sum of Left Leaves — Because Trees Are Funnier Than You Think

The O(n) Club: Sum of Left Leaves — Because Trees Are Funnier Than You Think

⚡ TL;DR

If you can’t tell your left from your right, this is the interview question for you! Sum every left leaf in a binary tree, meaning: a node is only counted if it sits on its parent’s left and has zero kids of its own (basically, the introverts of the tree world). The brute force is just DFS with a side serving of paranoia:

// Java snippet
public int sumOfLeftLeaves(TreeNode root) {
    return sumHelper(root, false);
}
private int sumHelper(TreeNode node, boolean isLeft) {
    if (node == null) return 0;
    if (node.left == null && node.right == null && isLeft) return node.val;
    return sumHelper(node.left, true) + sumHelper(node.right, false);
}

🧠 How Devs Usually Mess This Up

Here’s where careers go sideways: Most devs accidentally tally all left children, then wonder why their test cases do the walk of shame. Remember: left does not mean ‘lonely’. Don’t count left nodes with kids (they’re busy!), don’t count right leaves (they’re not even on the guest list), and never ever give the root node a participation trophy — it’s not anyone’s left child. Also: Handle your nulls, or the tree will handle you.

🔍 What’s Actually Going On

Imagine your family tree. Only those cousins on the leftmost branch, who surprisingly have no offspring, get included in your group chat. Everyone else? Ignored. We traverse every branch (DFS), carry a flag that screams “I’m a lefty!” down the call stack, and every time we hit a node that is both a left child and has no children, we pile it into the sum. For once in life, being left and alone pays off!

🛠️ PseudoCode

• Start Recursion: Call helper on root with isLeft = false.

  sumHelper(root, false);

• Base Case: If node == null, return 0. (Nulls don’t get invited.)

  if (node == null) return 0;

• Left Leaf Jackpot: If current node is a left child and has no kids, add its value!

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

• DFS Both Sides: Recurse left with isLeft = true; right with isLeft = false. Sum their answers.

  return sumHelper(node.left, true) + sumHelper(node.right, false);

💻 The Code

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 public int sumOfLeftLeaves(TreeNode root) {
    return sumHelper(root, false);
}
private int sumHelper(TreeNode node, boolean isLeft) {
    if (node == null) return 0;
    if (isLeft && node.left == null && node.right == null) return node.val;
    return sumHelper(node.left, true) + sumHelper(node.right, false);
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Counting left children who actually have kids — check for leafiness! No +1 for parents.
• Including right leaves (don’t be that person: filter for left only).
• Counting the root — unless your tree is upside down, the root cannot be a left child.
• Forgetting null-checks — the quickest path to NullPointerException land.
• Complexity: O(N) time (look at each node once), O(H) space (stack follows the tree height — so not your monstrous recursion nightmares, unless your tree is flat as the Kansas plains).

🧠 Interviewer Brain-Tattoo

“Not every left child is a left leaf. If only fixing family trees were this easy.”