Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Breadth-first traversal groups nodes by depth, making each level's sum available before advancing. Processing levels from smallest to largest also makes the tie rule simple: keep the earlier level when sums are equal.

Approach

Queue the root and begin numbering levels at one. At each iteration, process exactly the queue size recorded at that level's start, summing node values and enqueuing their children for the next level. Update the answer only for a strictly larger sum. Initialize the best sum to negative infinity so all-negative trees are handled correctly. Return the earliest level attaining the maximum sum.

# 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:
        q = deque([root])
        mx = -inf
        res = 0
        level = 1

        while q:
            total = 0
            for _ in range(len(q)):
                n = q.popleft()
                total += n.val
                if n.left:
                    q.append(n.left)
                if n.right:
                    q.append(n.right)

            if total > mx:
                mx = total
                res = level
            level += 1

        return res

Complexity analysis

For N nodes and maximum tree width W, both implementations take O(N) time. Python's deque removes processed entries and uses O(W) auxiliary space. JavaScript advances a head index without removing old array entries, so its queue retains O(N) node references and uses O(N) auxiliary space.