Deepest Leaves Sum: BFS Level-by-Level Traversal

Given the root of a binary tree, return the sum of values of its deepest leaves. A leaf is a node with no children, and the deepest leaves are the leaves at the maximum depth of the tree.

This is LeetCode 1302: Deepest Leaves Sum. For example, given a tree where the deepest level contains nodes with values 7 and 8, the answer is 15.

Why this problem matters

This problem is a clean exercise in level-order traversal. You need to identify which level is the deepest and sum only the nodes on that level. It is a natural follow-up to problems like "Maximum Depth of Binary Tree" and "Binary Tree Level Order Traversal," and it reinforces the BFS pattern that appears across dozens of tree and graph problems.

The trick is that you do not need to find the depth first and then traverse again. A single BFS pass handles everything. Each time you start a new level, you reset a running sum. When the queue is finally empty, the last sum you computed belongs to the deepest level. This "process level, reset, repeat" pattern is a building block you will use in many other problems.

Understanding this approach also prepares you for harder variations. Problems like "Maximum Level Sum of a Binary Tree" (LeetCode 1161) and "Binary Tree Zigzag Level Order Traversal" (LeetCode 103) all use the same level-by-level BFS skeleton. Master it here, and those problems become minor modifications.

The key insight

You do not need two passes. You do not need to compute the tree's depth before summing. Instead, run BFS and reset a level_sum variable at the start of every level. Process all nodes at the current level: add their values to level_sum and enqueue their children. When the queue empties, level_sum holds the sum of the last (deepest) level.

The key detail is the for _ in range(len(queue)) loop. This processes exactly the nodes at the current level before moving on. Without it, you would mix nodes from different levels and lose track of which level you are on.

The solution

from collections import deque

def deepest_leaves_sum(root):
    if not root:
        return 0

    queue = deque([root])

    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

Let's walk through the logic.

The function starts by handling the empty tree case. Then it initializes a queue with the root node and enters the BFS loop.

At the top of each iteration, level_sum resets to 0. The inner for loop processes every node at the current level. For each node, it adds the node's value to level_sum and pushes any children into the queue for the next level. When the inner loop finishes, one complete level has been processed.

The outer while loop continues as long as there are nodes in the queue. When it finally exits, no more children were added, meaning the last level processed was the deepest. The value of level_sum at that point is exactly the sum of the deepest leaves.

Visual walkthrough

Let's trace through the example tree level by level. Watch how level_sum resets at each level and holds the final answer when BFS completes.

Notice that we never explicitly track the depth. The BFS structure handles it implicitly. Each iteration of the outer loop is one level, and the last iteration is the deepest level.

Complexity analysis

Time is O(n) where n is the number of nodes in the tree. Every node is visited exactly once: it enters the queue once and is dequeued once. The work per node is O(1), so total time is linear.

Space is O(n) in the worst case. The queue holds at most one full level of the tree at a time. In a complete binary tree, the last level can contain up to n/2 nodes, so the queue can grow to O(n). In a skewed tree (every node has only one child), the queue holds at most 1 node at a time, making space O(1).

The building blocks

1. Level-by-level BFS

The pattern of processing all nodes at one depth before moving to the next:

from collections import deque

def bfs_by_level(root):
    queue = deque([root])
    while queue:
        for _ in range(len(queue)):
            node = queue.popleft()
            process(node)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

This is the foundation for almost every BFS tree problem. "Binary Tree Level Order Traversal," "Binary Tree Right Side View," "Maximum Width of Binary Tree," and this problem all use the same skeleton. The range(len(queue)) snapshot at the start of each level is the key detail. It freezes the count of nodes at the current depth so you process exactly that many before moving on.

2. Accumulate-and-overwrite

The pattern of resetting an accumulator at each level and keeping the final value:

while queue:
    level_sum = 0
    for _ in range(len(queue)):
        node = queue.popleft()
        level_sum += node.val
        enqueue_children(node, queue)
return level_sum

This is a simple but powerful trick. Instead of collecting all levels into a list and then picking the last one, you just overwrite a single variable. It saves space (no list of lists) and simplifies the code. The same idea works for finding the maximum level sum, the average of the last level, or any "last level" aggregate.

Edge cases

Before submitting, think through these scenarios:

• Empty tree: root is None. Return 0.
• Single node: the root itself is the only leaf and the deepest. Return root.val.
• Perfectly balanced tree: all leaves are at the same depth. The sum includes every leaf in the tree.
• Completely skewed tree: every node has only one child, forming a straight line. The single leaf at the bottom is the deepest. Return that leaf's value.
• Multiple leaves at the deepest level with value 0: the sum is 0. Make sure your code does not confuse "sum is zero" with "no leaves found."

From understanding to recall

You now see why BFS level-by-level is the right tool: it naturally groups nodes by depth, and the last group is the deepest leaves. The code is short and the logic is clean. But writing it quickly under pressure requires more than understanding.

The details that matter are small. Where do you reset level_sum? Inside the outer loop, before the inner loop. How do you snapshot the level size? With range(len(queue)) before any popleft calls. What do you return? The value of level_sum after the while loop exits. These are not hard concepts, but they are easy to fumble when you are nervous and on the clock.

Spaced repetition turns this pattern into muscle memory. You write the BFS skeleton, the level reset, and the final return from scratch at increasing intervals. After a few rounds, the code flows out automatically. You see "deepest level" in a problem description, and the template is already in your hands.

Related posts

• Level Order Traversal - The foundational BFS tree traversal that this problem builds on
• Binary Tree Level Order Traversal II - Bottom-up level order, another variation of the same BFS pattern
• Maximum Depth of Binary Tree - Finding tree depth, which is closely related to identifying the deepest level

CodeBricks breaks Deepest Leaves Sum into its level-by-level BFS and accumulate-and-overwrite building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a BFS tree problem shows up in your interview, you do not think about it. You just write it.