Average of Levels in Binary Tree

1. Define the problem

Average of Levels in Binary Tree

Given the root of a binary tree, return the average value of the nodes on each level , from top to bottom. Use breadth-first search with a queue to process one whole level at a time: dequeue every node currently waiting before enqueueing any of their children, and average each level as you go.

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
-2³¹ ≤ Node.val ≤ 2³¹ - 1

Example

Inputroot = [3, 9, 20, null, null, 15, 7]

Output[3, 14.5, 11]

Explanation Level 0 is [3] (average 3), level 1 is [9, 20] (average 14.5), level 2 is [15, 7] (average 11).

2. Know the words first

In plain terms

Level: All the nodes that sit the same number of steps from the root — the root itself is level 0, its children are level 1, and so on.
Queue: A first-in, first-out list. The node that has been waiting longest is always the next one processed.

3. Visualize the solution

One cell per node, in level order — values fill in as the queue reaches them

L03

L1—

L2—

Statuslevel 0

Start the queue with just the root, 3. Level 0 = [3], average 3.

What happens in this step

queue = [3]
levelSize = 1

Dequeue 3. It has no dequeued siblings this round, so sum = 3.
average = sum / levelSize = 3 / 1 = 3

Step 1 of 4

Steps to visualize

The row has one slot for each of the tree's five nodes, listed top to bottom, left to right. A slot shows — until the queue reaches that node.
Start a queue holding just the root.
Record the size of the queue — that many nodes belong to the current level.
Dequeue exactly that many nodes, summing their values and enqueueing their non-null children.
Divide the sum by the level size to get that level's average.
Repeat until the queue is empty; the list of averages, in order, is the answer.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per node, in level order — values fill in as the queue reaches them

L03

L1—

L2—

Statuslevel 0

Start the queue with just the root, 3. Level 0 = [3], average 3.

What happens in this step

queue = [3]
levelSize = 1

Dequeue 3. It has no dequeued siblings this round, so sum = 3.
average = sum / levelSize = 3 / 1 = 3

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function averageOfLevels(values) {
  function buildTree(vals) {
    if (vals.length === 0 || vals[0] === null) return null;
    const root = { val: vals[0], left: null, right: null };
    const queue = [root];
    let i = 1;
    while (queue.length > 0 && i < vals.length) {
      const node = queue.shift();
      if (i < vals.length) {
        const leftVal = vals[i++];
        if (leftVal !== null) {
          node.left = { val: leftVal, left: null, right: null };
          queue.push(node.left);
        }
      }
      if (i < vals.length) {
        const rightVal = vals[i++];
        if (rightVal !== null) {
          node.right = { val: rightVal, left: null, right: null };
          queue.push(node.right);
        }
      }
    }
    return root;
  }

  const root = buildTree(values);
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    let sum = 0;
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      sum += node.val;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(sum / levelSize);
  }

  return result;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`root = [3, 9, 20, null, null, 15, 7]`	`[3, 14.5, 11]`	example from the docstring
`root = [5]`	`[5]`	smallest valid input, a single node
`root = [1, 2, null, 3, null]`	`[1, 2, 3]`	left-skewed chain, one node per level
`root = [-5, -3, -8]`	`[-5, -5.5]`	negative values producing a fractional average
`root = [1, 1, 1, 1, 1, 1, 1]`	`[1, 1, 1]`	every node shares the same value
`root = [10, 5, 15, null, null, null, 20]`	`[10, 10, 20]`	one branch stops early while the other keeps going
`root = [0, -1, 1]`	`[0, 0]`	positive and negative values cancel out on a level

Average of Levels in Binary Tree