Average of Levels in Binary Tree

EasyTree BFSGrokkingJuniorOpen on LeetCodeUpdated Nov 11, 2026

You're given the root of a non-empty binary tree. Return a list holding the average value of the nodes on each level, starting with the root's level and ending with the deepest one. A level's average is the sum of its values divided by the number of nodes on it, returned as a floating-point number. Answers within 10^-5 of the true average are accepted.

Examples

root = [3,9,20,null,null,15,7] returns [3.00000,14.50000,11.00000]

Level 1 averages (9 + 20) / 2 = 14.5.

Level 0 holds only 3. Level 1 holds 9 and 20, which average to 14.5. Level 2 holds 15 and 7, which average to 11.

root = [3,9,20,15,7] returns [3.00000,14.50000,11.00000]

Here 15 and 7 are children of 9. Each level still holds the same values, so the averages match the first example.

Constraints

1 <= number of nodes <= 10^4
-2^31 <= Node.val <= 2^31 - 1

Hints

Hint 1

Each answer depends on one whole level at a time. What traversal order hands you the nodes level by level?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Breadth-first search (BFS) with a queue visits the tree one level at a time. At the start of each level, the queue holds exactly that level's nodes, so record its size, pop that many nodes, add up their values, and push their children for the next round. Append sum / size and repeat until the queue is empty. Every node is visited once, and the queue holds at most one level, which can be about half the tree.

Time

O(n)

Space

O(n)

Pitfall

Summing into an int in Java overflows when a level holds several values near 2^31 - 1, so use a long. And capture the queue's size before the inner loop: reading it as the loop bound while you push children mixes the next level into this one.

Solutions

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> out = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            long sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            out.add((double) sum / size);
        }
        return out;
    }
}

from collections import deque
from typing import List, Optional

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        out = []
        queue = deque([root])
        while queue:
            size = len(queue)
            total = 0
            for _ in range(size):
                node = queue.popleft()
                total += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            out.append(total / size)
        return out