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
Hint 1
The answer is organized by level. Which traversal naturally visits a tree one level at a time?
Hint 2
With a queue, everything currently in the queue at the start of a round is exactly one level. Snapshot its length before you start popping.
Hint 3
Alternatively, do a DFS carrying the current depth, and accumulate `sums[depth]` and `counts[depth]` in two lists; divide at the end.
TL;DR
Level-order BFS with a per-level queue snapshot — O(n) time, O(w) space where w is the max tree width.
The examples use this tree:
flowchart TD
A["3 (level 0)"] --> B["9 (level 1)"]
A --> C["20 (level 1)"]
C --> D["15 (level 2)"]
C --> E["7 (level 2)"]
Approach 1 — Brute force: one full pass per level
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
def averageOfLevels(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
A queue processes nodes in the order they were discovered. Snapshot the queue’s length at the start of a round, and you pop exactly one level while pushing exactly the next. Breadth-first search (BFS) 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
def averageOfLevels(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]:
| Round | Queue at start | size | total | append |
|---|
| 1 | [3] | 1 | 3 | 3.0 |
| 2 | [9, 20] | 2 | 29 | 14.5 |
| 3 | [15, 7] | 2 | 22 | 11.0 |
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
You don’t need to visit a level all at once; you only need each node’s value added to 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) 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
def averageOfLevels(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. The DFS-with-depth-indexed-lists variant does the same per-level aggregation in a single O(n) pass with O(h) space.