Maximum Level Sum of a Binary Tree: Level-Order BFS Pattern

Given the root of a binary tree, return the smallest level number (1-indexed) such that the sum of all the node values at that level is maximized. Every node has an integer value, and values can be negative. This is LeetCode 1161: Maximum Level Sum of a Binary Tree, and it builds directly on the standard level-order BFS template.

Why this problem matters

Level-order traversal (BFS layer by layer) is one of the most reusable patterns in tree problems. Most BFS tree problems ask you to collect values per level or answer some per-level question. This problem takes it one step further: instead of collecting values, you compute an aggregate (the sum) for each level and track which level produced the best result. Once you can do this for sums, the same structure works for averages, maximums, counts, or any other per-level computation.

The key insight

The core idea is the same level_size = len(queue) snapshot that powers all level-by-level BFS. At the start of each level, you know exactly how many nodes belong to that level because the queue contains only those nodes. You dequeue all of them, sum their values, and compare against your running maximum. If the current sum beats the max, you update both the max and the best level number.

Here is the algorithm step by step:

1. Seed the queue with the root. Set max_sum to negative infinity and best_level to 1.
2. While the queue is not empty, snapshot level_size = len(queue).
3. Dequeue level_size nodes. Sum their values. Enqueue any children.
4. If this level's sum is strictly greater than max_sum, update max_sum and best_level.
5. Increment the current level counter.
6. When the queue is empty, return best_level.

The solution

from collections import deque

def max_level_sum(root):
    queue = deque([root])
    max_sum = float("-inf")
    best_level = 1
    current_level = 1
    while queue:
        level_size = len(queue)
        level_sum = 0
        for _ in range(level_size):
            node = queue.popleft()
            level_sum += node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        if level_sum > max_sum:
            max_sum = level_sum
            best_level = current_level
        current_level += 1
    return best_level

The structure should look familiar if you have seen the basic level-order traversal. The only additions are the level_sum accumulator inside the inner loop and the comparison against max_sum after each level finishes.

• level_sum = 0 resets the accumulator before processing each level.
• The inner for loop drains exactly level_size nodes, adding each node's value to level_sum and pushing children for the next level.
• The if level_sum > max_sum check uses strict greater-than so that ties go to the earlier (smaller) level number. The problem asks for the smallest level with the maximum sum.
• current_level += 1 tracks which level we just finished, using 1-indexed numbering.

Visual walkthrough

Let's trace the algorithm through the tree [1, 7, 0, 7, -8]. Watch how the level sum is computed after each level drains from the queue, and how the best level updates when a new maximum is found.

Notice the rhythm: drain the level, compute the sum, compare to the running max, then move on. Level 2 produced a sum of 7, which beat level 1's sum of 1. Level 3 produced -1, which did not beat 7. The answer is level 2.

Complexity analysis

Time: Every node is enqueued and dequeued exactly once. The sum computation is O(1) per node. Total work is O(n) where n is the number of nodes in the tree.

Space: The queue can hold up to the widest level of the tree. For a balanced binary tree, the bottom level contains roughly n/2 nodes, so the worst case is O(n). For a skewed tree (a single chain), the queue holds at most one node at a time.

The building blocks

1. Level-order BFS with per-level processing

The foundation of this problem is BFS with the queue size snapshot. You process the tree one level at a time by capturing len(queue) before the inner loop:

from collections import deque

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

This template is the same one used in Binary Tree Level Order Traversal, Binary Tree Right Side View, Zigzag Level Order Traversal, and many more. The per-level grouping is what makes it possible to compute aggregates like sums, averages, or level-specific answers.

2. Tracking aggregate across levels

On top of the BFS template, you add a running comparison. After computing each level's aggregate (sum in this case), you compare it against a global best and update if it wins. This "scan and track the best" pattern appears in many problems beyond trees, such as finding the subarray with the maximum sum or the interval with the most overlap.

The combination of these two building blocks, level-by-level BFS and running-best tracking, gives you the complete solution.

Edge cases

• Single node tree: The tree has one level with one node. That level is the answer. The algorithm handles this naturally because level 1's sum beats the initial -inf.
• All negative values: Every level sum is negative. The algorithm still works because max_sum starts at -inf, so the least negative level wins.
• Tie between levels: If two levels have the same sum, the problem asks for the smallest level number. The strict > comparison ensures the first level to achieve the max is kept, and later ties do not overwrite it.
• Left-skewed or right-skewed tree: Each level has exactly one node. The algorithm processes each level normally. There is no special logic needed.

From understanding to recall

You just traced through a clean BFS solution that computes per-level sums and tracks the best level. The pattern makes sense right now. But will you reconstruct it from memory in a week when you face a variation like "find the level with the maximum average" or "return the deepest level with an even sum"?

Understanding a solution and being able to reproduce it under pressure are different skills. Spaced repetition bridges that gap. You practice writing the level-by-level BFS template from memory at increasing intervals, first after one day, then three days, then a week. Each repetition reinforces the queue snapshot, the per-level accumulator, and the running-best comparison until the entire pattern becomes automatic.

This problem combines two building blocks: level-order BFS and running-max tracking. Drilling them separately with spaced repetition means you can recombine them on the fly for any variation, rather than memorizing each problem individually.

Related posts

• Binary Tree Level Order Traversal - The foundational BFS template that this problem extends with per-level sum tracking
• Binary Tree Right Side View - Another level-by-level BFS variation that keeps the last node per level instead of summing
• Binary Tree Zigzag Level Order Traversal - The same BFS template with alternating traversal direction per level

CodeBricks breaks problems like this into reusable building blocks and uses spaced repetition to move them into long-term memory. Instead of grinding hundreds of problems and hoping the patterns stick, you drill the core templates until they become second nature.