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.