Average of Levels in Binary Tree

The problem. Given the root of a binary tree, return the average value of the nodes on each level, from the top level down. (Answers within 10⁻⁵ of the true value are accepted.)

The tree 3, 9, 20, null, null, 15, 7. Level 0 averages 3. Level 1 averages (9 + 20) / 2 = 14.5. Level 2 averages (15 + 7) / 2 = 11. The answer is [3, 14.5, 11].

Example

Input:  root = [3, 9, 20, null, null, 15, 7]
Output: [3.0, 14.5, 11.0]

Input:  root = [3, 9, 20, 15, 7]
Output: [3.0, 14.5, 11.0]

An average needs two numbers per level: the sum and the count. Any traversal that knows each node's level can collect them — the question is how directly.

Free account

Keep reading. It's free.

Sign up to read the rest of this lesson: 6 more sections, 2 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.

Still to come

1. Brute force: one walk per level
2. Optimal: one walk, a sum and a count per depth
3. Best solution: breadth-first search, one level at a time
Comparing the three approaches
Edge cases to test
Variations

Prev Next

Mark completed

Was this helpful?

QueueFirst-in, first-out — the structure behind task scheduling and breadth-first traversal.4 lessons · 5 problems
StackLast-in, first-out — the structure behind call stacks, undo history, and expression parsing.6 lessons · 13 problems
Hash MapKey → value lookups in O(1) on average — the tool behind counting, “seen it before?” checks, prefix sums and sliding windows.4 lessons · 11 problems

Average of Levels in Binary Tree

Example

Keep reading. It's free.

Keep exploring