We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Level Sum of a Binary Tree

Difficulty: Medium

Problem Description

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on. Return the smallest level x such that the sum of all the values of nodes at level x is maximal.

Key Insights

  • The problem requires calculating the sum of node values at each level of a binary tree.
  • A breadth-first search (BFS) approach is suitable for level-order traversal, allowing us to sum values level by level.
  • We need to track both the sums of each level and the level numbers to determine the smallest level with the maximal sum.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the binary tree, as we must visit each node exactly once.
Space Complexity: O(W), where W is the maximum width of the tree, due to the queue used for BFS.

Solution

We will use a breadth-first search (BFS) approach to traverse the binary tree level by level. We will maintain a queue to hold nodes for processing and calculate the sum of values at each level. After processing all levels, we will identify the level with the maximum sum and return the smallest level in case of ties.

Code Solutions

from collections import deque

def maxLevelSum(root):
    if not root:
        return 1
    
    max_sum = float('-inf')
    min_level = 1
    current_level = 1
    
    queue = deque([root])
    
    while queue:
        level_sum = 0
        level_length = len(queue)
        
        for _ in range(level_length):
            node = queue.popleft()
            level_sum += node.val
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        if level_sum > max_sum:
            max_sum = level_sum
            min_level = current_level
        
        current_level += 1
    
    return min_level
← Back to All Questions