Average of Levels in Binary Tree
Average of Levels in Binary Tree: return the average value of the nodes on each level, from the root downward, as a list of doubles.
- The number of nodes in the tree is in the range [1, 10⁴]
- -2³¹ <= Node.val <= 2³¹ - 1
- Answers within 10⁻⁵ of the actual answer are accepted
Intuition
Each level needs two numbers — a running sum and a count — and the count is already known before the level starts, because it is the queue's length at that moment. So a breadth-first walk that snapshots the queue size gets the divisor for free, sums the level as it drains, and emits one average per level without storing any of the values.
Reducing each level to one number is the level-order loop with a different accumulator — sum here, max for Largest Value in Each Row, last element for Right Side View. Recognising the shared skeleton means only the reduction has to be rewritten.
Approach
Before reading on: identify where the divisor for each level comes from without collecting the level into a list. Then work out which type the running sum needs in a fixed-width language, given the stated value range.
The queue length is the divisor
At the top of each iteration the queue holds exactly the nodes of one level, so count = len(queue) is simultaneously the number of nodes to pop and the denominator of the average. That coincidence is what makes the problem clean: there is no need to collect the level into a list and take its length afterwards. Popping exactly count nodes drains the current level while the children pushed during that loop wait behind them for the next round.
Accumulate a sum, not a list
Only the total and the count are needed, so the values themselves can be discarded as they are read. Keeping a running total instead of a per-level list drops the auxiliary space for the level from O(w) to O(1), though the queue itself still holds up to O(w) nodes so the overall bound is unchanged. The gain is clarity more than memory: the code states directly that a level is being reduced to a single number rather than materialised and then reduced.
Precision and why integer division fails
Node values reach ±2³¹ - 1 and a level can hold many of them, so the sum must be held in a 64-bit type in C++ and Java or it overflows before the division ever happens. The division itself must be floating point: total / count in Python 3 already produces a float, but in Java total / count on two ints truncates, so one operand must be cast to double. Answers within 10⁻⁵ are accepted, which a double comfortably satisfies. Time is O(n), space O(w).
Solution & live demo
Common pitfalls
Overflowing the level sum
int total = 0; for (...) total += node->val;
long total = 0; for (...) total += node->val;
Values reach 2³¹ - 1, so two large nodes on one level already exceed the signed 32-bit range. The sum wraps negative and the average comes out wildly wrong before any division occurs.
Integer division truncating the average
averages.add(total / count);
averages.add((double) total / count);
In Java and C++ dividing two integers discards the fractional part, so a level of 9 and 20 averages to 14 instead of 14.5. One operand must be floating point.
Re-reading the queue length inside the level loop
for (int i = 0; i < queue.size(); i++)
int count = queue.size(); for (int i = 0; i < count; i++)
The queue grows as children are enqueued, so the loop bound keeps moving and the level absorbs nodes from the level below, corrupting both the sum and the divisor.
Edge cases
One level, and the average equals the root's value.
The sum divided by one returns that value unchanged.
Sums and averages may be negative; nothing about the method assumes positivity.
The running sum must be 64-bit or it overflows mid-level.
Every level holds one node, so the output mirrors the chain of values.