Average of Levels: Aggregating Inside the Snapshot

This one is a Easy-rated classic reported from Meta, Amazon, Bloomberg interviews: "Average of Levels in Binary Tree". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Tree BFS pattern on sight. Part 4 of 11 in the Tree BFS arc.

The Problem

Given the root of a binary tree, return the average value of the nodes on each level as a list. The gentlest member of the family — and the cleanest illustration that the snapshot loop is really a per-level fold, with the level list being just one possible fold.

Input:  root = [3, 9, 20, None, None, 15, 7]
Output: [3.0, 14.5, 11.0]
Level two averages (9 + 20) / 2 = 14.5.

Recognizing the Tree BFS Pattern

Breadth-first search explores a tree or graph level by level using a queue, and its defining superpower is the level snapshot: freeze the queue length, process exactly that many nodes, and you have processed one complete level. Anything phrased per-level — level lists, level averages, rightmost visible node, shortest path in unweighted structures — is BFS by construction.

Any per-level statistic — average, max, min, count, sum — is the level-order template with the collection step swapped for an accumulation. Seeing 'per level' plus 'a number' should compile directly to this code in your head.

The Approach

Snapshot loop; instead of building a list, accumulate total across the level's nodes and append total / size after the inner loop. The snapshot size doubles as the divisor — no separate counting.

Totals can exceed 32-bit ranges on large trees in other languages; Python integers are unbounded, which is worth one sentence when asked about overflow.

Python Solution

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right


from collections import deque


def average_of_levels(root: TreeNode | None) -> list[float]:
    """Average node value per level."""
    if not root:
        return []
    result: list[float] = []
    queue: deque[TreeNode] = 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)
        result.append(total / size)
    return result

Complexity

• Time: O(n) — one visit per node
• Space: O(w) — queue only — no level lists retained

Interview Tips and Follow-Ups

• Note the space win over plain level order: aggregating drops the per-level buffer. Small, but it shows you think about what you allocate.
• Largest Value in Each Row (LeetCode 515) is this code with max — literally a one-token change. Bundle them.
• Floating point: sum-then-divide once beats running averages for both speed and accuracy — a quick numerics point if probed.

If this clicked, continue the Tree BFS arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.