LeetCode 1161 - Maximum Level Sum of a Binary Tree

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

In this problem, we are given the root node of a binary tree. Every node belongs to a specific level in the tree. The root is at level 1, its direct children are at level 2, their children are at level 3, and so on.

Our goal is to compute the sum of node values at every level and return the level number whose sum is the largest. If multiple levels have the same maximum sum, we must return the smallest level number among them.

The input is a standard binary tree structure where each node contains:

An integer value
A reference to a left child
A reference to a right child

The output is a single integer representing the level with the highest sum.

The constraints tell us several important things:

The tree can contain up to 10^4 nodes, so the solution must be efficient.
Node values may be negative, which means we cannot assume sums are always increasing.
Since the tree is not guaranteed to be balanced, the height could be as large as the number of nodes.

A naive solution that repeatedly traverses the tree level by level could become inefficient. We need a method that visits every node only once.

There are several important edge cases to consider:

A tree containing only one node
Trees where all values are negative
Multiple levels having the same maximum sum
Highly unbalanced trees that resemble linked lists
Sparse trees with many null children

The problem guarantees that at least one node exists, so we never need to handle an empty tree.

Approaches

Brute Force Approach

A brute force strategy would first compute the height of the tree. Then, for every level from 1 to height, we would perform a traversal to calculate the sum of nodes at that specific depth.

For example:

Traverse the tree to compute all nodes at level 1
Traverse again for level 2
Traverse again for level 3
Continue until the deepest level

This works because every level sum is computed correctly. However, it is inefficient because the tree is repeatedly traversed.

If the tree height is h and there are n nodes, this approach may take O(n * h) time. In the worst case of a skewed tree, h = n, leading to O(n^2) complexity.

Optimal Approach

The key observation is that we can compute level sums during a single traversal of the tree.

Breadth-First Search, also called level-order traversal, is ideal because it naturally processes nodes one level at a time.

Using a queue:

Start with the root node
Process all nodes currently in the queue, these belong to the same level
Compute their total sum
Add their children into the queue
Move to the next level

This guarantees that every node is visited exactly once.

Because we process one level at a time, it becomes easy to track:

The current level number
The sum of that level
The maximum sum seen so far
The corresponding level number

This reduces the time complexity to O(n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * h)	O(h)	Repeatedly traverses the tree for each level
Optimal	O(n)	O(w)	Single BFS traversal, where `w` is maximum tree width

Algorithm Walkthrough

Create a queue and insert the root node into it.

The queue allows us to process the tree level by level. This is exactly what Breadth-First Search is designed for. 2. Initialize tracking variables.

We maintain:

current_level, starting at 1
best_level, initially 1
max_sum, initially negative infinity

These variables help track which level currently has the largest sum. 3. Process the queue while it is not empty.

Each iteration of the loop handles one entire level of the tree. 4. Determine the number of nodes in the current level.

The queue length at the start of the iteration tells us exactly how many nodes belong to this level. 5. Compute the level sum.

Remove each node from the queue:

Add its value to level_sum
Push its left child into the queue if it exists
Push its right child into the queue if it exists

Compare the current level sum with the best sum seen so far.

If level_sum > max_sum:

Update max_sum
Update best_level

We use strictly greater comparison so that ties automatically preserve the smallest level number. 7. Increment the level counter.

After processing all nodes in the current level, move to the next level. 8. Return best_level.

Once the traversal is complete, this variable contains the smallest level with the maximum sum.

Why it works

Breadth-First Search processes nodes level by level in exact order from top to bottom. At the start of each iteration, the queue contains only nodes belonging to the current level. Therefore, summing all nodes currently processed gives the exact sum for that level.

Since every node is visited exactly once and every level sum is compared against the global maximum, the algorithm correctly identifies the smallest level with the maximum sum.

Python Solution

from collections import deque
from typing import Optional

# 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:
        queue = deque([root])

        current_level = 1
        best_level = 1
        max_sum = float("-inf")

        while queue:
            level_size = len(queue)
            level_sum = 0

            for _ in range(level_size):
                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
                best_level = current_level

            current_level += 1

        return best_level

The implementation begins by creating a queue containing the root node. The queue enables level-order traversal.

The variables current_level, best_level, and max_sum keep track of traversal progress and the best answer found so far.

Inside the main loop, level_size captures how many nodes belong to the current level. This is important because new child nodes are added during iteration, and we only want to process the current level in each pass.

The inner loop removes nodes one by one, adds their values to level_sum, and inserts any existing children into the queue for future processing.

After finishing the level, the algorithm compares the current sum against the maximum sum seen so far. If the current level is better, the answer variables are updated.

Finally, the level counter increases and the traversal continues until all nodes have been processed.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func maxLevelSum(root *TreeNode) int {
    queue := []*TreeNode{root}

    currentLevel := 1
    bestLevel := 1
    maxSum := -(1 << 60)

    for len(queue) > 0 {
        levelSize := len(queue)
        levelSum := 0

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]

            levelSum += node.Val

            if node.Left != nil {
                queue = append(queue, node.Left)
            }

            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        if levelSum > maxSum {
            maxSum = levelSum
            bestLevel = currentLevel
        }

        currentLevel++
    }

    return bestLevel
}

