Module 3 · BFS Pattern

Average of Levels in Binary Tree

EasyProblem 8 of 24 7 min read ~12 min to solve LeetCode

TreeBinary TreeBFSQueueAggregation

Asked atAmazonMicrosoftGoogleMetaAdobe

Problem Statement

Given the root of a binary tree, return the average value of the nodes on each level, ordered from top to bottom.

Input

The root of a non-empty binary tree, such as [3,9,20,null,null,15,7].

Output

A list of decimal values where each entry is the arithmetic mean of one tree level.

Constraints

•1 <= number of nodes <= 10^4
•-2^31 <= Node.val <= 2^31 - 1
•Answers within 10^-5 of the actual value are accepted

Examples

Example 1

Input:

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

Output: [3.00000,14.50000,11.00000]

Explanation: The level averages are **3 / 1 = 3**, **(9 + 20) / 2 = 14.5**, and **(15 + 7) / 2 = 11**.

Example 2

Input:

root = [3,9,20,15,7]

Output: [3.00000,14.50000,11.00000]

Explanation: Level 0 contains **3**, level 1 contains **9** and **20**, and level 2 contains **15** and **7**.

Learning Objectives

Recognise per-level aggregation as a BFS level-sweep problem.
Use the fixed queue-size template to count exactly the nodes in one level.
Compute each level sum with a long accumulator to avoid integer overflow.
Return decimal averages after dividing by the captured level size.

Intuition

Pattern Recognition

The phrase average of levels is a direct level-sweep signal. We do not need a full traversal order list; we need one aggregate per depth. BFS is the cleanest fit because the queue can isolate one level, giving both the values to sum and the count to divide by.

The common trap is using an int sum. Node values can be as large as 32-bit integers, and a level can contain many nodes. Even if the final average fits in a double, the intermediate sum can overflow an int. Use a long accumulator, then cast to double for the division.

Common mistakes

×Using an **int** accumulator and overflowing before the average is computed.
×Dividing after every node instead of summing the whole level first.
×Using the changing queue size after enqueueing children instead of the captured level size.
×Forgetting that the result type must contain decimal averages, not integer division.

Algorithm Explanation

Key idea

This is the canonical BFS level template with the per-level action changed from collecting values to computing an aggregate. At the start of a level, capture levelSize. Poll exactly that many nodes, add their values to a long sum, enqueue their children, and append sum / levelSize as a decimal average.

Level-by-level walkthrough

Use [3,9,20,null,null,15,7]. Start with queue [3]. The level size is 1. Poll 3, sum becomes 3, and enqueue 9 then 20. The average is 3 / 1 = 3.0, and the next queue is [9,20].

The next level size is 2. Poll 9, sum becomes 9. Poll 20, sum becomes 29, and enqueue 15 then 7. The average is 29 / 2 = 14.5, and the next queue is [15,7].

The final level size is 2. Poll 15 and 7, sum becomes 22, and the average is 22 / 2 = 11.0. The queue is empty, so the answer is [3.0,14.5,11.0].

Algorithm

Create an empty list of averages.
Add root to a queue if it is present.
While the queue is not empty, save levelSize = queue.size() and set sum = 0 as a long value.
Poll exactly levelSize nodes, adding each value to sum.
Enqueue each node left child then right child when present.
Append sum / levelSize as a double value.
Return the averages after all levels are processed.

Solutions

Solution: Queue BFS with long level sum

When to prefer this:

Use this as the default solution. It is the level-order template with a safer numeric accumulator and one average emitted per level.

Process the tree one level at a time with a queue. For each level, capture the size, sum exactly those node values in a long, then divide by the captured count to produce the average.

Step-by-step

Return an empty list if root is null.
Add root to a queue.
For each level, store the current queue size and initialise a long sum.
Poll exactly that many nodes, add their values to the sum, and enqueue children left-to-right.
Divide the sum by the level size using double arithmetic and append the average.

Time

O(n)

Space

O(width)

Each node contributes to exactly one level sum, and the queue is bounded by the maximum tree width.

Java implementation

Loading…

Dry Run

Sample input

root = [3,9,20,null,null,15,7]. Capture the level size before enqueueing children, then compute one average per row.

level	queue before level	sum	count	average	result so far
0	[3]	3	1	3.0	[3.0]
1	[9,20]	29	2	14.5	[3.0,14.5]
2	[15,7]	22	2	11.0	[3.0,14.5,11.0]

The count is the saved level size, not the queue size after children are enqueued. That is why the second level divides 29 by 2, even though the next queue also contains two nodes.

Interview Tips

Mention the overflow trap proactively. A strong answer says that the BFS structure is standard, but the accumulator should be long because many large 32-bit node values can appear on the same level. Also make clear that division happens after the level is complete.

Likely follow-ups

How would you return the maximum value on each level instead of the average?
How would you compute the average using DFS by tracking sum and count per depth?
How would you handle a streaming tree source where a full level may be very wide?
How would the solution change for an n-ary tree?

Key Takeaways

Per-level aggregates are natural BFS level-sweep problems.
Capture **queue.size()** before processing a level so the count is correct.
Use a **long** sum to avoid overflow from many large node values.
Convert to double only when computing the final average for the level.

Reusable template: BFS level aggregation: isolate one level with a saved queue size, accumulate the metric for those nodes, then emit one aggregate before moving to the next level.