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:
[1, 104].-105 <= Node.val <= 105In #1161 Maximum Level Sum of a Binary Tree, the goal is to determine which level of a binary tree has the highest sum of node values. The most intuitive strategy is Breadth-First Search (BFS), which naturally processes nodes level by level. Using a queue, you can iterate through each level, calculate the sum of its nodes, and track the level with the maximum value.
Another effective method uses Depth-First Search (DFS). During recursion, you track the current depth and accumulate sums for each level using a list or hash map. After the traversal, you simply identify the level with the highest recorded sum.
BFS is often preferred because it directly mirrors the level-order structure of the problem. Both approaches visit each node exactly once, making them efficient for large trees.
Time Complexity: O(n) since every node is processed once. Space Complexity: O(n) due to the queue in BFS or recursion stack and level storage in DFS.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search (Level Order Traversal) | O(n) | O(n) |
| Depth-First Search with Level Tracking | O(n) | O(n) |
codestorywithMIK
Use these hints if you're stuck. Try solving on your own first.
Calculate the sum for each level then find the level with the maximum sum.
How can you traverse the tree ?
How can you sum up the values for every level ?
Use DFS or BFS to traverse the tree keeping the level of each node, and sum up those values with a map or a frequency array.
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.
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.
1import java.util.LinkedList;
2import java.util.Queue;
3
4// Definition for a binary tree node.
5class TreeNode {
6
The Java solution employs a Queue to perform breadth-first search (BFS) on the tree. Each loop iteration computes the sum of node values at the current level and updates the maximum sum and the corresponding level whenever a higher sum is found.
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.
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).
1from collections import defaultdict
2
3# Definition for a binary tree node.
4class TreeNode
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Depth-First Search can also solve this problem by tracking the depth during recursion. You store cumulative sums for each level in an array or map, and after traversal, determine which level has the maximum sum.
Yes, tree traversal problems like this are common in FAANG-style interviews. They test understanding of BFS, DFS, and how to manage level-based computations within binary trees.
A queue is typically used for the BFS approach because it supports level-order traversal. For the DFS approach, a list or hash map is useful for storing sums associated with each tree level.
The most common approach is Breadth-First Search (BFS) using a queue to process nodes level by level. For each level, you compute the sum of node values and keep track of the maximum sum encountered. This approach naturally fits the level-based requirement of the problem.
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.