Problem #637: Average of Levels in Binary Tree

Intuition & Strategy Breakdown

Use BFS level order traversal. Compute sum of node values at each level divided by level node count.

Python Solution

import collections

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root:
            return []
        
        res = []
        queue = collections.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)
            
            res.append(level_sum / level_size)
            
        return res

Java Solution

class Solution {
    public List averageOfLevels(TreeNode root) {
        List result = new ArrayList<>();
        if (root == null) return result;
        
        Queue queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            double levelSum = 0;
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelSum += node.val;
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            result.add(levelSum / levelSize);
        }
        
        return result;
    }
}