Average of Levels in Binary Tree

Problem

You are given the root of a binary tree. For every depth level of the tree — the root is level 0, its children level 1, and so on — compute the average of all node values on that level. Return the averages as a list ordered from the top level down.

Answers within 10^-5 of the true average are accepted, so ordinary floating-point division is fine.

Examples

Example 1

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

        3
       / \
      9  20
        /  \
       15   7

Output: [3.0, 14.5, 11.0]

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

Example 2

Input:  root = [1,2,3,4]
Output: [1.0, 2.5, 4.0]

Level 2 contains only the node 4, so its average is 4.0.

Constraints

• The number of nodes is in [1, 10^4] — an O(n) traversal is expected.
• -2^31 <= Node.val <= 2^31 - 1 — level sums can exceed 32-bit range, but Python ints don’t overflow.

Think about it first

TL;DR

Level-order BFS with a per-level queue snapshot — O(n) time, O(w) space where w is the max tree width.

Approach 1 — Brute force: one full pass per level

The naive idea: first compute the height of the tree, then for each level d walk the whole tree again collecting only the nodes whose depth equals d.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, List


class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        def height(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            return 1 + max(height(node.left), height(node.right))

        def collect(node: Optional[TreeNode], depth: int, target: int, vals: List[int]) -> None:
            if not node:
                return
            if depth == target:
                vals.append(node.val)
                return
            collect(node.left, depth + 1, target, vals)
            collect(node.right, depth + 1, target, vals)

        h = height(root)
        result = []
        for d in range(h):
            vals: List[int] = []
            collect(root, 0, d, vals)
            result.append(sum(vals) / len(vals))
        return result

Complexity: O(n · h) time (one traversal per level), O(h) recursion space. With n up to 10^4 and a skewed tree (h = n), that is ~10^8 node visits — wasteful when a single pass suffices.

Approach 2 — BFS level-order traversal

The insight: a queue processes nodes in the order they were discovered, so if you snapshot the queue’s length at the start of a round, you pop exactly one level and push exactly the next one. Breadth-first search (BFS) is the classical algorithm that explores a graph in expanding rings of distance from the source — in a tree, those rings are the levels.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque
from typing import Optional, List


class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        result: List[float] = []
        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)
            result.append(total / size)
        return result

Walkthrough on [3,9,20,null,null,15,7]:

Result: [3.0, 14.5, 11.0].

Complexity: O(n) time — each node enters and leaves the queue once. O(w) space for the queue, where w is the maximum width (up to n/2 in a complete tree).

Approach 3 — DFS with per-depth accumulators

The insight: you don’t need to visit a level all at once — you only need each node’s contribution filed under the right depth. A single DFS carrying the depth can accumulate sums[depth] and counts[depth], then one division per level finishes the job. Depth-first search (DFS) is the classical traversal that follows one branch to the bottom before backtracking.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, List


class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        sums: List[int] = []
        counts: List[int] = []

        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if not node:
                return
            if depth == len(sums):
                sums.append(0)
                counts.append(0)
            sums[depth] += node.val
            counts[depth] += 1
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

        dfs(root, 0)
        return [s / c for s, c in zip(sums, counts)]

Walkthrough on [3,9,20,null,null,15,7]: visiting 3 creates slot 0 (sums=[3], counts=[1]); 9 creates slot 1 (sums=[3,9]); 20 adds into slot 1 (sums=[3,29], counts=[1,2]); 15 creates slot 2, 7 adds into it (sums=[3,29,22], counts=[1,2,2]). Final division gives [3.0, 14.5, 11.0].

Complexity: O(n) time, O(h) recursion space — better than BFS’s O(w) on wide bushy trees, worse on skewed ones.

Common pitfalls

• Popping the queue until it’s empty inside the round instead of snapshotting size = len(queue) first — the levels bleed together.
• Integer division habits from other languages: in Python / already yields float, but // would silently truncate the average.
• In fixed-width languages, summing a level of 2^31 - 1 values overflows 32 bits; use a 64-bit accumulator (Python is immune, but say so in an interview).

Pattern takeaway

“Group answers by level” is the signature of BFS with a length snapshot: size = len(queue) at the top of the loop makes each while iteration process exactly one level. Keep the DFS-with-depth-indexed-lists trick in your pocket too — it turns any per-level aggregation into a single O(n) pass with O(h) space.