Deepest Leaves Sum — Last-Level Sum via BFS in O(n)

Problem Statement#

Given the root of a binary tree, return the sum of values of its deepest leaves — the leaves at the maximum depth.

Constraints:

• The number of nodes is in [1, 10^4]
• 1 <= Node.val <= 100

Input:  root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15
Explanation: Deepest leaves are 7 and 8. 7 + 8 = 15.

Input:  root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19

Why This Problem Matters#

LeetCode 1302 "Deepest Leaves Sum" is an Amazon and Oracle staple, often used as a warm-up for level-order traversal. It tests whether you reach for BFS the moment you hear "deepest level" — a strong signal of pattern recognition during interviews.

It is also a good example of how the same answer can come from BFS or DFS, and choosing BFS leaves an obvious O(w) space footprint that scales with width rather than height.

The Core Insight#

In a level-order BFS, each iteration of the outer while-loop processes exactly one level. After draining the queue at the end, the last fully processed level is the deepest. Reset the running sum at the start of every level so that when the loop exits, the sum holds only the deepest level's contribution.

DFS works too: track the maximum depth and a running sum keyed on depth. Whenever you discover a new deeper level, reset the sum.

Visual Dry Run#

Tree [1,2,3,4,5,null,6,7,null,null,null,null,8]:

After loop: level_sum = 15. Return 15.

Solution (Optimal)#

class Solution:
    def deepestLeavesSum(self, root):
        from collections import deque
        queue = deque([root])
        level_sum = 0
        while queue:
            level_sum = 0
            for _ in range(len(queue)):
                node = queue.popleft()
                level_sum += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return level_sum

var deepestLeavesSum = function(root) {
    let queue = [root];
    let levelSum = 0;
    while (queue.length) {
        levelSum = 0;
        const nextQueue = [];
        for (const node of queue) {
            levelSum += node.val;
            if (node.left) nextQueue.push(node.left);
            if (node.right) nextQueue.push(node.right);
        }
        queue = nextQueue;
    }
    return levelSum;
};

Time: O(n) — every node is visited and summed exactly once. Space: O(w) — width of the deepest level dominates the queue size.

Common Mistakes#

• Accumulating across all levels instead of resetting level_sum at the start of each iteration.
• Tracking maximum depth via DFS but failing to reset the running sum when a deeper level is found.
• Using queue.shift() in JavaScript inside an inner loop — O(n) per call. Use index pointer or two-array swap.
• Confusing "deepest leaves" with "all leaves" — only the deepest count.
• Forgetting the empty-root edge case (constraints rule it out, but still worth a guard).

Interview Tips#

• Reach for BFS immediately when you hear "deepest" or "last level".
• Mention the DFS alternative — interviewers may ask why BFS is more natural here.
• Discuss the trade-off: BFS uses O(w) space; DFS uses O(h). Worst case both are O(n).
• For wide trees, BFS may be heavier; for skewed trees, DFS recursion may overflow.

Follow-up Questions#

• Sum at any depth k: generalize the function to return sum at depth k. Hint: BFS until depth k.
• Deepest leaves count: return the number of deepest leaves instead of the sum. Hint: replace += with += 1.
• DFS solution: write the post-order DFS variant. Hint: track (depth, sum) tuples.
• Average at deepest level: return the average value. Hint: track sum and count.
• Online tree: process nodes one at a time; cannot revisit. Hint: maintain rolling deepest sum.

Key Takeaways#

• LeetCode 1302 is a textbook BFS level-order problem.
• Reset level_sum at the start of each level so the loop's final value is the deepest level.
• DFS works with (depth, sum) tracking but is slightly less natural here.
• O(n) time, O(w) space for BFS; O(h) space for DFS.
• "Deepest leaves" = leaves at the maximum depth, not all leaves.
• Easy/Medium tier — a common phone-screen warm-up at Amazon and Oracle.
• Pattern recognition: hearing "deepest level" should trigger BFS.