Skip to main content

637 - Average of Levels in Binary Tree

Difficulty: Easy | Pattern: Tree BFS (Level Order) | Company tags: Amazon, Facebook, Google

Problem Statement​

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array.

Example:

Input: root = [3,9,20,null,null,15,7]
Output: [3.0, 14.5, 11.0]
Explanation:
Level 0: 3 → avg = 3.0
Level 1: 9, 20 → avg = 14.5
Level 2: 15, 7 → avg = 11.0

Solution: BFS Level Order — O(n), O(w)​

from collections import deque

def averageOfLevels(root) -> list[float]:
    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

Dry Run​

Tree: 3 → children 9, 20 → 20's children 15, 7

LevelQueuelevel_sumavg
0[3]33.0
1[9,20]2914.5
2[15,7]2211.0

Result: [3.0, 14.5, 11.0] ✓

  • 102 - Binary Tree Level Order Traversal: collect all values per level
  • 107: level order bottom-up
  • 515: find max per level (same BFS pattern)

Edge Cases​

  • Single node → [root.val]
  • Left-skewed tree → each level has exactly one node
  • Large values: use integer sum, divide at end to avoid float accumulation errors

Complexity​

  • Time: O(n)
  • Space: O(w) where w is max width of tree