Average of Levels in Binary Tree (LC 637)

Pattern: BFS — Level-by-Level Processing
Difficulty: Easy
Key Concept: For each level, sum all values at that level and divide by the count — use long (or double) for the sum to avoid integer overflow

Problem Statement

Given the root of a binary tree, return the average value of the nodes on each level, in order from shallowest level to deepest.

Input: TreeNode root.
Output: List<Double> — i-th element is the average of all node values at depth i.

Example (tree [3,9,20,null,null,15,7]):

Level 0: average of {3} → 3.0
Level 1: average of {9,20} → 14.5
Level 2: average of {15,7} → 11.0

Output: [3.0, 14.5, 11.0].

1. Algorithm & Pseudocode

function averageOfLevels(root):
    if root is null:
        return empty list

    averages = empty list
    queue = queue containing root

    while queue is not empty:
        levelSize = queue.size()
        sum = 0   // use long, not int

        repeat levelSize times:
            node = dequeue
            sum += node.val
            enqueue children if non-null

        average = (double) sum / levelSize
        append average to averages

    return averages

Brute force: For each level, copy all values into a list, then sum in a second pass — two passes per level, more allocations.

Optimal: One pass per level: running long sum + divide by levelSize once.

2. Step-by-Step Analysis (Beginner-Friendly)

Why BFS? Averages are defined per level. BFS groups nodes by depth automatically when you process levelSize nodes at a time.
Why not int sum? Node values can be up to 2^31 - 1 on LeetCode, and a level can have on the order of 10^4 nodes in worst cases. Multiplying “many large ints” overflows int. Example: 10^4 × 10^9 exceeds Integer.MAX_VALUE. long safely holds the partial sum before converting to double for division.
Why (double) sum / levelSize? Integer division would truncate. The problem expects floating averages; casting the numerator (or using 1.0 * sum) forces floating-point division.
Why is “collect then average” brute force? It is correct but allocates an extra list per level and iterates values twice; a running sum is simpler and faster in practice.
Relation to LC 102: Identical traversal; instead of storing List<Integer> per level, you store one double per level.

3. The Dry Run

Tree [3,9,20,null,null,15,7]:

Step	`levelSize`	Nodes processed (in order)	`long sum` after level	`average` = `(double)sum / levelSize`	`averages`
1	1	`3`	`3`	`3.0 / 1 = 3.0`	`[3.0]`
2	2	`9`, `20`	`29`	`29.0 / 2 = 14.5`	`[3.0, 14.5]`
3	2	`15`, `7`	`22`	`22.0 / 2 = 11.0`	`[3.0, 14.5, 11.0]`

Queue trace (abbreviated): start [3] → after level 0: [9,20] → after level 1: [15,7] → after level 2: [].

4. Java Solution

Brute Force

Store each level’s values, then sum with long and divide. Time: O(n). Space: O(n) for the extra per-level value lists plus queue.

import java.util.*;

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> averages = new ArrayList<>();
        if (root == null) {
            return averages;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> values = new ArrayList<>(levelSize);

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                values.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            long sum = 0L;
            for (int v : values) {
                sum += v;
            }
            averages.add((double) sum / values.size());
        }

        return averages;
    }
}

Optimal

Single pass per level with long sum. Time: O(n). Space: O(w) queue.

import java.util.*;

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> averages = new ArrayList<>();
        if (root == null) {
            return averages;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            long sum = 0L;

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            averages.add((double) sum / levelSize);
        }

        return averages;
    }
}

5. The “Java vs. Others” Edge

Java: long sum = 0L and (double) sum / levelSize is the standard LeetCode pattern. int accumulation is a common bug in interviews.
C++: use long long for sums; divide with static_cast<double>(sum) / levelSize.
Python: integers have arbitrary precision, so overflow is less of a talking point — but floating division (sum / n in Python 3) is still required for correct float output.
Pitfall: Using average = sum / levelSize with both int types truncates before you ever cast to double — cast before dividing, or use double for the accumulator if you accept possible precision limits (usually long + one double division is cleaner).

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(n)	Extra lists per level; still linear total
Optimal	O(n)	O(w)	One `long` sum per level; queue width w

n = nodes; w = max queue size (widest level).