Averages of Levels in Binary Tree

Difficulty Level Easy
Frequently asked in Facebook
Binary Tree TreeViews 1466

In averages of levels in binary tree problem we have given a binary tree, print the averages of all the nodes of every level in the tree.

Example

Input:

Averages of Levels in Binary Tree
Output: 
{10.0, 25.0, 45.0, 70.0}
Explanation:
First Level : Average = (10) / 1 = 10.0
Second Level : Average = (20 + 30) / 2 = 25.0
Third Level : Average = (40 + 50) / 2 = 45.0
Fourth Level : Average = (60 + 70 + 80) = 70.0

Algorithm for Averages of Levels in Binary Tree

Do a level order traversal and find the average of all the nodes in a level for each level of the tree.

  1. Create a queue named queue to traverse level order in the tree, push the root element to the queue.
  2. While the queue is not empty, repeat steps 3 to 6.
  3. Initialize two variables sum and total as 0, where sum represents the sum of all the nodes in a level and total represents the total number of nodes in that level. Create another queue named temp.
  4. While the queue is not empty, one by one removes all the elements from the queue, adds the value of the current element to the sum and increment total, and adds the children of the removed node to the queue temp.
  5. The average current level is (sum/total). Print it.
  6. Transfer all the elements from queue temp to queue ‘queue’.

Explanation for Averages of Levels in Binary Tree

Consider the tree,

Averages of Levels in Binary Tree

Step 1

Create a queue and push the root to it.
queue = 2

Step 2

Repeat Step 3 to 6, while the queue is not empty.

Step 3 to 6 

Iteration 1
Initialize sum and total as 0, that is, sum = 0 and total = 0
Remove the elements from queue ‘queue’, increment total and add the value of current element to total. Also push the children of removed elements to queue temp.
sum = 2, total = 1, temp = 7 -> 11
Average of this level = (2 / 1) = 2.0
Transfer all the elements of queue temp to queue ‘queue’.
queue = 7-> 11

Iteration 2
Initialize sum and total as 0, that is, sum = 0 and total = 0
Remove the elements from queue ‘queue’, increment total and add the value of current element to total. Also push the children of removed elements to queue temp.
sum = (7+ 11) = 18, total = 2, temp = 5 -> 9 -> 3
Average of this level = (18 / 2) = 9.0
Transfer all the elements of queue temp to queue ‘queue’.
queue = 5 -> 9 -> 3

Iteration 3
Initialize sum and total as 0, that is, sum = 0 and total = 0
Remove the elements from queue ‘queue’, increment total and add the value of current element to total. Also push the children of removed elements to queue temp.
sum = (5 + 9 + 3) = 17, total = 3, temp = null
Average of this level = (17 / 3) = 6.7
Transfer all the elements of queue temp to queue ‘queue’.
queue = null

As the queue becomes null, so we stop here.

JAVA Code for Averages of Levels in Binary Tree

import java.util.LinkedList;
import java.util.Queue;

public class AveragesOfAllLevelsInBinaryTree {
    // class representing node of a tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static void averages(Node root) {
        if (root == null) {
            return;
        }

        // create a queue for level order traversal
        Queue<Node> queue = new LinkedList<>();
        // add root to queue
        queue.add(root);
        
        while (!queue.isEmpty()) {
            // initialize sum and total as 0
            int sum = 0;
            int total = 0;
            // create another queue temp
            Queue<Node> temp = new LinkedList<>();
            while (!queue.isEmpty()) {
                Node curr = queue.poll();
                // add the data of current node to sum
                sum += curr.data;
                // increment total
                total++;
                // add children of curr node to queue temp
                if (curr.left != null) {
                    temp.add(curr.left);
                }
                if (curr.right != null) {
                    temp.add(curr.right);
                }
            }
            
            // average of current level is (sum / total)
            double average = (double) sum / (double) total;
            System.out.format("%.1f ", average);
            
            // move all the elements of queue temp to queue 'queue'
            queue = temp;
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        // Example tree
        Node root = new Node(10);
        root.left = new Node(20);
        root.right = new Node(30);
        root.right.left = new Node(40);
        root.right.right = new Node(50);
        root.right.left.left = new Node(60);
        root.right.right.left = new Node(70);
        root.right.right.right = new Node(80);

        averages(root);
    }
}
10.0 25.0 45.0 70.0

C++ Code for Averages of Levels in Binary Tree

#include<bits/stdc++.h> 
using namespace std;

// class representing a tree node
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = NULL;
        right = NULL;
    }
};

// function to create a new node
Node* newNode(int x) {
    Node *node = new Node(x);
    return node;
}

void averages(Node *root) {
    if (root == NULL) {
        return;
    } 
    
    // create a queue for level order traversal
    queue<Node *> q;
    // add root to queue
    q.push(root);
    
    while (!q.empty()) {
        // initialize sum and total as 0
        int sum = 0;
        int total = 0;
        // create another queue temp
        queue<Node *> temp;
        while (!q.empty()) {
            Node *curr = q.front();
            q.pop();
            // add the data of current node to sum
            sum += curr->data;
            // increment total
            total++;
            // add children of curr node to queue temp
            if (curr->left != NULL) {
                temp.push(curr->left);
            }
            if (curr->right != NULL) {
                temp.push(curr->right);
            }
        }
        
        // average of current level is (sum / total)
        double average = (double) sum / (double) total;
        printf("%.1f ", average);
        
        // move all the elements of queue temp to queue q
        q = temp;
    }
    cout<<endl;
}

int main() {
    // Example tree
    Node *root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->right->left = newNode(40);
    root->right->right = newNode(50);
    root->right->left->left = newNode(60);
    root->right->right->left = newNode(70);
    root->right->right->right = newNode(80);
    
    averages(root);
    
    return 0;
}
10.0 25.0 45.0 70.0

Complexity Analysis

Time Complexity = O(n)
Space Complexity = O(n)
where n is the total number of nodes in the tree

References

Translate »