Average of Levels in Binary Tree
Easy · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
Given the root of a binary tree, return a list with the average value of the nodes on each level, from the top level down.
Answers within 10^-5 of the exact averages are accepted.
Examples
Input: root = [4,7,2,null,6,1,8] Output: [4.0,4.5,5.0]
The levels are [4], [7,2] and [6,1,8].
Input: root = [10,-10] Output: [10.0,-10.0]
Each level has one node.
Input: root = [2147483647,2147483647,2147483647] Output: [2147483647.0,2147483647.0]
The second level's sum, 4294967294, does not fit in a 32-bit integer: sum in 64 bits.
Constraints
- The number of nodes is in the range [1, 10^4]
- -2^31 <= Node.val <= 2^31 - 1
Approaches
- Walk the whole tree once per depth — time O(n · h), space O(n)
Follow-up
Can you do it with depth-first search instead? Keep a running sum and count per depth in two arrays indexed by depth; the averages are their quotients at the end.
Related problems
Start free on Cariara · Coding problems · System design studio
