Average Value at Each Tree Level

easy tree bfs

Problem

Given the root of a binary tree, return the average value of nodes on each level, ordered from the root level downwards.

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

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