Average of Levels in Binary Tree

Easy#637tree nodes

You get the root of a binary tree. For every level, from the top down, find the average of its values and return the averages as a list. Our example is the tree [5, 3, 8, 2, 6, none, 10] in level order: 5 on top, 3 and 8 below it, then 2, 6 and 10 — the answer is [5, 5.5, 6].

637 Average of Levels in Binary TreeWalkthrough · 1×

Example: find the average of each level of the tree 5 / 3, 8 / 2, 6, 10.

5382610queuefront on the left—
not reachedin the queue, this levelin the queue, next levelcurrentadded to its sum

No averages yet: result = []

01/51
restart · back · play · step
Speed
1function averageOfLevels(root):
2 result = []
3 queue = [root]
4 while queue is not empty:
5 size = queue.size
6 sum = 0
7 repeat size times:
8 node = queue.popFront()
9 sum = sum + node.val
10 if node.left is not none:
11 queue.pushBack(node.left)
12 if node.right is not none:
13 queue.pushBack(node.right)
14 result.add(sum / size)
15 return result
state
result
[]
queue
–
size
–
sum
–
node
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. When a level starts, the queue holds exactly that level: the level above is all taken out, and none of the level below is in yet.
  2. size is read before the level puts its children in the queue, so the loop takes exactly the level and the sum is divided by its own count.
  3. Each node adds its value to the sum of its own level once, so every average is over the right values.

Complexity

Time O(n): each node enters and leaves the queue once. Memory O(w): the queue holds at most about two levels, w is the widest one.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.