Average of Levels in Binary Tree: BFS Level-by-Level

Imagine you are a building inspector walking through a skyscraper floor by floor. On each floor, you note the temperature of every room and jot down the floor's average. You do not jump between floors randomly. You finish one floor before moving to the next. That is exactly what this problem asks you to do with a binary tree. Given the root, return the average value of the nodes on each level. This is LeetCode 637: Average of Levels in Binary Tree.

Why this problem matters

Average of Levels is a clean introduction to BFS level-by-level processing on trees. It reinforces the core pattern of snapshotting the queue size at the start of each level, draining exactly that many nodes, and doing something with the collected values before moving on. The "something" here is computing an average instead of collecting a list. Once you have that template down, dozens of tree problems become small variations on the same idea.

This problem also appears frequently as a warm-up in interviews because it tests whether you truly understand level-aware BFS or whether you are just memorizing solutions. If you can explain why the queue size snapshot matters, you demonstrate real understanding.

The approach

Use BFS with a queue. At the start of each level, record the current queue size. That number tells you how many nodes belong to the current level. Drain exactly that many nodes from the queue, summing their values as you go, and enqueue their children for the next level. After processing all nodes in a level, divide the sum by the count and append the result.

The key insight is the same one that powers standard level order traversal: level_size = len(queue) taken before the inner loop begins. Without that snapshot, you cannot tell where one level ends and the next begins, because children from the current level get mixed into the queue during processing.

The Python solution

from collections import deque

def average_of_levels(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level_sum = 0
        for _ in range(level_size):
            node = queue.popleft()
            level_sum += node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_sum / level_size)
    return result

Here is what each part does:

• queue = deque([root]) seeds the queue with the root node. Level 0 always has exactly one node.
• level_size = len(queue) captures how many nodes are in the current level before you start dequeuing.
• level_sum += node.val accumulates the total value for this level as you process each node.
• level_sum / level_size computes the average once the entire level has been drained.

Step-by-step walkthrough

Let's trace BFS through the tree [3, 9, 20, null, null, 15, 7]. Watch how each level gets summed and averaged before moving to the next.

Notice the rhythm. At each step, you drain the entire current level from the queue, accumulate the sum, divide by the count, and push children for the next level. Once the queue is empty, every level has contributed one average to the result list.

Complexity analysis

The space is O(n) in the worst case because the bottom level of a complete binary tree contains roughly half of all nodes. For a skewed tree (a single chain), the queue never holds more than one node. The output list takes O(d) space where d is the number of levels, but d is bounded by n.

Edge cases to watch for

• Empty tree (root is None): return an empty list []. The guard clause at the top handles this.
• Single node (no children): return [root.val]. One level, one node, and the average is just that node's value.
• Skewed tree (every node has only one child): each level has one node. The average of a single number is that number itself, so the result is [a, b, c, ...].
• Large values: node values can be large integers. Summing them in Python avoids overflow since Python handles arbitrary precision, but in languages like Java or C++ you should use long or double to avoid integer overflow when summing level values.

The building blocks

This problem is built on one core pattern: BFS level-by-level processing. The template looks like this:

from collections import deque

def bfs_by_level(root):
    queue = deque([root])
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            # process node
            for child in get_children(node):
                queue.append(child)

The snapshot level_size = len(queue) is what turns a plain BFS into a level-aware BFS. Once you internalize this template, you can apply it to a range of problems with minimal tweaks:

• Level Order Traversal (LeetCode 102): collect each level into a sublist.
• Binary Tree Right Side View (LeetCode 199): keep only the last node of each level.
• Zigzag Level Order (LeetCode 103): reverse every other level list.
• Average of Levels (this problem): compute the mean instead of collecting a list.

All of these are variations on the same brick. The BFS loop stays identical. Only the per-level post-processing changes.

From understanding to recall

You just read through a clean BFS solution and watched the queue drain level by level, computing averages along the way. It makes sense right now. But when you face a similar BFS-by-level problem in an interview next month, will you remember the level_size = len(queue) snapshot? Will you reconstruct the template from scratch without hesitation?

Understanding a pattern and being able to reproduce it under pressure are different skills. Spaced repetition bridges that gap. You practice typing the BFS level-by-level template from memory at increasing intervals. First after a day, then three days, then a week. Each repetition reinforces the snapshot trick, the deque usage, and the inner loop structure until it becomes automatic.

BFS level-by-level is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Level Order Traversal - The base BFS level-by-level pattern that this problem directly builds on
• Binary Tree Right Side View - Another BFS-by-level variation where you keep only the last node per level
• Binary Tree Zigzag Level Order Traversal - BFS with a direction flag that reverses every other level