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

Source: Dev.to

Problem Summary

You are given the root of a binary tree where each node stores an integer value.
The root is at Level 1, its children at Level 2, and so on.

Goal:
Return the level number that has the maximum sum of node values.
If several levels share the same maximum sum, return the smallest (i.e., the highest) level number.

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
→ The maximum sum is 7, occurring at level 2.

Intuition

The most natural way to examine a tree level by level is Breadth‑First Search (BFS).
Instead of diving deep into a single branch, BFS uses a queue to process all nodes on the current “floor” before moving to the next.

Algorithm outline

1. Initialize a queue with the root node.
2. While the queue is not empty:
   • Record the current queue size → number of nodes on this level.
   • Dequeue each node, add its value to a running levelSum, and enqueue its non‑null children.
   • After the level is processed, compare levelSum with the best sum seen so far and update the answer if needed.
3. Return the level index that yielded the maximum sum.

The BFS guarantees O(N) time (each node visited once) and O(W) extra space, where W is the maximum width of the tree (the size of the largest level).

Code Blocks

C++

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

        long long maxSum   = LLONG_MIN;   // handles negative values
        int       maxLevel = 1;
        int       curLevel = 1;

        queue q;
        q.push(root);

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

            for (int i = 0; i val;

                if (node->left)  q.push(node->left);
                if (node->right) q.push(node->right);
            }

            if (levelSum > maxSum) {
                maxSum   = levelSum;
                maxLevel = curLevel;
            }
            ++curLevel;
        }
        return maxLevel;
    }
};

Python

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

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        max_sum   = float('-inf')
        max_level = 1
        cur_level = 1

        q = deque([root])

        while q:
            level_sum = 0
            for _ in range(len(q)):
                node = q.popleft()
                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
                max_level = cur_level

            cur_level += 1

        return max_level

JavaScript

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxLevelSum = function (root) {
    if (!root) return 0;

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

    const queue = [root];

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

        for (let i = 0; i  maxSum) {
            maxSum   = levelSum;
            maxLevel = curLevel;
        }
        ++curLevel;
    }

    return maxLevel;
};

Key Takeaways

• Breadth‑First Search (BFS) is the go‑to technique for “level‑order” tree problems.
• A queue (or deque in Python) lets us process each level in O(1) amortized time per node.
• Because node values may be negative, initialise the “maximum sum” with the smallest possible value (LLONG_MIN, -Infinity, or -inf).
• Time complexity: O(N), where N is the number of nodes.
• Space complexity: O(W), where W is the maximum width of the tree (worst‑case O(N) for a completely balanced tree).

Final Thoughts

This problem is an excellent introduction to tree‑traversal patterns that appear in large‑scale systems:

• Search‑engine indexing often uses BFS‑like crawlers to explore pages level by level from a homepage, ensuring the most “important” (top‑level) content is processed first.
• In social‑network analysis, locating the level with the most activity mirrors the “maximum level sum” idea—identifying the most influential “layer” of users.

Mastering BFS and queue management equips you to tackle a wide range of real‑world graph and tree challenges. Happy coding!

Identifying the Most Promising Degree of Separation

Identifying which “degree of separation” contains the most potential connections is a crucial step in graph analysis. Mastering Breadth‑First Search (BFS) is a core requirement for technical interviews at companies like Google or Meta.