Code Implementation

# 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

from collections import deque

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        max_sum = float('-inf')
        max_level = 1
        current_level = 1
        queue = deque([root])
        
        while queue:
            level_sum = 0
            for _ in range(len(queue)):
                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
                max_level = current_level
            current_level += 1
        return max_level
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };
#include <queue>
class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        if (!root) return 0;
        int maxSum = INT_MIN;
        int maxLevel = 1;
        int currentLevel = 1;
        std::queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int levelSum = 0;
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front(); q.pop();
                levelSum += node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            if (levelSum > maxSum) {
                maxSum = levelSum;
                maxLevel = currentLevel;
            }
            currentLevel++;
        }
        return maxLevel;
    }
};
      

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode() {}
//     TreeNode(int val) { this.val = val; }
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }
import java.util.*;

class Solution {
    public int maxLevelSum(TreeNode root) {
        if (root == null) return 0;
        int maxSum = Integer.MIN_VALUE;
        int maxLevel = 1;
        int currentLevel = 1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSum = 0;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                levelSum += node.val;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            if (levelSum > maxSum) {
                maxSum = levelSum;
                maxLevel = currentLevel;
            }
            currentLevel++;
        }
        return maxLevel;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxLevelSum = function(root) {
    if (!root) return 0;
    let maxSum = -Infinity;
    let maxLevel = 1;
    let currentLevel = 1;
    let queue = [root];
    while (queue.length > 0) {
        let levelSum = 0;
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            levelSum += node.val;
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        if (levelSum > maxSum) {
            maxSum = levelSum;
            maxLevel = currentLevel;
        }
        currentLevel++;
    }
    return maxLevel;
};
      

Problem Description

Given the root of a binary tree, return the level (starting at 1) with the maximum sum of node values. If there are multiple such levels, return the smallest level number.

• You are given a binary tree structure via the TreeNode class.
• The tree is non-empty (at least one node).
• Levels are counted starting from 1 (the root is level 1).
• There is always at least one valid answer.

Your task is to traverse the tree and find the level whose sum of all node values is maximized. If multiple levels have the same sum, return the smallest such level.

Thought Process

To solve this problem, we first need to understand how to process a binary tree by levels. This is a classic use case for a breadth-first search (BFS) traversal. BFS naturally processes nodes level by level, making it easy to compute the sum of nodes at each level.

A brute-force approach would be to traverse the tree multiple times: once for each level, summing the node values. But this is inefficient, especially for large trees.

Instead, we can optimize by using a queue to process all nodes at each level in a single pass. At each level, we sum the node values, compare against the current maximum, and track which level had the highest sum. This way, we only traverse each node once.

This approach is both efficient and straightforward, leveraging the properties of BFS to solve the problem in a single traversal.

Solution Approach

Let's break down the solution into clear steps:

1. Initialize Tracking Variables:
   • max_sum: to keep track of the highest level sum found so far (initialized to negative infinity).
   • max_level: to store the level number with the maximum sum.
   • current_level: to track which level we're on as we traverse.
2. Set Up a Queue for BFS:
   • Use a queue (such as collections.deque in Python) and add the root node to it.
3. BFS Traversal:
   • While the queue is not empty, do the following for each level:
   • Determine the number of nodes at the current level (queue size).
   • Initialize a variable to sum the node values at this level.
   • Process each node at this level:
     • Dequeue the node, add its value to the sum.
     • Enqueue its left and right children if they exist.
   • After processing all nodes at this level, compare the sum to max_sum. If it's greater, update max_sum and max_level.
   • Increment current_level.
4. Return the Result:
   • After traversing all levels, return max_level.

This approach ensures each node is processed exactly once, and all level sums are accurately computed.

Example Walkthrough

Let's walk through an example:

        1
       / \
      7   0
     / \
    7  -8
  

• Level 1: Nodes: [1], Sum: 1
• Level 2: Nodes: [7, 0], Sum: 7 + 0 = 7
• Level 3: Nodes: [7, -8], Sum: 7 + (-8) = -1

We compare the sums:

• Level 1 sum = 1
• Level 2 sum = 7 (maximum)
• Level 3 sum = -1

Step-by-step, our code would:

1. Start at level 1: sum = 1, max_sum = 1, max_level = 1
2. Level 2: sum = 7, max_sum updated to 7, max_level = 2
3. Level 3: sum = -1, max_sum remains 7
4. Return 2

Time and Space Complexity

• Brute-force approach:
  • Would require traversing the tree for each level, leading to O(N * H) time, where N = number of nodes, H = height of tree.
• Optimized BFS approach:
  • Time Complexity: O(N), since each node is visited exactly once.
  • Space Complexity: O(W), where W is the maximum width of the tree (the largest number of nodes at any level), due to the queue used in BFS.

This makes the BFS solution efficient for both time and space.

Summary

To find the level of a binary tree with the maximum sum, we use a breadth-first search (BFS) to process the tree level by level. By summing the nodes at each level and tracking the maximum, we efficiently solve the problem in linear time. The key insight is that BFS aligns perfectly with the requirement to process levels, making the solution both intuitive and optimal.