Average of Levels in Binary Tree

Return the average value of the nodes on each level in a binary tree.

Why this is worth learning

A level average requires a per-level accumulator and a frozen count. Integer division and cross-level sums are independent sources of subtle errors.

Before coding: one-minute experiment

For a level containing values 2 and 3, what is the average and why is integer division wrong?

Function signature

func AverageOfLevels(root *TreeNode) []float64

Inputs / outputs

• root: root of the tree.
• Return: slice where each entry is the average of one level.

Example

    3
   / \
  9  20
     / \
    15  7
Output: [3.0, 14.5, 11.0]

Constraints

• 0 <= number of nodes <= 100_000
• node values fit in 32-bit signed int

Core idea (near-solution)

Collecting every level and then averaging works, but the calculation only needs two summaries: sum and count. Save the frontier size before adding children and accumulate exactly those values. A divisor based on a changing queue length would mix depths. Integer division would discard the fraction, so convert operands before dividing. The signed-32-bit values and at most 100000 nodes bound the sum safely in int64 and below 2^53 in magnitude before its float64 conversion.

Invariant: the queue holds exactly the nodes for the current level when you start processing it.

Algorithm (step-by-step)

1. If root is nil, return empty.
2. Push root into queue.
3. While queue not empty:
   • Let n be queue size.
   • Pop n nodes, add their values to sum, enqueue children.
   • Append float64(sum)/float64(n) to result.

Correctness sketch

At each level boundary, freeze the number of nodes and reset the sum to zero. Processing exactly that many queued nodes adds each value from that depth once and no values from other depths. The arithmetic mean is therefore this sum divided by the frozen count, converted to floating point. Enqueuing children preserves the next-level order and coverage invariant but does not change the current divisor. Induction supplies the correct mean for every depth. For the stated 32-bit node values and at most 100000 nodes, an int64 or exact float64 integer accumulation is safe for each level sum.

Trace (hand walkthrough)

Example input:
    3
   / \
  9  20
     / \
    15  7
Output: [3.0, 14.5, 11.0]

Walk:
- level 0 sum=3 count=1 -> avg 3.0
- level 1 sum=9+20=29 count=2 -> avg 14.5
- level 2 sum=15+7=22 count=2 -> avg 11.0

Pitfalls to avoid

• Forgetting to reset the sum and count for each level.
• Using int for sums when node values can overflow; use int64.

Debugging lens

Use unequal-width levels, negative values, and large 32-bit values. Compare floating results with an explicit tolerance; do not require a particular decimal string formatting.

Complexity

• Time: O(n)
• Extra space: O(n).

Implementation notes (Go)

• Use int64 for sums, then convert to float64.
• Reset sum/count each level; capture level size up front.

Reconstruction checkpoint

A level contains [−3,2,2]. What sum, divisor, and result should be used? Would float64(sum/count) and float64(sum)/float64(count) agree?

Return to Binary Tree BFS · Module quiz