LeetCode Solutions Blog

Maximum Level Sum of a Binary Tree

Number: 1116

Difficulty: Medium

Paid? No

Problem Description

Given the root of a binary tree, determine the smallest level (starting from 1) with the maximum sum of node values. In other words, compute the sum of every level's nodes and return the level number where the sum is maximized.

Key Insights

Use a level order traversal (BFS) to process the tree by levels.
Maintain a running sum for each level and update the maximum sum when a higher level sum is encountered.
Track the current level and record the level number whenever a new maximum sum is found.
Since the first occurrence of the maximum sum is needed when sums are equal, only update on strictly greater sums.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree (each node is visited once).
Space Complexity: O(m), where m is the maximum number of nodes stored at any level (this can be O(n) in the worst-case scenario of a balanced tree).

Solution

Perform a breadth-first search (BFS) on the binary tree using a queue to traverse the tree level by level. For each level, calculate the sum of nodes and compare it against the maximum sum recorded so far. If the current level's sum exceeds the previous maximum, update the maximum sum and note the level number. This approach naturally handles the requirement to return the smallest level with the maximum sum since levels are processed sequentially.

Code Solutions

from collections import deque

# 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

def maxLevelSum(root: TreeNode) -> int:
    # Initialize the queue for BFS with the root node.
    queue = deque([root])
    max_sum = float('-inf')
    max_level = 1
    current_level = 1
    
    # Process each level of the binary tree
    while queue:
        level_size = len(queue)
        current_sum = 0
        
        # Iterate through all nodes in the current level
        for _ in range(level_size):
            node = queue.popleft()
            current_sum += node.val
            
            # Enqueue left child if it exists
            if node.left:
                queue.append(node.left)
            # Enqueue right child if it exists
            if node.right:
                queue.append(node.right)
        
        # Update the max_sum and corresponding level if this level's sum is higher
        if current_sum > max_sum:
            max_sum = current_sum
            max_level = current_level
        
        # Move to the next level
        current_level += 1
    
    return max_level

# Example usage:
# Construct the binary tree: [1,7,0,7,-8,null,null]
root = TreeNode(1)
root.left = TreeNode(7)
root.right = TreeNode(0)
root.left.left = TreeNode(7)
root.left.right = TreeNode(-8)

print(maxLevelSum(root))  # Expected Output: 2