Average of Levels in Binary Tree
The key idea
Process the tree one level at a time. A breadth-first sweep naturally groups nodes by depth: before starting each round, the queue holds exactly that level's nodes, so you can sum them, divide by the count, then enqueue all their children for the next round.
Problem
Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. The answer for each level is the sum of that level's node values divided by the number of nodes on the level. Answers within 10^-5 of the actual answer are accepted.
Constraints
- The number of nodes in the tree is in the range
[1, 10^4]. -2^31 <= Node.val <= 2^31 - 1
Examples
Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]
Complexity
Time: O(n) Space: O(w)
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
- 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
- Maximum Level Sum of a Binary TreeMEDIUM
- Minimum Depth of Binary TreeEASY