Average of Levels in Binary Tree

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

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)

Use BFS to traverse level by level. For each level, sum values using 64-bit integers, then divide by the count to produce a float.

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

• Invariant: the queue holds exactly the nodes for the current level when you start processing it.
• The queue holds exactly the current level’s nodes before each level pass.
• Processing size nodes and enqueueing children builds the next level correctly.
• Collected level results therefore match the required traversal.

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.

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.