Maximum Level Sum of a Binary Tree
Maximum Level Sum of a Binary Tree: return the 1-indexed level whose node values sum to the maximum. If several levels tie, return the smallest such level.
- The number of nodes is in the range [1, 10⁴].
- -10⁵ <= Node.val <= 10⁵
Intuition
Maximum level sum of a binary tree returns the level with the largest sum of values, where the root is level 1. When levels tie, the smallest level number wins.
Summing by level is naturally a BFS, since the traversal already visits nodes level by level:
- Snapshot the queue size before each round — that count is exactly the number of nodes on the current level, so one round processes one level.
Without that snapshot, nodes enqueued during the round are absorbed into it and the level boundaries blur, mixing sums from adjacent levels.
Each round sums the values it dequeues, enqueues the children, then compares that sum against the best seen.
The tie-breaking rule dictates the comparison. Update the answer only on a strictly greater sum:
Using >= would let a later level with an equal sum overwrite an earlier one, returning the larger level number when the smaller is required. Since BFS visits levels in increasing order, strict comparison keeps the first — and therefore smallest — level automatically.
Values can be negative, so the running maximum must start at negative infinity rather than zero. A tree of all-negative values would otherwise report a level sum that never occurred.
A DFS also works, carrying the depth and accumulating into a per-level array or map. It is equally correct, though the level ordering must then be reconstructed rather than coming free from the traversal.
Every node is visited once, giving O(n) time and O(w) space for the queue, where w is the widest level.
Any question phrased per level — maximum, average, rightmost, zigzag order — is level-order BFS with the queue drained in batches. Snapshotting len(queue) before the inner loop is the reusable idiom that turns flat BFS into level-aware BFS.
Approach
Before reading on: in a plain BFS queue, how would you know where one level ends and the next begins? And what should the initial best sum be when values can be negative? Aim for O(n).
Traverse level by level
BFS already visits nodes in level order, which is exactly the grouping the problem asks about.
Snapshot the queue size
Record the queue length before each round — that count is the current level's node count. Without it, newly enqueued children blur the level boundaries.
Sum each level
Add the values dequeued during the round, enqueueing children as you go. The round's total is that level's sum.
Compare strictly
Update only on a strictly greater sum. Using >= lets a later equal level overwrite an earlier one, returning the wrong level number on ties.
Initialise to negative infinity
Values can be negative, so starting the maximum at zero would report a level sum that never occurred on an all-negative tree.
Cost of the traversal
Every node is visited once, giving O(n) time and O(w) space for the queue, where w is the widest level.
Solution & live demo
Common pitfalls
Initialising the best sum to zero
best_sum = 0
best_sum = float('-inf')Values can be negative, so every level might sum below zero and none would ever beat the initial 0 — the function returns the seeded level regardless of the tree.
Not snapshotting the queue length
for _ in range(len(queue)):
node = queue.popleft()
queue.append(node.left) # length changes mid-looplevel_size = len(queue) for _ in range(level_size):
In Python range(len(queue)) is evaluated once so it happens to work, but in C++ or Java re-reading queue.size() inside the condition lets children join the same batch and levels merge. Snapshot it explicitly.
Using >= for the comparison
if total >= best_sum:
if total > best_sum:
The problem asks for the smallest level among ties. With >= a later level of equal sum overwrites the earlier one and the wrong level is reported.
Edge cases
One level with one sum; the answer is level 1.
The maximum sum is negative, which is why the initial best must not be 0.
The strict > comparison keeps the earlier level, as specified.
Every level holds one node; the queue never exceeds size 1.
The loop runs to the end, so a late maximum is still found.