Maximum Level Sum of a Binary Tree — LeetCode 1161 BFS Pattern

Problem Statement#

Given the root of a binary tree where the level of the root is 1, return the smallest level x such that the sum of all node values on level x is maximal.

Constraints:

• The number of nodes in the tree is in the range [1, 10^4]
• -10^5 <= Node.val <= 10^5

Input:  root = [1,7,0,7,-8,null,null]
Output: 2

Input:  root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2

Why This Problem Matters#

LeetCode 1161 — Maximum Level Sum of a Binary Tree — is a high-frequency BFS question at Amazon, Meta, Uber, and Microsoft. It looks like a basic level-order traversal, but the twist of returning the smallest level (i.e., the first one) on a tie tests careful comparison logic — a common spot where candidates lose points.

Interviewers love this problem because it can be solved in three lines with the right pattern but requires negative-value awareness, since Node.val can be -10^5. Initialize the running max to -infinity, not 0, or you'll silently fail on all-negative trees.

This pattern appears in real-world analytics: identifying the "hottest" tier of a hierarchy, finding the layer with maximum aggregated metric in a routing tree, or selecting the most-loaded shard layer in a sharded database.

The Core Insight#

Run BFS, keep a level counter starting at 1. For each level, sum the node values, compare against the running maximum, and update the answer level only when we strictly exceed the current max — strict comparison ensures we keep the smallest level on ties.

DFS also works: pass depth recursively and accumulate level_sums[depth] += node.val in a hashmap or list, then scan for the index of the max.

Visual Dry Run#

Tree [1, 7, 0, 7, -8]:

Answer: level 2.

Solution (Optimal)#

from collections import deque
from typing import Optional
 
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:
        if root is None:
            return 0
        queue = deque([root])
        best_level = 1
        best_sum = float('-inf')
        level = 0
        while queue:
            level += 1
            level_sum = 0
            for _ in range(len(queue)):
                node = queue.popleft()
                level_sum += node.val
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
            if level_sum > best_sum:
                best_sum = level_sum
                best_level = level
        return best_level

var maxLevelSum = function(root) {
    if (!root) return 0;
    const queue = [root];
    let bestLevel = 1;
    let bestSum = -Infinity;
    let level = 0;
    while (queue.length > 0) {
        level += 1;
        let levelSum = 0;
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            levelSum += node.val;
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        if (levelSum > bestSum) {
            bestSum = levelSum;
            bestLevel = level;
        }
    }
    return bestLevel;
};

Time: O(n) — each node enqueued and dequeued once. Space: O(w) — queue holds at most the widest level.

Common Mistakes#

• Initializing bestSum = 0. With negative values like -10^5, you'll incorrectly return level 1.
• Using >= instead of > and updating to a later level on ties.
• Computing depth via DFS but forgetting to track level_sums per index, leading to off-by-one between 0-indexed depth and 1-indexed level.
• Forgetting that the root is level 1, not level 0.
• Using queue.shift() repeatedly in JavaScript on n = 10^4 is fine but slow; for larger inputs prefer an index pointer.

Interview Tips#

• Mention both BFS and DFS solutions. BFS is cleaner here.
• Walk through the tie-breaker: "I update only when strictly greater, so the smallest level wins."
• Ask: "Are levels 1-indexed?" if not stated. Most LeetCode tree-level problems use 1-indexed levels.
• Sketch a small tree with negative leaves to highlight the -infinity initialization.

Follow-up Questions#

• "Smallest level with minimum sum" — Flip the comparator to < with +infinity initial.
• "Average per level instead of sum" — LC 637, divide by level size.
• "K-ary tree variant" — Replace node.left, node.right with a children loop.
• "Streaming variant: nodes arrive online" — Maintain per-level sums in a hashmap keyed by depth.
• "Level with max odd-valued sum" — Filter inside the inner loop before adding.

Key Takeaways#

• LeetCode 1161 Maximum Level Sum returns the smallest 1-indexed level with maximal node sum.
• BFS with a level counter and strict-greater comparison gives O(n) time, O(w) space.
• Initialize the running max to negative infinity to handle trees of negative values.
• DFS with a depth-indexed sum array works equivalently in O(n).
• Strict-greater (>) preserves the smallest-level tie-breaker; >= would be a bug.
• Frequent at Amazon, Meta, and Uber as a BFS pattern check.
• Generalizes to "find the layer with extreme aggregate" across many tree analytics tasks.