How to solve ‘Average of levels in Binary Tree – Leetcode’ in Ten seconds?

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
• 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