Maximum Level Sum of a Binary Tree
The key idea
Walk the tree one level at a time (BFS). Sum the values on each level, track which level has the largest sum, and return that level's 1-indexed number. On a tie, the smallest level number wins, so only update when a strictly larger sum appears.
Problem
You are given the root of a binary tree. The level of the root is 1, the level of its children is 2, and so on. Return the smallest level x such that the sum of all the node values at level x is the maximum among all levels.
Constraints
- The number of nodes in the tree is in the range [1, 10^4].
- -10^5 <= Node.val <= 10^5
Examples
Input: root = [1,7,0,7,-8,null,null]
Output: 2
Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Minimum Depth of Binary TreeEASY