Maximum Level Sum of a Binary Tree

Solving tips

'Per-level' is BFS's native vocabulary: snapshot len(queue) before draining so one outer-loop iteration sums exactly one level. O(n) time, O(w) space.
DFS works too if each call carries its depth and accumulates into sums[depth]; scan for the first max afterward (O(h) space).
Pitfall: values can be negative, so never return early when a level sum drops — a later level can rebound; examine all levels.
Pitfall: seed best_sum from the root or -inf (not 0), use strict > so ties break toward the shallower level, and remember levels are 1-indexed in the answer.

Problem

Given the root of a binary tree, label the root’s level as 1, its children as level 2, and so on. For each level, compute the sum of all node values on it. Return the smallest level number whose sum is maximal (ties break toward the shallower level). Node values can be negative.

Examples

Input: root = [1,7,0,7,-8,null,null] → Output: 2 Level sums: level 1 = 1, level 2 = 7 + 0 = 7, level 3 = 7 + (-8) = -1. The maximum is 7, first reached at level 2.
Input: root = [989,null,10250,98693,-89388,null,null,null,-32127] → Output: 2 Sums: 989, 10250, 9305, -32127. Level 2 wins with 10250.
Input: root = [-1,-2,-3] → Output: 1 Sums: -1, -5. All negative — the maximum is -1 at level 1.

Constraints

1 <= n <= 10^4 nodes; -10^5 <= Node.val <= 10^5.
Values may be negative, so you cannot stop early when a level sum drops.
Expected: one O(n) traversal.

Think about it first

Hint 1

What traversal naturally groups nodes level by level?

Hint 2

With breadth-first search, one iteration of the outer loop processes exactly one level — sum the values as you drain the queue's current length.

Hint 3

DFS works too: carry the depth as a parameter and accumulate into `sums[depth]`. Either way, finish all levels, then take the first index of the maximum — don't return early, negatives can rebound.

TL;DR

Level-order BFS, summing one level per queue drain — O(n) time, O(w) space (w = max width).

Approach 1 — Brute force: one full traversal per level

The naive framing: first find the tree’s height H; then for each level 1..H, traverse the whole tree again, adding up only the nodes at that depth.

# 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: Optional[TreeNode]) -> int:
        def height(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            return 1 + max(height(node.left), height(node.right))

        def level_sum(node: Optional[TreeNode], level: int) -> int:
            if not node:
                return 0
            if level == 1:
                return node.val
            return (level_sum(node.left, level - 1)
                    + level_sum(node.right, level - 1))

        best_level, best_sum = 1, level_sum(root, 1)
        for lvl in range(2, height(root) + 1):
            s = level_sum(root, lvl)
            if s > best_sum:
                best_sum, best_level = s, lvl
        return best_level

Complexity: O(n · h) time, O(h) space. On a skewed tree of 10^4 nodes that is ~10^8 node visits — the constraints exist precisely to make you compute all level sums in a single pass.

Approach 2 — BFS level by level (the classic)

The insight: breadth-first search visits the tree in exactly the grouping the problem asks about. If you snapshot the queue length before draining, one while iteration processes one complete level, so its sum is available the moment the level ends. Track the best sum and the first level achieving it.

# 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

from collections import deque

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

Walkthrough on root = [1,7,0,7,-8,null,null]:

Level 1: queue [1] → total 1; best = (1, level 1). Enqueue 7, 0.
Level 2: drain [7, 0] → total 7 > 1; best = (7, level 2). Enqueue 7, -8.
Level 3: drain [7, -8] → total −1; not better. Queue empty → return 2.

Complexity: O(n) time — each node enqueued and dequeued once; O(w) space where w is the maximum level width (up to n/2 on a complete tree).

The strict > in the comparison is what implements “smallest level wins ties”.

Approach 3 — DFS with depth-indexed sums (the well-known alternative)

The insight: BFS grouping isn’t required — any traversal works if each visit knows its depth. Recurse carrying depth, accumulate into a list where index d holds level d+1’s running sum, then scan for the first maximum.

# 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: Optional[TreeNode]) -> int:
        sums: List[int] = []

        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if not node:
                return
            if depth == len(sums):
                sums.append(node.val)
            else:
                sums[depth] += node.val
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

        dfs(root, 0)
        best = max(sums)
        return sums.index(best) + 1

Walkthrough on root = [-1,-2,-3]: visit -1 at depth 0 → sums = [-1]; -2 at depth 1 → sums = [-1, -2]; -3 at depth 1 → sums = [-1, -5]. max is -1, first at index 0 → return 1.

Complexity: O(n) time, O(h) recursion stack plus O(h) for sums (one entry per level). On a deep skewed tree this recursion can hit Python’s default limit (~1000), so BFS is the safer production choice; on a wide bushy tree, DFS’s O(h) beats BFS’s O(w) memory. Knowing which traversal’s memory profile fits the tree shape is the real content of this alternative.

Common pitfalls

Returning as soon as a level sum decreases — negative values mean sums can dip and then recover, so every level must be examined.
Initializing best_sum = 0 — an all-negative tree then reports the wrong level. Seed it from the root (or use -inf).
Using >= when updating the best, which breaks the tie toward deeper levels; the problem wants the smallest level.
Forgetting that levels are 1-indexed in the answer while your list or counter is 0-indexed.

Pattern takeaway

“Per-level” is BFS’s native vocabulary. Any question phrased in terms of levels — level sums, level averages, rightmost node per level, zigzag order — maps to the snapshot-the-queue-length BFS loop; and the DFS-with-depth trick is the interchangeable alternative whenever recursion depth is safe. Choose between them by memory: O(width) for BFS, O(height) for DFS.