Interview question: Average of Levels in a Binary Tree

Problem Statement

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Original link from leetcode

Constraints: Nodes’ values are 32-bit signed integer

Example:

Input:
3
/ \
9 20
/ \
15 7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

Visual Example:

Analysis

Breadth First Search (BFS) algorithm seems like a perfect fit here, since we start with the root, we explore the neighbours first, before moving to the next level neighbours. Of course this is accomplished using a Queue.

In a basic BFS, we will naturally traverse the tree level by level. But still, we need a way to stop at the end of each level to calculate the average. This can be solved by queuing a sentinel node (null node) at the end of each level. 
Whenever we pop the null node. We calculate the average of that level and we append it to the result array.
Also if you think about it (You really have to think about), pop-ing the null node means that you visited all the child nodes and already appended their children to the queue. So logically we have to append another Null node to the queue.

If you still can’t get the trick, I suggest you check the visualisation of the algorithm further down.

Implementation

Visualisation


If you think that there’s an interesting interview question/Problem that might need cool explanation and fancy visualisation like this one 😉 please comment it below.
Show your love and support by clicking the little heart !