🌲 Beginner-Friendly Guide 'Maximum Level Sum of a Binary Tree' – LeetCode 1161 (C++, Python, JavaScript)

Navigating a binary tree can often feel like exploring a multi-story building. To find which floor has the most "value," we need a strategy that lets us visit one level at a time and tally up the scores.

---

Problem Summary

You're given:

• The root of a binary tree where each node contains an integer value.
• A structure where the root starts at Level 1, its children are at Level 2, and so on.

Your goal:

• Find the level number that has the highest total sum of node values.
• If two or more levels have the same maximum sum, return the smallest (lowest) level number among them.

For Example

Input: root = [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.

---

Intuition

The most effective way to process a tree level by level is a technique called Breadth-First Search (BFS). Instead of diving deep into one branch, we use a queue to keep track of all nodes on the current "floor" before moving to the next.

1. The Queue Strategy: We start by placing the root in a queue.
2. Level Processing: While the queue isn't empty, we look at its current size. This size tells us exactly how many nodes are on the current level.
3. Summation: we loop through that many nodes, add their values to a running total, and then add their children (the next level) to the back of the queue.
4. Comparison: After finishing a level, we compare its sum to the highest sum we've seen so far. By keeping track of the level index, we can easily identify which floor was the "winner."

---

Code Blocks

C++

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        if (!root) return 0;

        long long maxSum = LLONG_MIN;
        int maxLevel = 1;
        int currentLevel = 1;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int size = q.size();
            long long levelSum = 0;

            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;
    }
};

Python

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
            # Process all nodes currently in the queue for this level
            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)

            # Update max_sum and result level if a new maximum is found
            if level_sum > max_sum:
                max_sum = level_sum
                max_level = current_level

            current_level += 1

        return max_level

JavaScript

var maxLevelSum = function(root) {
    if (!root) return 0;

    let maxSum = -Infinity;
    let maxLevel = 1;
    let currentLevel = 1;

    const queue = [root];

    while (queue.length > 0) {
        let levelSize = queue.length;
        let levelSum = 0;

        for (let i = 0; i < levelSize; 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;
};

---

Key Takeaways

• Breadth-First Search (BFS): This is the gold standard for "level-order" problems. It ensures we visit nodes in the order of their distance from the root.
• Queue Management: Using a queue (or deque in Python) allows for efficient removal from the front, keeping our total time complexity at .
• Handling Negatives: Since node values can be negative, it is vital to initialize your "maximum sum" variable to a very small number like LLONG_MIN or -Infinity rather than 0.

---

Final Thoughts

This problem is a fantastic introduction to tree traversal patterns used in high-scale systems. For instance, in search engine indexing, crawlers might use BFS to index pages level by level from a home page to ensure they capture the most "relevant" (top-level) information first. In social network analysis, finding the level with the most nodes is similar to identifying which "degree of separation" contains the most potential connections. Mastering BFS is a core requirement for technical interviews at companies like Google or Meta.