Maximum Level Sum of a Binary Tree

Problem in plain words

Number the levels of a binary tree starting from 1 at the root. Add up the values on each level. Return the number of the level with the biggest total; if several levels tie, return the smallest such level number.

Example: root 2, children -5 and 9, and 9 has a child 1. The level sums are 2, 4 and 1, so the answer is level 2.

Intuition

We need an aggregate per level, which is exactly what a level-order traversal gives us. Process the BFS queue one level at a time, compute that level's sum, and compare it with the best seen so far. Updating only on a strictly larger sum automatically keeps the earliest level on ties.

Approach

1. Start a queue with the root, level = 0, bestSum = -infinity, bestLevel = 1.
2. While the queue is non-empty, increment level and pop exactly the current queue size worth of nodes, adding their values to sum and enqueuing their children.
3. If sum > bestSum, record bestSum = sum and bestLevel = level.
4. Return bestLevel.

Dry run

Java solution

class Solution {
    public int maxLevelSum(TreeNode root) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        long bestSum = Long.MIN_VALUE;
        int bestLevel = 1;
        int level = 0;
        while (!queue.isEmpty()) {
            level++;
            long sum = 0;
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            if (sum > bestSum) {
                bestSum = sum;
                bestLevel = level;
            }
        }
        return bestLevel;
    }
}

Python solution

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        best_sum, best_level, level = float('-inf'), 1, 0
        queue = deque([root])
        while queue:
            level += 1
            total = 0
            for _ in range(len(queue)):
                node = queue.popleft()
                total += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if total > best_sum:
                best_sum, best_level = total, level
        return best_level

Complexity

Edge cases and common mistakes

• All-negative trees — initialise the best sum to negative infinity (or the root level's sum), never to 0, or you may return a level that does not exist.
• Using `>=` — that would return the last level among ties. The problem wants the smallest level, so update only on a strictly larger sum.
• Off-by-one level numbers — levels start at 1, not 0.
• Overflow worries — a level's sum fits in int for the given limits, but using long costs nothing and is safer.