Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.
root = [3,9,20,null,null,15,7][3.0, 14.5, 11.0]root = [1,2,3,4,5][1.0, 2.5, 4.5]root = [1][1.0]sz = queue.size() — node count at current level; init sum = 0sz nodes: sum += node.val, enqueue non-null childrenavg = sum / sz, add to result; loop until queue emptyExtending level order BFS — instead of collecting values, we accumulate a running sum. By capturing sz = queue.size() before the inner loop, we guarantee sum contains exactly the current level's nodes. avg = sum / sz gives the level average. Without the snapshot, children added during iteration would corrupt the level boundary and inflate the sum.
You could first collect every node with its depth, group them by depth, and then average each group. That works, but it needs an extra map and a second pass. A breadth first search already visits the tree one level at a time, so we can average as we go.
Use a queue, and start with just the root in it. At the start of each round, the queue holds exactly one full level. So read the queue size first, and that tells you how many nodes belong to this level. Pop exactly that many nodes, add up their values, and push their children for the next round. When the round ends, divide the sum by the count, and that is the average for this level.
The queue size at the start of a round is the size of that level. Use a double for the sum, so large values do not overflow.
Run the animation above on your own input, or watch the 2:35 video explanation of Average of Levels in Binary Tree with a dry run and Java code.