Average of Levels in Binary Tree (LeetCode 637)

The problem

You get the root of a non-empty binary tree. Return a list where the i-th number is the average of all node values on level i (the root is level 0). Answers within 10⁻⁵ of the true value are accepted.

Input:      3
           / \
          9   20
             /  \
            15   7

Output: [3.0, 14.5, 11.0]

Level 0 is 3; level 1 is (9 + 20) / 2 = 14.5; level 2 is (15 + 7) / 2 = 11.0.

How to think about it

Start with brute force. Do any traversal (say DFS) and pass the depth along, adding each value into sums[depth] and counts[depth]. Then divide. That is actually O(n) and perfectly fine, but it needs two side arrays and it’s easy to get the indexing wrong.

The key insight: the question is about levels, and BFS visits a tree level by level. A queue that starts with the root and appends children as it pops nodes processes all of level 0, then all of level 1, and so on. The only extra trick is knowing where one level ends: at the start of each round, len(q) is exactly the number of nodes on the current level. Pop that many, sum them, divide by that count.

Which pattern is this? Tree BFS, level-order traversal. The tell is any phrase like “each level”, “per depth” or “row by row” on a tree.

Approach

1. Put the root in a queue.
2. While the queue is not empty:
   • take n = len(q), the size of the current level, and set s = 0,
   • pop n nodes, adding each value to s and pushing its children,
   • append s / n to the result.
3. Return the result.

Solution

from collections import deque

def average_of_levels(root):
    res = []; q = deque([root])
    while q:
        n = len(q); s = 0                         # n = number of nodes on this level
        for _ in range(n):
            node = q.popleft(); s += node.val
            if node.left: q.append(node.left)     # children belong to the next level
            if node.right: q.append(node.right)
        res.append(s / n)
    return res
# average_of_levels([3,9,20,null,null,15,7]) -> [3.0, 14.5, 11.0]

Dry run

On the example tree:

Result: [3.0, 14.5, 11.0].

Complexity

• Time: O(n). Every node is enqueued and dequeued exactly once.
• Space: O(w), where w is the widest level. The queue only ever holds about one level plus some of the next. For a complete tree that is about n/2 nodes, so O(n) in the worst case.

Edge cases and pitfalls

• Empty tree: the problem guarantees at least one node. If it didn’t, this code would try to read None.val; add if not root: return [].
• Single node: returns [root.val] as a float.
• Measuring the level inside the loop. len(q) changes as you push children. Snapshot it into n before the for.
• Integer division. In Python 3 / is true division. In Java/C++, cast to double and watch for int overflow on large sums.
• Using a list as a queue. list.pop(0) is O(n). Use collections.deque.

Related problems

• Binary Tree Level Order Traversal (LeetCode 102): the same loop, collecting the values instead of averaging them.
• Binary Tree Right Side View (LeetCode 199): the same loop, keeping only the last value of each level.
• Minimum Depth of Binary Tree (LeetCode 111): BFS that stops at the first leaf.