Generation Averages
A lab grows a cell culture from one starting cell. Each cell splits into at most two daughter cells. The lab records the family as a binary tree: every node holds a cell's size in micrometres, and its children are the cells it split into.
To spot whether cells shrink over time, the lab wants the average size of each generation: the starting cell, then its daughters, then theirs, and so on.
Your task
Write generationAverages(root). Return a list with the average node value of each level of the tree, from the top level down.
An empty tree gives an empty list. Trees are shown in level order, like [12, 8, 10, 7, 9, null, 15], where null marks a missing child. Your function receives real TreeNode objects with val, left and right.
generationAverages(root: TreeNode) → float[] Numbers are accepted within 1e-6.
Examples
root = [12, 8, 10, 7, 9, null, 15]
[12, 9, 10.333333333333334]
Generation 1 is just 12. Generation 2 is 8 and 10, average 9. Generation 3 is 7, 9 and 15 (the null is a missing cell), average 31 / 3 = 10.333…
root = [5]
[5]
A single starting cell that never split: one generation, average 5.
Constraints
- 0 ≤ number of cells ≤ 10,000
- -1,000,000 ≤ size ≤ 1,000,000
- Answers within 0.000001 of the expected value are accepted.
Start with brute force
Do a depth-first walk, passing the depth along, and keep a sum and a count per depth in two lists. Then divide.
That is actually O(n) and perfectly fine. It is listed here because it is a natural first idea. The breadth-first version matches the question more directly: "per level" is exactly what BFS gives you, one level at a time.
Hints
0 of 4 shown- Hint 1
Forget averages for a moment. How would you get the list of cells in generation 2? In generation 3?
- Hint 2
Each generation is exactly the children of the previous generation. If you have all of generation k in a list, you can build generation k + 1 from it.
- Hint 3
Process the tree one level at a time with a queue. The trick is knowing where one level ends and the next begins. What do you know about the queue's length right when a level starts?
- Hint 4
Put the root in a queue. While it is not empty: read
size = queue.length, pop exactlysizenodes, add up their values, push their children, then recordsum / size. Thosesizenodes were exactly one level.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Breadth-first search visits the tree level by level. The only extra step is to handle one whole level at a time so you can average it.
Trace [12, 8, 10, 7, 9, null, 15]:
- Level holds [12]. Sum 12, size 1, average 12. Children: [8, 10].
- Level holds [8, 10]. Sum 18, size 2, average 9. Children: [7, 9, 15].
- Level holds [7, 9, 15]. Sum 31, size 3, average 10.333…. No children, so stop.
The JavaScript version builds a fresh array for each level. The Python version uses one queue and reads its length at the start of each level. Both are the same idea.
function generationAverages(root) {
const result = [];
if (!root) return result;
let queue = [root];
while (queue.length > 0) {
let sum = 0;
const next = [];
for (const node of queue) {
sum += node.val;
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
result.push(sum / queue.length);
queue = next;
}
return result;
}from collections import deque
def generation_averages(root):
result = []
if root is None:
return result
queue = deque([root])
while queue:
size = len(queue)
total = 0
for _ in range(size):
node = queue.popleft()
total += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(total / size)
return resultRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.