The Go implementation follows the same BFS logic as the Python solution.

Instead of Python's deque, Go uses a slice as a queue. Removing the front element is done using:

queue = queue[1:]

Go uses nil checks for child nodes instead of truthy checks.

The variable maxSum is initialized to a very small negative number to correctly handle trees containing only negative values.

Since the constraints fit comfortably within Go's integer range, integer overflow is not a concern here.

Worked Examples

Example 1

Input:

root = [1,7,0,7,-8,null,null]

Tree structure:

Step-by-step traversal

Level	Queue Before Processing	Level Sum	Best Level	Max Sum
1	[1]	1	1	1
2	[7, 0]	7	2	7
3	[7, -8]	-1	2	7

Final answer:

Example 2

Input:

root = [989,null,10250,98693,-89388,null,null,null,-32127]

Tree structure:

        989
           \
           10250
           /   \
       98693  -89388
               /
           -32127

Step-by-step traversal

Level	Nodes	Level Sum
1	[989]	989
2	[10250]	10250
3	[98693, -89388]	9305
4	[-32127]	-32127

The maximum sum is 10250 at level 2.

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(w)	Queue stores at most one level at a time

The algorithm performs a standard Breadth-First Search traversal. Each node enters and leaves the queue exactly once, producing linear time complexity.

The space usage depends on the maximum number of nodes stored simultaneously in the queue. In the worst case of a complete binary tree, this can be approximately half the nodes, giving O(w) space complexity where w is the maximum tree width.

Test Cases

from collections import deque
from typing import Optional

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:
        queue = deque([root])

        current_level = 1
        best_level = 1
        max_sum = float("-inf")

        while queue:
            level_size = len(queue)
            level_sum = 0

            for _ in range(level_size):
                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
                best_level = current_level

            current_level += 1

        return best_level

solution = Solution()

# Example 1
root1 = TreeNode(
    1,
    TreeNode(7, TreeNode(7), TreeNode(-8)),
    TreeNode(0)
)
assert solution.maxLevelSum(root1) == 2  # maximum sum at level 2

# Example 2
root2 = TreeNode(
    989,
    None,
    TreeNode(
        10250,
        TreeNode(98693),
        TreeNode(-89388, TreeNode(-32127), None)
    )
)
assert solution.maxLevelSum(root2) == 2  # level 2 has largest sum

# Single node tree
root3 = TreeNode(5)
assert solution.maxLevelSum(root3) == 1  # only one level exists

# All negative values
root4 = TreeNode(
    -1,
    TreeNode(-2),
    TreeNode(-3)
)
assert solution.maxLevelSum(root4) == 1  # -1 is greater than -5

# Tie between levels
root5 = TreeNode(
    1,
    TreeNode(2),
    TreeNode(1)
)
assert solution.maxLevelSum(root5) == 1  # both levels sum to 3, choose smaller level

# Left-skewed tree
root6 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(
            3,
            TreeNode(4)
        )
    )
)
assert solution.maxLevelSum(root6) == 4  # deepest level has largest sum

# Sparse tree
root7 = TreeNode(
    10,
    TreeNode(2, None, TreeNode(5)),
    TreeNode(3)
)
assert solution.maxLevelSum(root7) == 3  # level 3 sum is 5

Test	Why
`[1,7,0,7,-8,null,null]`	Validates the primary example
`[989,null,10250,98693,-89388,null,null,null,-32127]`	Tests sparse structure with negative values
Single node tree	Ensures minimal input works
All negative values	Confirms maximum among negative sums is handled correctly
Tie between levels	Verifies smallest level number is returned
Left-skewed tree	Tests highly unbalanced trees
Sparse tree	Ensures missing children do not affect traversal

Edge Cases

One important edge case is a tree containing only a single node. In this scenario, the root is both the only node and the only level. A careless implementation might incorrectly initialize variables or fail to process the queue correctly. This solution handles the case naturally because the BFS loop runs once and returns level 1.

Another critical case involves trees where all node values are negative. Some implementations incorrectly initialize the maximum sum to 0, which would fail because every level sum would be smaller than zero. This implementation initializes max_sum to negative infinity, ensuring that negative sums are processed correctly.

A third important edge case is when multiple levels share the same maximum sum. The problem specifically requires returning the smallest level number. This implementation uses a strictly greater comparison:

if level_sum > max_sum:

Because equal sums do not overwrite the previous answer, the earliest level is preserved automatically.

Highly unbalanced trees are another potential source of bugs. In a skewed tree, the height can approach the number of nodes. Recursive DFS solutions could risk stack depth issues in some languages. The iterative BFS solution avoids recursion entirely and handles skewed trees safely.