Maximum Level Sum of a Binary Tree — Solution

Problem

Given a binary tree, find the 1-indexed level whose nodes' values add up to the largest sum. If two levels tie, return the smaller level number.

[1,7,0,7,-8]

• Input: root = [1, 7, 0, 7, -8]
• Output: 2
• Explanation: Level 1 sums to 1, level 2 sums to 7, level 3 sums to −1; level 2 wins.

For ties, the smaller level number wins. In the tree below, levels 1 and 2 both sum to 7 (root=7, children 3+4=7) — the answer is 1.

[7,3,4,1]

Intuition

Level-order (BFS) traversal naturally groups nodes by depth. The only challenge is that node values can be negative, so any level's sum could be negative — you cannot skip a level or assume a positive baseline. Track the running maximum across levels and record which level produced it, breaking ties in favor of the earlier level.

Solution — BFS Level-Order Traversal

Process the tree one level at a time using a queue. For each level, snapshot the queue size before the inner loop so you know exactly how many nodes belong to the current level, then sum their values and update the running maximum.

1. Initialize a queue with the root, set max_sum = -∞ and max_level = 1.
2. While the queue is non-empty, increment the level counter and snapshot level_size = len(queue).
3. Pop exactly level_size nodes; accumulate their values into level_sum and enqueue their non-null children.
4. If level_sum > max_sum, update max_sum and record max_level (strict > ensures ties keep the earlier level).
5. Return max_level after the queue empties.

1from collections import deque
2
3def maxLevelSum(root):
4    max_sum = float('-inf')
5    max_level = 1
6    current_level = 0
7
8    queue = deque([root])
9    while queue:
10        current_level += 1
11        level_size = len(queue)     # snapshot before inner loop to isolate this level
12        level_sum = 0
13
14        for _ in range(level_size):
15            node = queue.popleft()
16            level_sum += node.val
17            if node.left:
18                queue.append(node.left)
19            if node.right:
20                queue.append(node.right)
21
22        if level_sum > max_sum:     # strict > keeps the first (smallest) level on ties
23            max_sum = level_sum
24            max_level = current_level
25
26    return max_level

Time: O(n) — every node is enqueued and dequeued exactly once.

Space: O(w) where w is the maximum width of the tree; in the worst case (a complete binary tree) the last level holds n/2 nodes, so O(n).

Complexity Summary

Common Mistakes

• Initializing max_sum = 0 — if every node is negative, all level sums are negative and no level would ever update the max, returning a wrong answer.
• Not snapshotting the queue size — without level_size = len(queue) captured before the inner loop, newly enqueued children get processed in the same iteration, silently merging levels.
• Using >= instead of > when updating — >= keeps the last level with the maximum sum rather than the first, violating the tie-breaking rule.
• 0-indexed levels — the problem is 1-indexed; starting current_level at 0 and forgetting to increment before the first check shifts every answer off by one.
• Skipping levels with negative sums — every level must be visited; skipping pessimistic-looking levels can cause you to return a level whose sum was never actually the global maximum.

Related Problems

• Binary Tree Level Order Traversal — the direct foundation; collects all level sums instead of just the maximum
• Binary Tree Zigzag Level Order Traversal — same BFS skeleton, alternates collection direction per level
• Binary Tree Right Side View — same level-order BFS structure, captures only the last node of each level
• Maximum Width of Binary Tree — tracks a width metric per level using the same BFS layering technique
• Path Sum — different traversal (DFS root-to-leaf), but combines tree structure with numeric sum targets