Domain 2MediumMEDIUM

Maximum Level Sum of a Binary Tree

Perform a level-order traversal (BFS), calculating the sum of node values at each depth, tracking the shallowest index with the maximum cumulative sum.

Domain: medium•Updated: 2026-09-09
#Breadth-First Search#Queue#Level Order Traversal#O(N) Time Complexity

Problem Breakdown

We are given the root of a binary tree where levels start from 1 for the root. The objective is to compute the sum of node values at each level and return the smallest level index that possesses the maximum total sum.

Inputs:

  • A pointer to the root TreeNode.
  • Constraints: Tree size [1, 10^4], Node values between -10^5 and 10^5.

Outputs:

  • An integer representing the level index (1-based).

Key Requirements:

  • Handle negative node sums correctly.
  • Return the smallest level index in case of ties for maximum sum.
  • Ensure linear time complexity O(N)O(N) to handle large inputs efficiently.

Intuition

Since levels are defined by distance from the root, a Breadth-First Search (BFS) is the most natural traversal method. BFS processes nodes layer-by-layer naturally using a queue.

Why not DFS? While Depth First Search visits every node in O(N)O(N) time as well, managing level boundaries requires passing depth parameters or maintaining state during backtracking. BFS isolates levels explicitly by processing all current queue items before moving to the next iteration (level).

Handling Negatives: Since sums can be negative, initializing max_sum to zero is incorrect; it must start at a value lower than any possible sum (-float('inf')). This ensures that even if every level has a negative sum, we correctly identify the “least negative” as the maximum.

Tie-Breaking: To satisfy the requirement of returning the smallest level index when sums are equal, we must use strict inequality (>) rather than greater-than-or-equal-to (>=). This ensures that once a max_sum is found at Level XX, subsequent levels with an identical sum will not update the result.

Approach

  1. Initialization:
    • Initialize a queue (deque) and enqueue the root node.
    • Set max_sum to negative infinity (-float('inf')) to handle cases where all level sums are negative.
    • Set result_level to track the index of the maximum sum found so far.
  2. BFS Traversal:
    • While the queue is not empty, determine the number of nodes currently in the queue (level_size). This count represents exactly how many nodes exist at the current depth level.
  3. Process Level Nodes:
    • Iterate level_size times to process all nodes at the current level.
    • Pop a node from the front and add its value to current_level_sum.
    • Enqueue any existing left or right children for processing in subsequent iterations (next levels).
  4. Update Maximum:
    • After finishing the inner loop, compare current_level_sum with max_sum.
    • If current_level_sum > max_sum, update both max_sum and result_level to the current level index (level_idx).
  5. Increment Level Index: Increment level_idx for the next iteration of the outer loop.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the number of nodes in the tree. Each node is enqueued and dequeued exactly once during the BFS traversal.
  • Space Complexity: O(W)O(W), where WW is the maximum width (number of nodes) at any level. In a balanced binary tree, this can be up to N/2N/2. The queue stores these nodes temporarily.

Solution

from collections import deque

# Definition for a binary tree node (Standard LeetCode structure)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxLevelSum(root: 'TreeNode') -> int:
    # Constraints guarantee at least one node (N >= 1), 
    # but handling empty root defensively is good practice.
    if not root:
        return 0 
    
    queue = deque([root])
    
    # Initialize with negative infinity to handle cases where all sums are negative.
    max_sum = -float('inf') 
    result_level = 1
    
    level_idx = 1
    
    while queue:
        current_level_size = len(queue)
        current_level_sum = 0
        
        for _ in range(current_level_size):
            node = queue.popleft()
            current_level_sum += node.val
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Check strict inequality to preserve the smallest level index on ties.
        if current_level_sum > max_sum:
            max_sum = current_level_sum
            result_level = level_idx
            
        level_idx += 1
        
    return result_level

Edge Cases Handled

  • Negative Sums: By initializing max_sum to -float('inf'), the algorithm correctly identifies a negative sum as maximal if all levels have negative sums. For example, if Level 1 is -5 and Level 2 is -3, it returns Level 2 because -3 > -5.
  • Tie Handling: Using strict greater-than (>) when updating ensures that if multiple levels share the same maximum sum (e.g., Level 2 = 7, Level 4 = 7), we return the smallest level index (Level 2).
  • Single Node Tree: The loop runs once for the root; current_level_sum equals root.val, updates max immediately, and returns 1. Correctly handles constraints where N=1N=1.