# 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 7Output:[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 !