Level Order Sum / Averages
Sum every level with BFS and return the smallest level with the largest sum.
Examples
Level 1 sums to 1, level 2 to 7, level 3 to -1.
Level sums are 989, 10250, 9305 and -32127.
Problem Understanding
Given the root of a binary tree, the root is on level 1, its children on level 2, and so on (LeetCode 1161).
- Goal: Return the smallest level whose values add up to the largest sum.
- Example:
[1, 7, 0, 7, -8]has level sums 1, 7 and -1, so the answer is level 2.
The same loop answers the other per-level questions — averages, maximums — by changing only what is accumulated.
Algorithm Strategy
Use level-order BFS.
- Start:
best_sumat negative infinity,best_level = 1,level = 1, and the root in the queue. - One level per pass: set
level_sum = 0, readsize, then dequeue exactlysizenodes, adding each value and enqueueing its children. - Compare: after the inner loop, replace the best only if
level_sum > best_sum. A tie keeps the earlier level, which is the smallest one — exactly what the problem asks for. - Advance:
level += 1, and repeat until the queue is empty. Returnbest_level.
Interactive Visualization
The level being summed is outlined as it waits in the queue and turns green as each value is added. After every level the sum is compared with the best so far — try the Tie preset, where two levels sum to the same value and the earlier one is kept.
Dry Run
Tree: [1, 7, 0, 7, -8] — root 1; children 7 and 0; 7 has children 7 and -8.
| Level | Nodes | Sum Calculation | Action |
|---|---|---|---|
| 1 | [1] |
sum = 1 |
Max Sum so far: 1 (Level 1). |
| 2 | [7, 0] |
sum = 7 + 0 = 7 |
Max Sum: 7 (Level 2). |
| 3 | [7, -8] |
sum = 7 + (-8) = -1 |
Max Sum: 7 (Level 2). |
Result: Level 2 has the Maximum Sum.
Edge Cases & Common Mistakes
Edge Cases:
- Ties: Use a strict
>. Replacing on>=would return the deepest of the tied levels, not the smallest. - All-negative levels: Starting
best_sumat 0 would never be beaten by a negative level. Start at negative infinity (Long.MIN_VALUE,LLONG_MIN). - Large sums: LeetCode allows up to 10,000 nodes with values up to 100,000 in size, so a level sum stays within ±10^9 and fits in 32 bits. The Java, C++ and C code keeps sums in 64-bit integers anyway, so
best_sumcan start below every possible level sum.
Common Mistakes:
- Setting
level_sum = 0once before the loop instead of at the start of every level, which turns it into one running total for the whole tree. - Numbering levels from 0 — LeetCode counts the root as level 1.
Solution Code
Finding the Level with Maximum Sum.
Level Order Sum / Averages Code
1var maxLevelSum = function(root) {2 let bestSum = -Infinity;3 let bestLevel = 1;4 let level = 1;5 const queue = [root];6 let head = 0;7 while (head < queue.length) {8 let levelSum = 0;9 const size = queue.length - head;10 for (let i = 0; i < size; i++) {11 const node = queue[head++];12 levelSum += node.val;13 if (node.left) {14 queue.push(node.left);15 }16 if (node.right) {17 queue.push(node.right);18 }19 }20 if (levelSum > bestSum) {21 bestSum = levelSum;22 bestLevel = level;23 }24 level++;25 }26 return bestLevel;27};