Average of Levels in 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^-5 of the actual answer are accepted.

Example 1

Input: root = [3,9,20,null,null,15,7] Output: [3.0, 14.5, 11.0] Explanation: Level 0 avg = 3/1 = 3.0. Level 1 avg = (9+20)/2 = 14.5. Level 2 avg = (15+7)/2 = 11.0.

Example 2

Input: root = [3,9,20,15,7] Output: [3.0, 14.5, 11.0]

Constraints:

1 <= Number of nodes <= 10⁴
-2³¹ <= Node.val <= 2³¹ - 1

Solution: BFS Level Order
Complexity Analysis

Solution: BFS Level Order

Perform level-order BFS. For each level, accumulate the sum and count the nodes. Divide the sum by the count to get the average. Use a double (or long) accumulator to avoid integer overflow: node values can be up to 2³¹-1 and a level can have many nodes.

Algorithm:

Enqueue root.
While queue is non-empty, capture levelSize = queue.size().
Dequeue levelSize nodes, accumulating their values as double.
Compute average as sum / levelSize and add to result.

Java

public List<Double> averageOfLevels(TreeNode root) {
    List<Double> result = new ArrayList<>();
    if (root == null) return result;

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

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

        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);
        }

        result.add(sum / levelSize);
    }
    return result;
}

Note: Using double sum prevents integer overflow since node values can be close to Integer.MAX_VALUE and a level can have thousands of nodes.

Complexity Analysis

Time: O(n). Every node is enqueued and dequeued exactly once.
Space: O(n). The queue holds at most n/2 nodes at the widest level of the tree.