Maximum Level Sum of a Binary Tree
Problem
Given the root of a binary tree, return the level (1-indexed) with the maximum sum of node values. If multiple levels have the same maximum sum, return the smallest level number.
- The number of nodes in the tree is in the range [1, 10⁴]
- −10⁵ ≤ Node.val ≤ 10⁵
Example
root = [1,7,0,7,-8,null,null]2The tree levels are: Level 1: [1], sum = 1 Level 2: [7, 0], sum = 7 Level 3: [7, -8], sum = -1 The maximum sum is 7 at level 2, so the output is 2. A brute-force approach might traverse the tree multiple times to compute sums per level, which is inefficient. Instead, a BFS traversal processes nodes level-by-level, accumulating sums in a single pass. The critical insight is that BFS naturally partitions nodes by level, enabling simultaneous sum calculation and comparison.
Approach
Straightforward Solution
A naive solution might perform a DFS to collect nodes per level and then compute sums, requiring extra space and multiple passes. Alternatively, BFS with a queue allows processing each level in a single pass, reducing complexity.
Core Observation
A binary tree can be traversed level-by-level using BFS, which naturally groups nodes by their depth. Summing node values at each level and tracking the maximum sum is straightforward with this approach.
Path to Optimal
PreviewRecognizing that BFS inherently processes nodes in level order allows summing values as nodes are dequeued per level…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a queue initialized with the root node. For each level, iterate over all nodes currently in the queue, summing their values and enqueueing their children…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each node is enqueued and dequeued exactly once during BFS, resulting in linear time proportional to the number of nodes.
Space
O(w)
The queue stores at most the maximum number of nodes at any level (the tree's maximum width), which can be up to O(n) in the worst case but typically less.
Pattern Spotlight
BFS (Level-Order Traversal with Aggregation)
When a problem requires processing or aggregating nodes by their depth in a tree, BFS naturally partitions nodes level-by-level, enabling efficient single-pass computations per level.
Solution
| 1 | from collections import deque |
| 2 | |
| 3 | class Solution: |
| 4 | def maxLevelSum(self, root: Optional[TreeNode]) -> int: |
| 5 | queue = deque([root]) |
| 6 | level = 1 |
| 7 | |
| 8 | best_level = 1 |
| 9 | best_sum = float("-inf") |
| 10 | |
| 11 | while queue: |
| 12 | level_sum = 0 |
| 13 | |
| 14 | for _ in range(len(queue)): |
| 15 | node = queue.popleft() |
| 16 | level_sum += node.val |
| 17 | |
| 18 | if node.left: |
| 19 | queue.append(node.left) |
| 20 | |
| 21 | if node.right: |
| 22 | queue.append(node.right) |
| 23 | |
| 24 | if level_sum > best_sum: |
| 25 | best_sum = level_sum |
| 26 | best_level = level |
| 27 | |
| 28 | level += 1 |
| 29 | |
| 30 | return best_level |
Step-by-Step Solution
Initialize BFS Queue and Tracking Variables
| 5 | queue = deque([root]) |
| 6 | level = 1 |
| 8 | best_level = 1 |
| 9 | best_sum = float("-inf") |
Objective
To set up the queue with the root node and initialize variables to track the current level and the best level with maximum sum.
Key Insight
Starting the queue with the root node establishes the BFS frontier. Initializing the level counter at 1 aligns with the problem's 1-indexed level numbering. Setting the best sum to negative infinity ensures any level sum will update it, handling negative values correctly.
Interview Quick-Check
Core Logic
Initializing the queue with the root node sets the stage for level-order traversal.
State & Boundaries
Level numbering starts at 1 to match problem requirements.
Common Pitfalls & Bugs
Setting best_sum to negative infinity handles trees with negative node values correctly.
Traverse Tree Level-by-Level and Aggregate Sums
To process each level's nodes, sum their values, enqueue their children, and update the maximum sum and corresponding level.
Return the Level with the Maximum Sum
To output the level number that has the maximum sum after completing the BFS traversal.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 1 Critical line interviewers watch for.
if level_sum > best_sum:Compare the current level sum to the best sum found so far.
This conditional identifies if the current level has a strictly greater sum, which is necessary to update the best level.
Full line-by-line criticality + rationale for all 18 lines available on Pro.
Test Your Understanding
Why does BFS guarantee that nodes are processed level-by-level, enabling correct aggregation of sums per level?
See the answer with Pro.
Related Problems
BFS pattern
Don't just read it. Drill it.
Reconstruct Maximum Level Sum of a Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Maximum Level Sum of a Binary Tree drill