Maximum Level Sum of a Binary Tree — Problem & Solution
Maximum Level Sum of a Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Level Sum of a Binary Tree is a medium coding problem on breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Breadth-First Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, number its levels from the top: the root is on level 1, its children on level 2, and so on.
Return the level whose node values add up to the largest sum. If several levels share that largest sum, return the smallest such level.
Example 1
Input: root = [1,7,0,7,-8]
Output: 2
Explanation: The level sums are 1, 7 + 0 = 7 and 7 - 8 = -1; level 2 is the largest.
Example 2
Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2
Explanation: The sums are 989, 10250, 98693 - 89388 = 9305 and -32127; level 2 wins.
Example 3
Input: root = [1,2,-1]
Output: 1
Explanation: Levels 1 and 2 both sum to 1; the smaller level number, 1, is returned.
Constraints
1 <= number of nodes <= 10^4-10^5 <= Node.val <= 10^5
Hints for Maximum Level Sum of a Binary Tree
Hint 1
You need one number per level, so visit the tree level by level.
Hint 2
A breadth-first walk that processes exactly the nodes currently in the queue at a time handles one whole level per round.
Hint 3
Keep the best sum and its level; replace them only on a strictly larger sum so ties keep the earlier level. Sums can be negative — do not start the best at 0.
How to solve Maximum Level Sum of a Binary Tree
A breadth-first walk visits the tree one level at a time; sum each level and keep the first level that reaches the maximum.
Approach
- Put the root in a queue and set the level counter to 0.
- While the queue is not empty: increase the level, take exactly the nodes now in the queue, add up their values and enqueue their children.
- If this is the first level or its sum is strictly larger than the best so far, record the sum and the level.
- Return the recorded level.
Why it works
Each round of the walk removes exactly the nodes of one level, because those are precisely the nodes enqueued during the previous round. Comparing with a strict > keeps the earliest level among equal sums.
Complexity
- Time —
O(n) - Space —
O(w), w the widest level
Pitfalls
- Initialising the best sum to 0 fails when every level sum is negative.
- Using
>=returns the last level among ties instead of the first.
Reference solution
Python
from typing import Optional
def maxLevelSum(root: Optional[TreeNode]) -> int:
best_sum = None
best_level = 1
level = [root]
depth = 0
while level:
depth += 1
total = 0
nxt = []
for node in level:
total += node.val
if node.left:
nxt.append(node.left)
if node.right:
nxt.append(node.right)
if best_sum is None or total > best_sum:
best_sum = total
best_level = depth
level = nxt
return best_levelJava
public static int maxLevelSum(TreeNode root) {
Deque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
int depth = 0, bestLevel = 1;
long bestSum = Long.MIN_VALUE;
while (!queue.isEmpty()) {
depth++;
long total = 0;
for (int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
total += node.val;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
if (total > bestSum) { bestSum = total; bestLevel = depth; }
}
return bestLevel;
}C++
int maxLevelSum(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
int depth = 0, bestLevel = 1;
long long bestSum = LLONG_MIN;
while (!q.empty()) {
depth++;
long long total = 0;
for (int i = (int) q.size(); i > 0; i--) {
TreeNode* node = q.front();
q.pop();
total += node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
if (total > bestSum) { bestSum = total; bestLevel = depth; }
}
return bestLevel;
}JavaScript
var maxLevelSum = function(root) {
var queue = [root], head = 0, depth = 0, bestLevel = 1, bestSum = 0;
while (head < queue.length) {
var end = queue.length, total = 0;
depth++;
while (head < end) {
var node = queue[head++];
total += node.val;
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
if (depth === 1 || total > bestSum) { bestSum = total; bestLevel = depth; }
}
return bestLevel;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 156 breadth-first search problems · the whole catalogue
Learn the technique: Breadth-First Search (BFS) · Binary Trees and Tree Traversals