Max Level Sum Binary Tree LeetCode 1161

LeetCode 1161 — Maximum Level Sum of a Binary Tree gives you the root of a binary tree with integer node values. Your task is to find the level (1-indexed, where the root is level 1) whose nodes have the greatest sum across all their values. If two levels share the same maximum sum, return the smallest level number.

The tree can contain negative values, which makes initialization tricky — you cannot assume any level has a positive sum. A careful implementation must initialize the maximum sum tracking variable to negative infinity to correctly handle all-negative trees.

This is a clean application of BFS level-order traversal with one extra accumulation step. Instead of collecting node values per level into a list, you sum them directly and compare with the running maximum. The level-size technique separates each level cleanly within the BFS loop.

BFS processes the tree level by level, which is exactly what we need to sum each level independently. The core idea: enqueue the root, then repeatedly dequeue all nodes at the current level (using a snapshot of the queue size), sum their values, enqueue their children, and move on to the next level.

At each level, compare the level's sum with the running maximum. If the current sum strictly exceeds the maximum, update both the maximum and the answer level. Using strict greater-than (not >=) ensures that when two levels tie, the first (smaller) level index is preserved.

This single-pass approach runs in O(n) time since every node is enqueued and dequeued exactly once. Space is O(w) where w is the maximum width of the tree — the maximum number of nodes at any single level.

Initialize a queue with the root node and set level = 1, maxSum = -Infinity, answerLevel = 1. Enter the main while loop that runs as long as the queue is non-empty. At the start of each iteration, snapshot levelSize = queue.size and set levelSum = 0.

Dequeue exactly levelSize nodes. For each node, add its value to levelSum and enqueue its left and right children if they exist. After processing all nodes at the current level, compare levelSum with maxSum. If levelSum > maxSum, update maxSum = levelSum and answerLevel = level. Increment level.

After the loop ends, return answerLevel. The answer is always set at least once on the first level, so no special handling for the empty-queue case beyond the while condition is needed.

A DFS approach is also valid. Perform a DFS (preorder or any order) and pass the current level as a parameter. Maintain an array levelSums where levelSums[level - 1] accumulates the sum for each level. Resize the array as new levels are discovered.

After the full traversal, scan levelSums to find the maximum value and record its index. Return index + 1 as the 1-indexed level number. DFS runs in O(n) time and O(h) space where h is the tree height — O(log n) for balanced trees, O(n) for skewed trees.

BFS tends to be more natural for level-based problems because it processes one complete level per iteration. DFS requires a separate post-traversal scan to find the maximum, while BFS computes the answer incrementally during traversal.

Consider the tree [1, 7, 0, 7, -8, null, null]: root is 1, its children are 7 and 0, and the children of 7 are 7 and -8. Level 1 contains just the root: sum = 1. Level 2 contains nodes 7 and 0: sum = 7 + 0 = 7. Level 3 contains nodes 7 and -8: sum = 7 + (-8) = -1.

Tracking the running maximum: after level 1, maxSum = 1, answerLevel = 1. After level 2, 7 > 1, so maxSum = 7, answerLevel = 2. After level 3, -1 < 7, no update. The final answer is level 2, which matches the expected output.

Notice that level 3 has a negative sum. This is why initializing maxSum to -Infinity is important — if we had initialized it to 0, a tree where all levels have negative sums would produce a wrong answer of the default level rather than the actual maximum.

In Python: use collections.deque for O(1) popleft. Initialize the queue with root, level = 1, max_sum = float('-inf'), ans = 1. While queue: level_size = len(queue), level_sum = 0. Loop level_size times: node = queue.popleft(), level_sum += node.val, append children. If level_sum > max_sum: max_sum, ans = level_sum, level. Increment level. Return ans.

In Java: use ArrayDeque<TreeNode>. Initialize maxSum = Integer.MIN_VALUE, ans = 1, level = 1. While !queue.isEmpty(): int size = queue.size(), levelSum = 0. Loop size times: node = queue.poll(), levelSum += node.val, offer children. If levelSum > maxSum: maxSum = levelSum, ans = level. Increment level. Return ans. O(n) time, O(w) space.

Both implementations are tight loops with no auxiliary data structures beyond the queue. The only language-specific detail is the negative-infinity initialization: Python uses float('-inf'), Java uses Integer.MIN_VALUE. Either way, the first level always sets the baseline.

Maximum Level Sum belongs to the tree BFS family, which processes nodes level by level. Related problems include Binary Tree Right Side View (LeetCode 199), which returns the last node at each level; Zigzag Level Order Traversal (LeetCode 103), which alternates left-to-right and right-to-left direction per level; and Maximum Depth of Binary Tree (LeetCode 104), which counts the total number of levels.

All these problems share the same BFS skeleton: initialize a queue with the root, loop while the queue is non-empty, snapshot the level size, process exactly that many nodes, enqueue their children, and track per-level information. Mastering this skeleton unlocks the entire tree level-order family.

Beyond tree problems, the BFS level-order pattern generalizes to graph shortest-path problems in unweighted graphs. The level in BFS corresponds to the minimum number of edges from the source, making BFS the natural tool for shortest-path queries in grid and graph problems.