1161. Maximum Level Sum of a Binary Tree

Medium · solved 2026-10-06 · Open on LeetCode

treebinary-treebfs

Time O(n) · Space O(w)

How to get there

Close a level when the next node belongs to another

1. Restate the answer. Sum the values on each level, numbering the root’s level 1, and return the level with the largest sum. On a tie, the smallest level wins.

2. Sum LeetCode’s first example by hand and find where one queue gets stuck. In [1, 7, 0, 7, -8], the levels sum to 1, 7 + 0 = 7, and 7 + (−8) = −1, so the answer is level 2. A breadth-first queue visits nodes level by level, but it is one long line: nothing in it says where one level ends and the next begins, and a level’s sum can only be judged once the level is complete.

3. Tag each node with its level. Push (node, level), and every child gets its parent’s level + 1. Now each node carries its level, and the sum can run for the current level.

4. Detect the end of a level by peeking. The children of the node just taken are already appended, so queue[0] is the next node to come out. If the queue is empty, or queue[0] is on a different level, the node just taken was the last of its level: close the sum, compare it with the best, and reset.

5. Settle ties and negative sums. best starts at root.val - 1, below level 1’s sum, so level 1 is always taken first, even when every sum is negative. The comparison is a strict >, so a later level with an equal sum never replaces an earlier one, and the smallest level wins the tie.

6. Check the cost. Each node is queued once: O(n) time, and O(w) for the widest level in the queue.

The reusable recipe: to process a breadth-first walk group by group without counting, tag each item with its group and close a group when the next item belongs to another.

Let the running sum's meaning write the branches

Variable	Always means, at the top of the loop
`queue`	`(node, level)` pairs in breadth-first order: the rest of one level, then the start of the next
`temp_sum`	the sum of the nodes already taken on the current level
`best`, `result`	the largest closed level sum so far, and the smallest level that has it

Code	What happened	What it keeps true
`queue, best, result = deque([(root, 1)]), root.val-1, 1`	nothing is summed yet	`best` sits below level 1’s sum, so level 1 is taken first
`queue.append((child, level+1))`	the node’s children are found	each child carries its level
`if not queue or queue[0][1] != level:`	the next node is on another level, or there is none	`current` is the last node of its level
`temp_sum += current.val`, then the comparison	the level is complete	a strictly larger sum takes over, so ties keep the earlier level
`temp_sum = 0`	the next level starts	the running sum describes the new level
`else: temp_sum += current.val`	more of this level is coming	the running sum grows

Both branches add current.val, so the addition can move above the if and the else disappears. The if not root guard never runs, since LeetCode guarantees at least one node.

The method carries over: say what the running total covers, and close it exactly when that description stops being true.

Alternatives compared

Approach	Time	Space	How it works
Level by level with a count	O(n)	O(w)	Breadth-first search with `for _ in range(len(queue))`: each round takes exactly one level, so its sum is complete when the round ends.
Level tags and a peek (chosen, `solution.py`)	O(n)	O(w)	Each queue entry carries its level; a level closes when the next entry belongs to another.
Depth-first with a sum per depth	O(n)	O(h + levels)	Walk the tree in any order, adding each value to `sums[depth]`; then pick the first index of the maximum.

The breadth-first versions close each level as soon as it is complete. The depth-first one keeps every level’s sum until the end, which needs a list as long as the tree is tall but no queue.

solution.py

# 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: TreeNode | None) -> int:
        if not root:
            return 0

        queue, best, result = deque([(root, 1)]), root.val-1, 1

        temp_sum = 0
        while queue:
            current, level = queue.popleft()

            if current.left:
                queue.append((current.left, level+1))
            if current.right:
                queue.append((current.right, level+1))

            if not queue or queue[0][1] != level:
                temp_sum += current.val
                if temp_sum > best:
                    best = temp_sum
                    result = level
                temp_sum = 0
            else:
                temp_sum += current.val

        return result

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.