Maximum Level Sum of a Binary Tree - Solution & Explanation
Problem Statement
Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.
Return the smallest level x such that the sum of all the values of nodes at level x is maximal.
Example 1:
Input: root = [1,7,0,7,-8,null,null] Output: 2 Explanation: Level 1 sum = 1. Level 2 sum = 7 + 0 = 7. Level 3 sum = 7 + -8 = -1. So we return the level with the maximum sum which is level 2.
Example 2:
Input: root = [989,null,10250,98693,-89388,null,null,null,-32127] Output: 2
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -105 <= Node.val <= 105
Approach Overview
Problem Overview: You’re given the root of a binary tree. Each level contains several nodes, and each node has an integer value. The task is to compute the sum of values at every level and return the level index (1-indexed) that has the maximum sum.
The key observation: nodes on the same depth belong to the same level. If you process the tree level by level, you can compute the sum for each level and track the maximum as you go.
Approach 1: Breadth-First Search (Level Order Traversal) (Time: O(n), Space: O(w))
This approach uses Breadth-First Search to traverse the binary tree level by level. Start by pushing the root node into a queue. For each iteration, process all nodes currently in the queue (which represent one level). Sum their values, enqueue their left and right children, and compare the level sum with the current maximum.
The queue naturally separates nodes by level because children are added only after their parent level is processed. Maintain variables for currentLevel, maxSum, and resultLevel. Whenever a level sum exceeds maxSum, update the answer. This approach is straightforward and matches how most interviewers expect you to handle level-based tree problems.
Time complexity is O(n) since each node is processed exactly once. Space complexity is O(w), where w is the maximum width of the tree, due to the queue storing nodes of the current level.
Approach 2: Depth-First Search with Level Tracking (Time: O(n), Space: O(h))
A recursive solution using Depth-First Search also works. Instead of processing by levels explicitly, DFS tracks the current depth while traversing the tree. Maintain a dynamic array where index i stores the cumulative sum for level i. During recursion, add the node’s value to the corresponding level entry.
If the DFS reaches a depth that hasn’t been seen before, append a new element to the array. After the traversal completes, scan the array to find the level with the maximum sum. This approach separates traversal from result evaluation and works well in recursive implementations.
Time complexity remains O(n) because every node is visited once. Space complexity is O(h) for recursion stack depth (where h is tree height) plus O(L) for storing level sums.
Recommended for interviews: The BFS level-order traversal is typically the expected solution. The problem explicitly revolves around levels, so using a queue to process nodes level by level demonstrates a clear understanding of tree traversal patterns. The DFS approach is still valid and shows flexibility, but BFS is usually the first method interviewers want to see.
Approach 1: Breadth-First Search (BFS) Approach
The BFS approach is well-suited for problems involving levels of a binary tree. We will use a queue to process the tree level by level, keeping track of the sum of node values at each level. We will maintain a variable to store the maximum sum encountered and the level corresponding to this maximum sum. By processing level by level, we ensure that when we find a new maximum, it is the smallest level with that sum.
This implementation uses a queue to traverse the binary tree level by level. For each level, we calculate the sum of its node values. If this sum is greater than the previously recorded maximum sum, we update the maximum sum and note the level number. The queue helps ensure that each node of a given level is processed before nodes of the next level, which is key to implementing BFS.
Complexity
Time Complexity: O(n), where n is the number of nodes in the tree, because each node is enqueued and dequeued exactly once.
Space Complexity: O(m), where m is the maximum number of nodes at any level in the tree, due to the queue holding nodes of a single level.
Approach 2: Depth-First Search (DFS) with Level Tracking
This approach involves using a DFS traversal to explore the tree. We pass the current depth as a parameter to each recursive call and maintain an array or dictionary to track the sum of values at each level. After the traversal, we determine which level has the highest sum. DFS allows us to explore the tree deeply, and since each call carries a depth count, we can easily track levels.
The Python solution uses DFS by recursively traversing the tree and tracking the sum of node values at each level using a dictionary. After completing the traversal, it identifies the level with the maximum sum.
Code
Python
Complexity
Time Complexity: O(n)
Space Complexity: O(d), where d is the maximum depth of the tree (related to recursion stack depth and level count in the dictionary).
Approach 3: BFS
We use BFS to traverse level by level, calculating the sum of nodes at each level, and find the level with the maximum sum. If there are multiple levels with the maximum sum, return the smallest level number.
Specifically, we use a queue q to store the nodes of the current level. During each traversal, we record the sum of nodes at the current level as s, then add all child nodes of the current level to the queue to prepare for the next level. We use variable mx to record the current maximum sum, and variable ans to record the corresponding level number. After calculating the sum of each level, if s is greater than mx, we update mx and ans. Finally, we return ans.
The time complexity is O(n) and the space complexity is O(n), where n is the number of nodes in the binary tree.
Approach 4: DFS
We can also use DFS to solve this problem. We use an array s to store the sum of nodes at each level. The index of the array represents the level, and the value of the array represents the sum of nodes. We use DFS to traverse the binary tree, adding the value of each node to the sum of nodes at the corresponding level. Finally, we return the index corresponding to the maximum value in s.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(n), where n is the number of nodes in the tree, because each node is enqueued and dequeued exactly once. |
| Depth-First Search (DFS) with Level Tracking | Time Complexity: O(n) |
| BFS | — |
| DFS | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (Level Order) | O(n) | O(w) | Best for problems involving level-by-level processing of a binary tree |
| Depth-First Search with Level Tracking | O(n) | O(h) + O(L) | Useful when implementing recursive traversal or when tracking level data during DFS |
Video Solution
Maximum Level Sum of a Binary Tree | Leetcode 1161 | AMAZON | codestorywithMIK • codestorywithMIK • 11,981 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Level Sum of a Binary Tree easy or hard?
Maximum Level Sum of a Binary Tree Python/Java solution
How to solve Maximum Level Sum of a Binary Tree in O(n)?
What is the best approach for Maximum Level Sum of a Binary Tree?
Is Maximum Level Sum of a Binary Tree asked at Google/Amazon/Meta?
What data structure is used in Maximum Level Sum of a Binary Tree?
What is the time complexity of Maximum Level Sum of a Binary Tree?
Ready to solve this problem?
Practice Maximum Level Sum of a Binary Tree with our built-in code editor and test cases.
Practice on FleetCode