Maximum Level Sum of a Binary Tree
Medium · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
The root of a binary tree is on level 1, its children on level 2, their children on level 3, and so on. The sum of a level is the sum of the values of all nodes on it.
Given the root, return the level with the largest sum. If several levels share the largest sum, return the smallest of them.
Values can be negative, so a deeper level is not always worth more.
Examples
Input: root = [1,7,0,7,-8,null,null] Output: 2
Level 1 sums to 1, level 2 to 7 + 0 = 7, level 3 to 7 - 8 = -1.
Input: root = [989,null,10250,98693,-89388,null,null,null,-32127] Output: 2
The sums are 989, 10250, 98693 - 89388 = 9305 and -32127.
Input: root = [-4,-5,-6] Output: 1
Level 1 sums to -4, level 2 to -11.
Constraints
- 1 <= number of nodes <= 10^4
- -10^5 <= Node.val <= 10^5
Approaches
- Breadth-first, level by level — time O(n), space O(w)
Follow-up
The same walk answers any per-level score. The use cases score levels by their average (compared exactly, without floating point) and work on a tree of any shape given as a parent array.
Related problems
Start free on Cariara · Coding problems · System design studio
