Average of Levels in Binary Tree

easy tree bfs

Problem

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 will be accepted.

Run a level-order BFS. At the start of each iteration the queue length equals the size of the current level — drain exactly that many nodes, sum them, divide by the count, and enqueue all their children.

Inputlevel-order: [3, 9, 20, _, _, 15, 7]

Output[3.0, 14.5, 11.0]

level-order ('_' for null)

from collections import deque
def average_of_levels(root):
    out = []
    q = deque([root])
    while q:
        n = len(q)
        s = 0
        for _ in range(n):
            node = q.popleft()
            s += node.val
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        out.append(s / n)
    return out

function averageOfLevels(root) {
  const out = [];
  const q = [root];
  while (q.length) {
    const n = q.length;
    let s = 0;
    for (let i = 0; i < n; i++) {
      const node = q.shift();
      s += node.val;
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    out.push(s / n);
  }
  return out;
}

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> out = new ArrayList<>();
        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            int n = q.size();
            double s = 0;
            for (int i = 0; i < n; i++) {
                TreeNode node = q.poll();
                s += node.val;
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            out.add(s / n);
        }
        return out;
    }
}

vector<double> averageOfLevels(TreeNode* root) {
    vector<double> out;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        int n = q.size();
        double s = 0;
        for (int i = 0; i < n; i++) {
            auto node = q.front(); q.pop();
            s += node->val;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        out.push_back(s / n);
    }
    return out;
}

Explanation

To average each level, we need to process the tree one level at a time. A queue and a level-order (BFS) sweep make that easy.

The key trick is at the start of each loop iteration: the queue contains exactly the nodes of the current level. So we record n = len(q) and then pop exactly n nodes, summing their values and enqueuing all their children.

After draining those n nodes, the children we added form the next level, and s / n is this level's average, which we append to the answer.

Capturing n before the inner loop is important — the queue grows as we add children, so we must freeze the count first.

Example: level 0 is just [3] → average 3. Level 1 is [9, 20] → (9+20)/2 = 14.5. Level 2 is [15, 7] → 11. Result: [3.0, 14.5, 11.0].

Time: O(n) Space: O(w) queue width