Coding Interview PatternsMaximum Level Sum of a Binary Tree
MediumTree Breadth-First Search

Maximum Level Sum of a Binary Tree

Explanation & Solution

Practice Problem

Description

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 number x such that the sum of all the values of nodes at level x is maximal.

Examples

Example 1:

```tree

[1, 7, 0, 7, -8]

`

Input:root = [1, 7, 0, 7, -8]
0
1
1
7
2
0
3
7
4
-8

Output: 2

Explanation: Level 1 sum = 1. Level 2 sum = 7 + 0 = 7. Level 3 sum = 7 + (-8) = -1. The maximum sum is 7 at level 2.

Example 2:

```tree

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

`

Input:root = [989, null, 10250, 98693, -89388, null, null, null, -32127]
0
989
1
null
2
10250
3
98693
4
-89388
5
null
6
null
7
null
8
-32127

Output: 2

Explanation: Level 1 sum = 989. Level 2 sum = 10250. Level 3 sum = 98693 + (-89388) = 9305. Level 4 sum = -32127. The maximum sum is 10250 at level 2.

Example 3:

```tree

[1]

`

Input:root = [1]
0
1

Output: 1

Explanation: Only one level exists with sum 1.

Constraints

  • The number of nodes in the tree is in the range [1, 10⁴]
  • -10⁵ <= Node.val <= 10⁵

Approach

Tree Breadth-First Search pattern

1. Base Case

  • If root is null:
  • Return 0
  • Reason:
  • An empty tree has no levels

2. Initialize BFS

  • Create a queue with the root node
  • Set maxSum = -Infinity to track the maximum level sum
  • Set maxLevel = 1 to track the level with the maximum sum
  • Set currentLevel = 1

3. Process Level by Level

  • While the queue is not empty:
  • Record the levelSize
  • Initialize levelSum = 0
  • Loop levelSize times:
  • Dequeue a node
  • Add its value to levelSum
  • Enqueue left and right children if they exist

4. Track Maximum

  • After processing each level:
  • If levelSum > maxSum:
  • Update maxSum = levelSum
  • Update maxLevel = currentLevel
  • Using strict > ensures we keep the smallest level number on ties
  • Increment currentLevel

5. Return Result

  • Return maxLevel — the 1-indexed level with the maximum sum

Key Insight

  • BFS gives us natural level-by-level processing, making it easy to compute sums per level
  • Using strict greater-than (not >=) ensures we return the smallest level number when there are ties
Time
O(n)visit each node once
Space
O(w)where w is the maximum width of the tree

Visualization

Input:
DFS Traversal[1, 7, 0, 7, -8]
1707-8
output0

Press play to start DFS traversal

CurrentIn stackComplete
11 steps

Solution Code

Previous
Deepest Leaves Sum
Next
Vertical Order Traversal of a Binary Tree