275. Average of Levels in Binary Tree

Process the tree level by level with a queue. For each level, sum the node values and divide by the count to get that level's average.

Idea

Averaging per level is a natural fit for a breadth-first (level-order) traversal. Using a queue, we can process exactly one level at a time by recording how many nodes are currently queued before we start expanding them.

Algorithm

1. Put root in a queue.
2. While the queue is non-empty:
   • Let count = current queue size (the number of nodes on this level).
   • Pop count nodes, summing their values and enqueuing their children.
   • Append sum / count to the result.
3. Return the list of averages.

Worked example: [3,9,20,null,null,15,7]

      3          level 0: [3]      -> 3
     / \
    9   20        level 1: [9,20]  -> 14.5
       /  \
      15   7       level 2: [15,7]  -> 11

Result: [3, 14.5, 11].

Complexity

• Time: O(n) — every node visited once.
• Space: O(w) — the queue holds at most one level (width w).

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

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