The Average of levels in Binary Tree Leetcode problem is one of the most common interview questions. Suppose you are given a binary tree and asked to find the average of all the values at each level of the Binary tree and store the computed average value in an array. This is the task of the problem ‘Average of levels in Binary tree’ problem described on LeetCode.

Here it is important to know that we need to traverse the entire tree and compute the average of all the nodes present. A suitable algorithm for level order traversal is Breadth-First Search or BFS. Prerequisite to solve the problem ‘Average levels in Binary tree’ is to understand how the BFS algorithm works.

The BFS algorithm uses a queue as a base data structure, and we should build logic to get the average making use of the queue. So, here is a pseudo-code to get the average of levels in a binary tree:

- Start
- Enqueue the root.
- While queue is not empty
- For all elements in queue
- Sum the value

- If valid left and right childs are present push to queue

- Store the average of the current level

- For all elements in queue
- Return the array of averages
- Stop

The average time complexity of using the BFS algorithm is O(n) and its space complexity is O(n).

Now let us implement the logic in C++ to solve Average levels in a Binary tree:

class Solution { public: vector<double> averageOfLevels(TreeNode* root) { // Vector to store the averages vector<double> A; // Queue to store nodes queue<TreeNode*> Q; // 1: Push root node Q.push(root);`while(!Q.empty()){`

// 2: Get the number of nodes in queue`int Count = Q.size();`

// Variable to store sum`double Sum = 0.0;`

// 3: Loop over all elements in the queue`for(int i=0; i<Count; ++i){`

// 4: Pop the element from queue`TreeNode* N = Q.front();`

`Q.pop();`

// 5: Add the value in node`Sum += static_cast<double>(N->val);`

// 6: Push valid left and right child nodes`if(N->left) Q.push(N->left);`

`if(N->right) Q.push(N->right);`

`}`

// 7: Store the average at current level`A.push_back(Sum/Count);`

`}`

// 8: Return the array with all averages`return A;`

`}`

};

What are some of the real-world applications of BFS?

- Crawlers in Search Engine
- GPS navigation systems
- Peer to Peer networking

I am a Software Developer and Learning Enthusiast.

I love to code and create awesome technologies.

Currently I am developing MATLAB Unit Test Framework at MathWorks.

Here, I share my personal learnings and experiences that I think will benefit you 😉