The O(n) Club: Deepest Leaves Sum — BFS to the Rescue (Again)

The O(n) Club: Deepest Leaves Sum — BFS to the Rescue (Again)

⚡ TL;DR

Quick summary: Find every leaf node chilling at the bottom of the tree and add up their values. Hint: Don’t waste your life with two traversals. BFS sums the right level by simply being last—the Michael Scott of tree traversals.

// Java: single pass BFS, simple as a coffee refill
public int deepestLeavesSum(TreeNode root) {
    Queue
<treenode> queue = new LinkedList<>();
    queue.add(root);
    int sum = 0;
    while (!queue.isEmpty()) {
        sum = 0;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            sum += node.val;
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
    }
    return sum;
}
</treenode>

🧠 How Devs Usually Mess This Up

Let me guess your first attempt: You “ingeniously” traverse for max depth, trek through again to sum up leaves at that level, and wonder why you’re out of time at interviews.
Or you count all nodes at the last level, assuming they’re leaves because your trees are always perfect, just like in fairy tales. Maybe you overengineer it with DFS-wrapped-in-maps, or lose sleep over whether the root is depth 0, 1, or the meaning of life. Cue dramatic sigh.

🔍 What’s Actually Going On

Imagine a company org chart: you want the total salaries of the new hires, not the CEO’s. BFS invites everyone level by level; when HR finally gets to the real interns (the literal bottom), that’s when you sum. And only then. The trick: reset your sum every floor you visit so the last one to leave wins. You’ll need fewer sticky notes and less existential dread.

🛠️ PseudoCode

• Add the root to your friendly queue.
  

  Queue<treenode> queue = new LinkedList<>();
  queue.add(root);</treenode>

• While queue isn’t empty, process one tree level per lap. (No marathons, I promise.)
  

  while (!queue.isEmpty()) {
      // ...levels ahead
  }

• Start each new level with sum = 0. Forget the old sum; we’re living in the now.
  

  sum = 0;

• Process each node at this level: queue size tells you how many to do.
  

  int size = queue.size();
  for (int i = 0; i < size; i++) {
      // ...dequeue, add kids
  }

• Add current node’s value to sum. (Those leaves aren’t going to sum themselves.)
  

  TreeNode node = queue.poll();
  sum += node.val;

• Queue up each child for the next level’s reckoning.
  

  if (node.left != null) queue.add(node.left);
  if (node.right != null) queue.add(node.right);

• When the loop is over, the last sum you calculated is the deepest leaves sum. Interviewer sighs with relief.

💻 The Code

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 public class Solution {
    public int deepestLeavesSum(TreeNode root) {
        Queue
<treenode> queue = new LinkedList<>();
        queue.add(root);
        int sum = 0;
        while (!queue.isEmpty()) {
            sum = 0;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return sum;
    }
}
</treenode>

⚠️ Pitfalls, Traps & Runtime Smacks

• Root Only? If the root is alone, it’s also the deepest leaf. Don’t let your code be a loner hater.
• Last Level ≠ All Leaves: In wild trees (read: the real world), not every node at the bottom is a leaf. Luckily, BFS still works since the queue at last level only contains nodes that exist, leaf or not.
• Unbalanced Trees: If your deepest leaves are all on the left or right, that’s fine. Don’t get symmetric anxiety.
• Queue Space: Worst case, your queue is as big as the number of deepest leaves. It’s O(n)—not scary, just something for your mental RAM.
• Edge Counting: Just be consistent (root as depth 0 or 1) and you’ll survive the interview.

🧠 Interviewer Brain-Tattoo

“BFS is like pizza delivery in a tower block—the last floor gets their order last, but they get everything hot and fresh.” 🍕🌳