Average of Levels in Binary Tree

Difficulty: Easy | Acceptance: 74.90% | Paid: No Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10⁻⁵ of the actual answer will be accepted.

• Examples
• Constraints
• Breadth-First Search (Level Order Traversal)
• Depth-First Search

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].

Example 2

Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]

Constraints

- The number of nodes in the tree is in the range [1, 10^4].
- -2^31 <= Node.val <= 2^31 - 1

Breadth-First Search (Level Order Traversal)

Intuition Process the tree level by level using a queue, calculating the average for each level as we go.

Steps

• Initialize a queue with the root node
• For each level, record the number of nodes and sum their values
• Divide the sum by the count to get the average for that level
• Add children of current level nodes to the queue for the next iteration

from collections import deque
from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> 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

Complexity

• Time: O(n) where n is the number of nodes
• Space: O(w) where w is the maximum width of the tree (worst case O(n))
• Notes: Intuitive approach that naturally processes nodes level by level

Depth-First Search

Intuition Traverse the tree recursively while tracking the depth, accumulating sums and counts for each level.

Steps

• Use two arrays to store sum and count of nodes at each depth
• During DFS, when visiting a node at depth d, add its value to sum[d] and increment count[d]
• After traversal, compute averages by dividing each sum by its corresponding count

from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root:
            return []
        
        level_sums = []
        level_counts = []
        
        def dfs(node: Optional[TreeNode], depth: int):
            if not node:
                return
            
            if depth == len(level_sums):
                level_sums.append(0)
                level_counts.append(0)
            
            level_sums[depth] += node.val
            level_counts[depth] += 1
            
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
        
        dfs(root, 0)
        
        return [s / c for s, c in zip(level_sums, level_counts)]

Complexity

• Time: O(n) where n is the number of nodes
• Space: O(h) where h is the height of the tree for recursion stack, plus O(h) for storing sums/counts
• Notes: More space-efficient for skewed trees, but requires additional arrays for tracking