Coding Interview PatternsAverage of Levels in Binary Tree
EasyTree Breadth-First Search

Average of Levels in Binary Tree

Explanation & Solution

Practice Problem

Description

Given the root of a non-empty binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10⁻⁵ of the actual answer will be accepted.

Examples

Example 1:

```tree

[3, 9, 20, null, null, 15, 7]

`

Input:root = [3, 9, 20, null, null, 15, 7]
0
3
1
9
2
20
3
null
4
null
5
15
6
7
Output:[3, 14.5, 11]
0
3
1
14.5
2
11

Explanation: Level 0: average of [3] = 3. Level 1: average of [9, 20] = 14.5. Level 2: average of [15, 7] = 11.

Example 2:

```tree

[3, 9, 20, 15, 7]

`

Input:root = [3, 9, 20, 15, 7]
0
3
1
9
2
20
3
15
4
7
Output:[3, 14.5, 11]
0
3
1
14.5
2
11

Example 3:

```tree

[1]

`

Input:root = [1]
0
1
Output:[1]
0
1

Constraints

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

Approach

Tree Breadth-First Search pattern

1. Handle Empty Tree

  • If root is null:
  • Return []
  • Note: per constraints the tree is non-empty, but we handle this defensively

2. Initialize BFS

  • Create result = [] for level averages
  • Create queue = [root] with head = 0 pointer

3. Process Level by Level

  • While the queue is not empty:
  • Calculate levelSize = queue.length - head
  • Initialize sum = 0 for the current level

4. Sum All Values in the Level

  • Loop levelSize times:
  • Dequeue node via queue[head++]
  • Add node.val to sum
  • Enqueue left and right children if they exist

5. Compute and Store Average

  • After processing all nodes in a level:
  • Push sum / levelSize into result
  • This gives the arithmetic mean of the level

6. Return Result

  • After all levels, return result
  • Each element is the average of one level, from top to bottom

Key Insight

  • Standard BFS with level-size tracking
  • Accumulate a running sum per level, then divide by count
  • Using a head pointer avoids costly shift() — O(1) dequeue
Time
O(n)visit each node once
Space
O(n)queue holds at most one level of nodes

Visualization

Input:
DFS Traversal[3, 9, 20, 15, 7]
3920157
output0

Press play to start DFS traversal

CurrentIn stackComplete
11 steps

Solution Code

Previous
Binary Tree Right Side View
Next
Minimum Depth of Binary Tree