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
The question is about levels, so process the tree one level at a time. A breadth-first traversal that drains the queue in batches gives you each level in isolation — sum the batch, compare against the best, and keep the earlier level on a tie.
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).
Level-by-level batching
Plain BFS visits nodes in level order but blurs the boundaries between levels. The fix is to record the queue's size before processing: that count is exactly how many nodes are on the current level. Pop precisely that many, summing as you go and enqueueing their children. When the batch is exhausted the queue holds exactly the next level, and the process repeats. This snapshot-the-size idiom is the core of every level-aware BFS.
Tracking the best level
Keep best_sum and best_level. After summing a level, replace them only when the new sum is strictly greater. Using a strict comparison is what implements the tie-breaking rule — an equal sum on a deeper level leaves the earlier one in place, which is what the problem asks for. Levels are 1-indexed, so start the counter at 1 rather than 0.
Why negatives forbid a zero start
Node values may be negative, so a level's sum can be below zero and the maximum sum may itself be negative. Initialising best_sum to 0 would then never be beaten and the answer would default to whatever level was seeded. Start from negative infinity — or seed with the first level's actual sum — so every level is genuinely compared. Time is O(n) with 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.