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:**

**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.

- Create a queue named queue to traverse level order in the tree, push the root element to the queue.
- While the queue is not empty, repeat steps 3 to 6.
- 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.
- 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.
- The average current level is (sum/total). Print it.
- Transfer all the elements from queue temp to queue ‘queue’.

## Explanation for Averages of Levels in Binary Tree

Consider the 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