Maximum Level Sum of a Binary Tree

Med

#1090Time: O(N), where N is the number of nodes in the tree. The DFS traversal takes O(N) time as it visits each node once. The subsequent loop to find the maximum sum takes O(H) time, where H is the height of the tree. Thus, the total time is O(N + H), which simplifies to O(N).Space: O(H), where H is the height of the tree. This space is used by the recursion stack and the `levelSums` list, both of which can grow up to the height of the tree. In the worst case of a skewed tree, H can be N, making the space complexity O(N).

Algorithms

Depth-First Search Breadth-First Search

Data structures

Tree Binary Tree

Prompt

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, 10⁴].
-10⁵ <= Node.val <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a recursive Depth-First Search traversal to visit every node. We pass the current level as an argument in the recursive calls. A list is used to store the sum of node values for each level. After the traversal is complete, we iterate through this list to find the level with the maximum sum.

Algorithm

Initialize an empty list, levelSums, to store the sum of nodes for each level.
Define a recursive helper function dfs(node, level).
In dfs(node, level):
- Base case: If node is null, return.
- If level is greater than the current size of levelSums, add node.val as a new entry.
- Otherwise, update the sum at index level - 1 by adding node.val.
- Recursively call dfs for the left child with level + 1.
- Recursively call dfs for the right child with level + 1.
Start the traversal by calling dfs(root, 1).
After the traversal, iterate through levelSums to find the maximum sum.
Keep track of the index i where the maximum sum is found. The first such index will correspond to the smallest level.
Return i + 1 as the result.

Walkthrough

This approach utilizes a Depth-First Search (DFS) traversal to compute the sum of nodes at each level. We use a recursive helper function that takes the current node and its level as arguments. An external data structure, like an ArrayList, is used to store the sum for each level. The index of the list corresponds to the level number (minus one). As the DFS traversal explores the tree, it populates this list with the sums. Once the traversal is complete, we perform a second pass over the list of sums to identify the maximum sum and the smallest level at which it occurs.

Here is the Java implementation:

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    private List<Integer> levelSums = new ArrayList<>();18 19    public int maxLevelSum(TreeNode root) {20        dfs(root, 1);21 22        int maxSum = Integer.MIN_VALUE;23        int maxLevel = 0;24 25        for (int i = 0; i < levelSums.size(); i++) {26            if (levelSums.get(i) > maxSum) {27                maxSum = levelSums.get(i);28                maxLevel = i + 1;29            }30        }31        return maxLevel;32    }33 34    private void dfs(TreeNode node, int level) {35        if (node == null) {36            return;37        }38        if (level > levelSums.size()) {39            levelSums.add(node.val);40        } else {41            levelSums.set(level - 1, levelSums.get(level - 1) + node.val);42        }43        dfs(node.left, level + 1);44        dfs(node.right, level + 1);45    }46}

Complexity

Time

O(N), where N is the number of nodes in the tree. The DFS traversal takes O(N) time as it visits each node once. The subsequent loop to find the maximum sum takes O(H) time, where H is the height of the tree. Thus, the total time is O(N + H), which simplifies to O(N).

Space

O(H), where H is the height of the tree. This space is used by the recursion stack and the `levelSums` list, both of which can grow up to the height of the tree. In the worst case of a skewed tree, H can be N, making the space complexity O(N).

Trade-offs

Pros

Conceptually simple if you are very familiar with DFS and recursion.

Cons

Requires two passes over the data: one to traverse the tree and populate the sums, and a second to iterate through the sums to find the maximum.
Less intuitive for a level-by-level problem compared to BFS.
Space complexity can be O(N) for skewed trees, which is worse than BFS for that specific case.

This approach uses Breadth-First Search (BFS), which is the natural way to traverse a tree level by level. We use a queue to process nodes. In each iteration of the main loop, we process all nodes of a single level, calculate their sum, and compare it with the maximum sum found so far.

Algorithm

