How do you approach Average of Levels in Binary Tree?

Process the tree one level at a time rather than node by node - collect the whole frontier, then average it.

What is the time complexity of Average of Levels in Binary Tree?

Time complexity: O(n). Space complexity: O(w) for the widest level..

What are common mistakes on Average of Levels in Binary Tree?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Average of Levels in Binary Tree

EasyData Structures

Description

Given a binary tree, return an array of the **average value of the nodes on each level**, from the root down. Round each average to 5 decimal places. The tree is given as a **level-order array with explicit nulls**, where the children of index `i` sit at `2i + 1` and `2i + 2`. An empty array is an empty tree.

Example 1

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

Output: [3, 14.5, 11]

Example 2

Input: root = [1,2,3]

Output: [1, 2.5]

Example 3

Input: root = [5]

Output: [5]

Constraints

- 1 <= number of nodes <= 10^4 - -2^31 <= Node.val <= 2^31 - 1 - Round each average to 5 decimal places.

Average of Levels in Binary Tree: approach, complexity and pitfalls

An easy trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

More Treesproblems →

If you are stuck

Show the 3-step hint ladder

Process the tree one level at a time rather than node by node - collect the whole frontier, then average it.
Take the size of the current frontier BEFORE adding children, so you know exactly which nodes belong to this level.
Sum the level's values and divide by the count, then round to 5 decimal places.

The optimal approach

Show the approach: Level-order traversal with a per-level boundary

BFS naturally visits nodes level by level, but a plain queue loses track of where one level ends. The standard technique is to snapshot the frontier: process exactly the nodes currently in it, collecting their children into a fresh frontier for the next round.

That gives you every level as a discrete group, so summing and dividing is direct. The same skeleton solves level-order traversal, right-side view, zigzag traversal, and level maximums - only what you do with each group changes, which makes it worth learning as a template rather than as one solution.

Two practical notes. Sum with a numeric type wide enough for the constraint: with up to 10^4 nodes at the full int32 range, an intermediate sum can exceed 32-bit range, which matters in languages with fixed-width ints (JavaScript and Python are safe here). And rounding is specified rather than incidental, so apply it explicitly instead of relying on the default float formatting.

Time: O(n)
Space: O(w) for the widest level.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.