Maximum Level Sum Of A Binary Tree - Leetcode Solution

Problem Statement:

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.

Example:

Input: [1,7,0,7,-8,null,null] Output: 2 Explanation: Level 1 sum = 1. Level 2 sum = 7 + 0 = 7. Level 3 sum = 7 + (-8) = -1. So we return the level with the maximum sum which is level 2.

Solution:

To solve this problem, we traverse the given binary tree in a level by level order. For each level, we calculate the sum of all the nodes at that level and keep track of the maximum sum and the level with that maximum sum. Here are the detailed steps of the algorithm:

1. Create an empty queue and push the root node into it.
2. Initialize the level to 1 and the maximum sum to the value of the root node.
3. While the queue is not empty, do the following: a. Get the current size of the queue and a variable to store the sum of nodes at the current level. b. Loop through all the nodes at the current level (i.e., the nodes in the queue) and add their values to the sum variable. c. If the sum variable is greater than the maximum sum, update the maximum sum and the level with that sum. d. Push the left and right child of each node into the queue if they exist. e. Increment the level variable by 1.
4. Return the level with the maximum sum.

Here is the Python code that implements the above algorithm:

class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        q = [root]
        level = 1
        max_sum = root.val
        
        while q:
            size = len(q)
            level_sum = 0
            
            for i in range(size):
                node = q.pop(0)
                level_sum += node.val
                
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            
            if level_sum > max_sum:
                max_sum = level_sum
                result = level
            
            level += 1
        
        return result

Time Complexity: O(N) where N is the number of nodes in the binary tree. We traverse each node in the tree exactly once.

Space Complexity: O(W) where W is the maximum width of the binary tree. In the worst case scenario, the queue will hold all the nodes in the last level of the tree, which can be at most N/2 nodes.

1