Handle the edge case where the root is null.
Initialize a Queue and add the root node.
Initialize variables: maxSum to a very small number, resultLevel = 1, and currentLevel = 1.
Begin a loop that continues as long as the queue is not empty.
Inside the loop, first determine the number of nodes at the current level by getting the queue's size (levelSize).
Initialize currentLevelSum = 0.
Start an inner loop that runs levelSize times to process all nodes of the current level:
- Dequeue a node from the queue.
- Add the node's value to currentLevelSum.
- Enqueue the node's non-null left and right children.
After the inner loop, compare currentLevelSum with maxSum. If it's greater, update maxSum and set resultLevel to currentLevel.
Increment currentLevel for the next iteration.
After the main loop finishes, return resultLevel.

Walkthrough

This approach uses Breadth-First Search (BFS), which is a natural fit for problems involving tree levels. By using a queue, we can process the tree one level at a time. We iterate through the levels, and for each level, we calculate the sum of its node values. We maintain a variable to track the maximum sum seen so far and the level at which it occurred. Since we process levels in increasing order (1, 2, 3, ...), the first time we find a maximum sum, we record its level. Any subsequent levels with the same maximum sum will be ignored, automatically satisfying the condition to return the smallest level. This method efficiently finds the result in a single pass over the tree.

Here is the Java implementation:

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public int maxLevelSum(TreeNode root) {18        if (root == null) {19            return 0;20        }21 22        Queue<TreeNode> queue = new LinkedList<>();23        queue.offer(root);24 25        int maxSum = Integer.MIN_VALUE;26        int resultLevel = 0;27        int currentLevel = 1;28 29        while (!queue.isEmpty()) {30            int levelSize = queue.size();31            int currentLevelSum = 0;32 33            for (int i = 0; i < levelSize; i++) {34                TreeNode node = queue.poll();35                currentLevelSum += node.val;36 37                if (node.left != null) {38                    queue.offer(node.left);39                }40                if (node.right != null) {41                    queue.offer(node.right);42                }43            }44 45            if (currentLevelSum > maxSum) {46                maxSum = currentLevelSum;47                resultLevel = currentLevel;48            }49            currentLevel++;50        }51        return resultLevel;52    }53}

Complexity

Time

O(N), where N is the number of nodes. Each node is enqueued and dequeued exactly once.

Space

O(W), where W is the maximum width of the binary tree. The space is dominated by the queue, which holds at most all nodes of the widest level. In the worst case (a complete binary tree), W can be up to N/2, making the space complexity O(N).

Trade-offs

Pros

Very intuitive for a level-order problem.
Calculates the sum and finds the maximum in a single pass.
Naturally finds the smallest level in case of ties because levels are processed in order.
More space-efficient than DFS for tall, skinny trees.

Cons

Can be less space-efficient than DFS for short, wide trees (e.g., complete binary trees where space is O(N) vs DFS's O(log N)).

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int maxLevelSum ( TreeNode root ) { Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); int mx = Integer . MIN_VALUE ; int i = 0 ; int ans = 0 ; while (! q . isEmpty ()) { ++ i ; int s = 0 ; for ( int n = q . size (); n > 0 ; -- n ) { TreeNode node = q . pollFirst (); s += node . val ; if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } if ( mx < s ) { mx = s ; ans = i ; } } return ans ; } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxLevelSum ( TreeNode * root ) { queue < TreeNode *> q { { root } }; int mx = INT_MIN ; int ans = 0 ; int i = 0 ; while ( ! q . empty ()) { ++ i ; int s = 0 ; for ( int n = q . size (); n ; -- n ) { root = q . front (); q . pop (); s += root -> val ; if ( root -> left ) q . push ( root -> left ); if ( root -> right ) q . push ( root -> right ); } if ( mx < s ) mx = s , ans = i ; } return ans ; } };

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def maxLevelSum ( self , root : Optional [ TreeNode ]) -> int : q = deque ([ root ]) mx = - inf i = 0 while q : i += 1 s = 0 for _ in range ( len ( q )): node = q . popleft () s += node . val if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) if mx < s : mx = s ans = i return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem