Given the root of a binary tree, return the average value of the nodes on each level. Level 0 is the root, level 1 is its children, and so on.
DSA Animator › DSA Revision › Tree › Average of Levels in Binary Tree
Remember: 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. The video solves Average of Levels in Binary Tree (LeetCode 637, Easy) with the BFS Level Order pattern from the Tree topic, and you can replay every step in the interactive Average of Levels in Binary Tree animation.
Given the root of a binary tree, return the average value of the nodes on each level. Level 0 is the root, level 1 is its children, and so on.
For the tree 3, with children 9 and 20, where 20 has children 15 and 7, the answer is 3, then 14.5, then 11. Level 1 holds 9 and 20, and their average is 29 divided by 2, which is 14.5.
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 starts with 3, so level 0 has one node. Pop 3, the sum is 3, and push its children 9 and 20. The average of level 0 is 3 divided by 1, which is 3. Now the queue size is 2, so level 1 has two nodes. Pop 9, which has no children, then pop 20 and push 15 and 7. The sum is 29, so the average is 14.5. Level 2 has 15 and 7, with a sum of 22, so the average is 11. The queue is empty, and the answer is 3, 14.5 and 11.
In code, create a queue and add the root. While the queue is not empty, store its size in n, and set the sum to 0. Loop n times, poll a node, add its value to the sum, and offer its left and right child if they exist. After the loop, add sum divided by n to the result. Every node is visited once, so the time is O of n, and the queue holds at most one level.
Remember: 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.