Return the average value of the nodes on each level, top to bottom, as a slice of
float64.
levelAverages(root)
Input format: level-order with x for missing children. Output the averages
space-separated (e.g. 3 14.5 11).
3 9 20 x x 15 7 // → [3, 14.5, 11]
1 2 3 // → [1, 2.5]
(empty) // → []
This extends level-grouping: instead of collecting each level's raw values, you want one summary number per level — the average. You don't need to keep every value around, just a running sum and count.
The same invariant applies: at the start of each round, the queue's length tells you exactly how many nodes belong to the level about to be processed, since children enqueued during a round belong to the next level. That size becomes your count directly — no separate counting pass.
You could reuse the level-grouping solution to build value lists per level, then loop over each computing sum and average afterward. That works, but it holds an entire list per level just to collapse it into one number. Since sum and count are exactly what an average needs, and both accumulate incrementally as you dequeue, there's no need to materialize the list at all.
An average of integers usually isn't an integer. The division needs to preserve fractional results, or a level like [9, 20] would incorrectly report 14 instead of 14.5.
Every node is still enqueued and dequeued once, so work is proportional to the number of nodes; the per-level sum and count add no meaningful overhead.
def level_averages(root):
if root is None:
return []
averages = []
queue = [root]
i = 0
while i < len(queue):
size = len(queue) - i
total = 0
for _ in range(size):
node = queue[i]
i += 1
total += node.val
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
averages.append(total / size)
return averages
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.