Find average of levels in binary tree
The given problem involves finding the average of values at each level in a binary tree. We are required to create a program that calculates the average of node values for each level in the binary tree and then prints the result.
Problem Statement
The task is to implement a program that takes a binary tree as input, calculates the average of node values for each level, and then prints the averages of all levels.
Explanation with Example
Consider the following binary tree:
1
/ \
/ \
2 3
/ / \
4 9 6
/ \ \ \
7 8 4 10
Idea to Solve the Problem
To find the average of values at each level in a binary tree, we can perform a level-order traversal. During the traversal, we keep track of the level of each node and maintain a sum of node values for each level. We also keep a count of nodes at each level. After visiting all nodes at a level, we calculate the average for that level and store it in a result array. Finally, we print the averages for all levels.
Pseudocode
- Define the TreeNode class to represent binary tree nodes with data, left, and right pointers.
- Define the QueueNode class to represent nodes of a custom queue, which stores TreeNode elements along with their levels.
- Implement the MyQueue class with methods to enqueue, dequeue, check if the queue is empty, etc.
- Create the BinaryTree class with methods to find the average of levels in the tree (level_average).
- In the level_average() method:
- If the binary tree is empty, print "Empty Binary Tree" and return.
- Initialize a temporary node (node) to the root of the binary tree.
- Initialize some counter variables: level_counter to 1, node_level to 0, and sum to 0.0.
- Create a new queue (MyQueue queue).
- Enqueue the root node (node) along with level_counter into the queue.
- Initialize an array to store the averages for each level.
- While the queue is not empty, do the following:
- Dequeue the current node along with its level from the front of the queue.
- If the dequeued node has a left child, enqueue it into the queue along with its level+1.
- If the dequeued node has a right child, enqueue it into the queue along with its level+1.
- If the node_level is not equal to level_counter, calculate the average for the current level and store it in the result array.
- Update the level_counter to the current node_level and reset the sum to 0.0.
- Add the data of the dequeued node to the sum.
- Calculate and store the average for the last level.
- Print the result array containing the averages for each level.
Code Solution
// C program
// Find average of levels in binary tree
#include <stdio.h>
#include <stdlib.h>
//Node of binary tree
struct Node
{
int data;
struct Node *left, *right;
};
struct MyQueue
{
int level;
struct Node *element;
struct MyQueue *next;
};
//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes
struct Node * insert(int data)
{
//create dynamic memory to new binary tree node
struct Node * new_node = (struct Node * ) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set node value
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
printf("Memory Overflow\n");
}
//return reference
return new_node;
}
//Create a queue node and returns this node
struct MyQueue *enqueue(struct Node *tree_node)
{
//Make a new Queue node
struct MyQueue *new_node = (struct MyQueue * ) malloc(sizeof(struct MyQueue));
if (new_node != NULL)
{
//Set node values
new_node->element = tree_node;
new_node->next = NULL;
}
else
{
printf("Memory Overflow\n");
}
return new_node;
}
//Remove a queue elements
void dequeue(struct MyQueue ** front)
{
if ( * front != NULL)
{
struct MyQueue *remove = *front;
//Visit to next node
*front = remove->next;
remove->element = NULL;
remove->next = NULL;
//free node
free(remove);
remove = NULL;
}
}
//Find the average of all levels in a given binary tree
void level_average(struct Node *root)
{
if (root != NULL)
{
//make MyQueue pointers
struct MyQueue *front = NULL, *tail = NULL;
//Get first node of tree
front = enqueue(root);
//Start level of first node is one
front->level = 1;
tail = front;
int level_counter = 1;
struct Node *node = root;
double sum = 0.0;
printf("\n Level Averages ");
//Execute loop until the queue is not empty
while (front != NULL)
{
node = front->element;
if (node->left != NULL)
{
//Add new left child node
tail->next = enqueue(node->left);
tail->next->level = front->level + 1;
tail = tail->next;
}
if (node->right != NULL)
{
//Add new right child node
tail->next = enqueue(node->right);
tail->next->level = front->level + 1;
tail = tail->next;
}
if (front->level != level_counter)
{
printf("\n Level %d -> %lf",level_counter,(sum/level_counter));
//When level change
sum = 0.0;
level_counter = front->level;
}
sum += node->data;
//remove element of queue
dequeue( &front);
}
tail = NULL;
//last level
printf("\n Level %d -> %lf \n",level_counter,sum/level_counter);
}
else
{
printf("Empty Linked List\n");
}
}
int main()
{
struct Node *root = NULL;
/* Construct Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 9 6
/ \ \ \
7 8 4 10
*/
//Add node
root = insert(1);
root->left = insert(2);
root->right = insert(3);
root->right->right = insert(6);
root->right->left = insert(9);
root->left->left = insert(4);
root->left->left->left = insert(7);
root->left->left->right = insert(8);
root->right->left->right = insert(4);
root->right->right->right = insert(10);
//find level average
level_average(root);
return 0;
}Output
Level Averages
Level 1 -> 1.000000
Level 2 -> 2.500000
Level 3 -> 6.333333
Level 4 -> 7.250000/*
Java program
Find average of levels in binary tree
*/
//Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
public TreeNode element;
public QueueNode next;
public int level;
public QueueNode(TreeNode element, int level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
public QueueNode front;
public QueueNode tail;
public MyQueue()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
public void enqueue(TreeNode element, int level)
{
QueueNode new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
//Add node at last position
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
public boolean is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
//set initial tree root to null
this.root = null;
}
//Display Inorder view of binary tree
public void inorder(TreeNode node)
{
if (node != null)
{
// Executing left subtree
this.inorder(node.left);
//Print node value
System.out.print(" " + node.data);
// Executing right subtree
this.inorder(node.right);
}
}
public void level_average()
{
if (this.root == null)
{
System.out.print("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
TreeNode node = this.root;
//Define some useful counter variables
int level_counter = 1;
int node_level = 0;
double sum = 0.0;
//Create a Queue
MyQueue queue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, level_counter);
System.out.print("\n Level Averages ");
//Execute loop until the queue is not empty
while (queue.is_empty() == false)
{
node = queue.front.element;
node_level = queue.front.level;
if (node.left != null)
{
//Add left node
queue.enqueue(node.left, node_level + 1);
}
if (node.right != null)
{
//Add right node
queue.enqueue(node.right, node_level + 1);
}
if (node_level != level_counter)
{
System.out.print("\n Level " + level_counter + " -> " + (sum / level_counter));
//When level change
sum = 0.0;
level_counter = queue.front.level;
}
sum += node.data;
//remove element into queue
queue.dequeue();
}
//last level
System.out.print("\n Level " + level_counter + " -> " + (sum / level_counter));
}
}
public static void main(String[] args)
{
//Make object of Binary Tree
BinaryTree tree = new BinaryTree();
/* Construct Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 9 6
/ \ \ \
7 8 4 10
*/
//Add node
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(6);
tree.root.right.left = new TreeNode(9);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(8);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(10);
tree.inorder(tree.root);
tree.level_average();
}
}Output
7 4 8 2 1 9 4 3 6 10
Level Averages
Level 1 -> 1.0
Level 2 -> 2.5
Level 3 -> 6.333333333333333
Level 4 -> 7.25//Include header file
#include <iostream>
using namespace std;
/*
C++ program
Find average of levels in binary tree
*/
//Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
//set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Queue Node
class QueueNode
{
public: TreeNode *element;
QueueNode *next;
int level;
QueueNode(TreeNode *element, int level)
{
this->element = element;
this->next = NULL;
this->level = level;
}
};
//Define custom queue class
class MyQueue
{
public: QueueNode *front;
QueueNode *tail;
MyQueue()
{
this->front = NULL;
this->tail = NULL;
}
//Add a new node at last of queue
void enqueue(TreeNode *element, int level)
{
QueueNode *new_node = new QueueNode(element, level);
if (this->front == NULL)
{
//When first node of queue
this->front = new_node;
}
else
{
//Add node at last position
this->tail->next = new_node;
}
this->tail = new_node;
}
//Delete first node of queue
void dequeue()
{
if (this->front != NULL)
{
if (this->tail == this->front)
{
this->tail = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
}
}
bool is_empty()
{
if (this->front == NULL)
{
return true;
}
else
{
return false;
}
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
//set initial tree root to null
this->root = NULL;
}
//Display Inorder view of binary tree
void inorder(TreeNode *node)
{
if (node != NULL)
{
// Executing left subtree
this->inorder(node->left);
//Print node value
cout << " " << node->data;
// Executing right subtree
this->inorder(node->right);
}
}
void level_average()
{
if (this->root == NULL)
{
cout << "\n Empty Binary Tree \n";
}
else
{
//Get top node in tree
TreeNode *node = this->root;
//Define some useful counter variables
int level_counter = 1;
int node_level = 0;
double sum = 0.0;
//Create a Queue
MyQueue queue = MyQueue();
//Add first node at the level of one
queue.enqueue(node, level_counter);
cout << "\n Level Averages ";
//Execute loop until the queue is not empty
while (queue.is_empty() == false)
{
node = queue.front->element;
node_level = queue.front->level;
if (node->left != NULL)
{
//Add left node
queue.enqueue(node->left, node_level + 1);
}
if (node->right != NULL)
{
//Add right node
queue.enqueue(node->right, node_level + 1);
}
if (node_level != level_counter)
{
cout << "\n Level " << level_counter << "->" << (sum / level_counter);
//When level change
sum = 0.0;
level_counter = queue.front->level;
}
sum += node->data;
//remove element into queue
queue.dequeue();
}
//last level
cout << "\n Level " << level_counter << "->" << (sum / level_counter);
}
}
};
int main()
{
//Make object of Binary Tree
BinaryTree tree = BinaryTree();
/*Construct Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 9 6
/ \ \ \
7 8 4 10
*/
//Add node
tree.root = new TreeNode(1);
tree.root->left = new TreeNode(2);
tree.root->right = new TreeNode(3);
tree.root->right->right = new TreeNode(6);
tree.root->right->left = new TreeNode(9);
tree.root->left->left = new TreeNode(4);
tree.root->left->left->left = new TreeNode(7);
tree.root->left->left->right = new TreeNode(8);
tree.root->right->left->right = new TreeNode(4);
tree.root->right->right->right = new TreeNode(10);
tree.inorder(tree.root);
tree.level_average();
return 0;
}Output
7 4 8 2 1 9 4 3 6 10
Level Averages
Level 1->1
Level 2->2.5
Level 3->6.33333
Level 4->7.25//Include namespace system
using System;
/*
C# program
Find average of levels in binary tree
*/
//Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
public TreeNode element;
public QueueNode next;
public int level;
public QueueNode(TreeNode element, int level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
public QueueNode front;
public QueueNode tail;
public MyQueue()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
public void enqueue(TreeNode element, int level)
{
QueueNode new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
//Add node at last position
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
public Boolean is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
//set initial tree root to null
this.root = null;
}
//Display Inorder view of binary tree
public void inorder(TreeNode node)
{
if (node != null)
{
// Executing left subtree
this.inorder(node.left);
//Print node value
Console.Write(" " + node.data);
// Executing right subtree
this.inorder(node.right);
}
}
public void level_average()
{
if (this.root == null)
{
Console.Write("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
TreeNode node = this.root;
//Define some useful counter variables
int level_counter = 1;
int node_level = 0;
double sum = 0.0;
//Create a Queue
MyQueue queue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, level_counter);
Console.Write("\n Level Averages ");
//Execute loop until the queue is not empty
while (queue.is_empty() == false)
{
node = queue.front.element;
node_level = queue.front.level;
if (node.left != null)
{
//Add left node
queue.enqueue(node.left, node_level + 1);
}
if (node.right != null)
{
//Add right node
queue.enqueue(node.right, node_level + 1);
}
if (node_level != level_counter)
{
Console.Write("\n Level " + level_counter + " -> " + (sum / level_counter));
//When level change
sum = 0.0;
level_counter = queue.front.level;
}
sum += node.data;
//remove element into queue
queue.dequeue();
}
//last level
Console.Write("\n Level " + level_counter + " -> " + (sum / level_counter));
}
}
public static void Main(String[] args)
{
//Make object of Binary Tree
BinaryTree tree = new BinaryTree();
/* Construct Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 9 6
/ \ \ \
7 8 4 10
*/
//Add node
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(6);
tree.root.right.left = new TreeNode(9);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(8);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(10);
tree.inorder(tree.root);
tree.level_average();
}
}Output
7 4 8 2 1 9 4 3 6 10
Level Averages
Level 1 -> 1
Level 2 -> 2.5
Level 3 -> 6.33333333333333
Level 4 -> 7.25<?php
/*
Php program
Find average of levels in binary tree
*/
//Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
function __construct($data)
{
//set node value
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
// Queue Node
class QueueNode
{
public $element;
public $next;
public $level;
function __construct($element, $level)
{
$this->element = $element;
$this->next = null;
$this->level = $level;
}
}
//Define custom queue class
class MyQueue
{
public $front;
public $tail;
function __construct()
{
$this->front = null;
$this->tail = null;
}
//Add a new node at last of queue
public function enqueue($element, $level)
{
$new_node = new QueueNode($element, $level);
if ($this->front == null)
{
//When first node of queue
$this->front = $new_node;
}
else
{
//Add node at last position
$this->tail->next = $new_node;
}
$this->tail = $new_node;
}
//Delete first node of queue
public function dequeue()
{
if ($this->front != null)
{
if ($this->tail == $this->front)
{
$this->tail = null;
$this->front = null;
}
else
{
$this->front = $this->front->next;
}
}
}
public function is_empty()
{
if ($this->front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
public $root;
function __construct()
{
//set initial tree root to null
$this->root = null;
}
//Display Inorder view of binary tree
public function inorder($node)
{
if ($node != null)
{
// Executing left subtree
$this->inorder($node->left);
//Print node value
echo " ". $node->data;
// Executing right subtree
$this->inorder($node->right);
}
}
public function level_average()
{
if ($this->root == null)
{
echo "\n Empty Binary Tree \n";
}
else
{
//Get top node in tree
$node = $this->root;
//Define some useful counter variables
$level_counter = 1;
$node_level = 0;
$sum = 0.0;
//Create a Queue
$queue = new MyQueue();
//Add first node at the level of one
$queue->enqueue($node, $level_counter);
echo "\n Level Averages ";
//Execute loop until the queue is not empty
while ($queue->is_empty() == false)
{
$node = $queue->front->element;
$node_level = $queue->front->level;
if ($node->left != null)
{
//Add left node
$queue->enqueue($node->left, $node_level + 1);
}
if ($node->right != null)
{
//Add right node
$queue->enqueue($node->right, $node_level + 1);
}
if ($node_level != $level_counter)
{
echo "\n Level ". $level_counter ." -> ". (($sum / $level_counter));
//When level change
$sum = 0.0;
$level_counter = $queue->front->level;
}
$sum += $node->data;
//remove element into queue
$queue->dequeue();
}
//last level
echo "\n Level ". $level_counter ." -> ". (($sum / $level_counter));
}
}
}
function main()
{
//Make object of Binary Tree
$tree = new BinaryTree();
/* Construct Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 9 6
/ \ \ \
7 8 4 10
*/
//Add node
$tree->root = new TreeNode(1);
$tree->root->left = new TreeNode(2);
$tree->root->right = new TreeNode(3);
$tree->root->right->right = new TreeNode(6);
$tree->root->right->left = new TreeNode(9);
$tree->root->left->left = new TreeNode(4);
$tree->root->left->left->left = new TreeNode(7);
$tree->root->left->left->right = new TreeNode(8);
$tree->root->right->left->right = new TreeNode(4);
$tree->root->right->right->right = new TreeNode(10);
$tree->inorder($tree->root);
$tree->level_average();
}
main();Output
7 4 8 2 1 9 4 3 6 10
Level Averages
Level 1 -> 1
Level 2 -> 2.5
Level 3 -> 6.3333333333333
Level 4 -> 7.25/*
Node Js program
Find average of levels in binary tree
*/
//Binary Tree node
class TreeNode
{
constructor(data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
constructor(element, level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
constructor()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
enqueue(element, level)
{
var new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
//Add node at last position
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
constructor()
{
//set initial tree root to null
this.root = null;
}
//Display Inorder view of binary tree
inorder(node)
{
if (node != null)
{
// Executing left subtree
this.inorder(node.left);
//Print node value
process.stdout.write(" " + node.data);
// Executing right subtree
this.inorder(node.right);
}
}
level_average()
{
if (this.root == null)
{
process.stdout.write("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
var node = this.root;
//Define some useful counter variables
var level_counter = 1;
var node_level = 0;
var sum = 0.0;
//Create a Queue
var queue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, level_counter);
process.stdout.write("\n Level Averages ");
//Execute loop until the queue is not empty
while (queue.is_empty() == false)
{
node = queue.front.element;
node_level = queue.front.level;
if (node.left != null)
{
//Add left node
queue.enqueue(node.left, node_level + 1);
}
if (node.right != null)
{
//Add right node
queue.enqueue(node.right, node_level + 1);
}
if (node_level != level_counter)
{
process.stdout.write("\n Level " + level_counter + " -> " + ((sum / level_counter)));
//When level change
sum = 0.0;
level_counter = queue.front.level;
}
sum += node.data;
//remove element into queue
queue.dequeue();
}
//last level
process.stdout.write("\n Level " + level_counter + " -> " + ((sum / level_counter)));
}
}
}
function main()
{
//Make object of Binary Tree
var tree = new BinaryTree();
/* Construct Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 9 6
/ \ \ \
7 8 4 10
*/
//Add node
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(6);
tree.root.right.left = new TreeNode(9);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(8);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(10);
tree.inorder(tree.root);
tree.level_average();
}
main();Output
7 4 8 2 1 9 4 3 6 10
Level Averages
Level 1 -> 1
Level 2 -> 2.5
Level 3 -> 6.333333333333333
Level 4 -> 7.25# Python 3 program
# Find average of levels in binary tree
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# set node value
self.data = data
self.left = None
self.right = None
# Queue Node
class QueueNode :
def __init__(self, element, level) :
self.element = element
self.next = None
self.level = level
# Define custom queue class
class MyQueue :
def __init__(self) :
self.front = None
self.tail = None
# Add a new node at last of queue
def enqueue(self, element, level) :
new_node = QueueNode(element, level)
if (self.front == None) :
# When first node of queue
self.front = new_node
else :
# Add node at last position
self.tail.next = new_node
self.tail = new_node
# Delete first node of queue
def dequeue(self) :
if (self.front != None) :
if (self.tail == self.front) :
self.tail = None
self.front = None
else :
self.front = self.front.next
def is_empty(self) :
if (self.front == None) :
return True
else :
return False
class BinaryTree :
def __init__(self) :
# set initial tree root to null
self.root = None
# Display Inorder view of binary tree
def inorder(self, node) :
if (node != None) :
# Executing left subtree
self.inorder(node.left)
# Print node value
print(" ", node.data, end = "")
# Executing right subtree
self.inorder(node.right)
def level_average(self) :
if (self.root == None) :
print("\n Empty Binary Tree \n", end = "")
else :
# Get top node in tree
node = self.root
# Define some useful counter variables
level_counter = 1
node_level = 0
sum = 0.0
# Create a Queue
queue = MyQueue()
# Add first node at the level of one
queue.enqueue(node, level_counter)
print("\n Level Averages ", end = "")
# Execute loop until the queue is not empty
while (queue.is_empty() == False) :
node = queue.front.element
node_level = queue.front.level
if (node.left != None) :
# Add left node
queue.enqueue(node.left, node_level + 1)
if (node.right != None) :
# Add right node
queue.enqueue(node.right, node_level + 1)
if (node_level != level_counter) :
print("\n Level ", level_counter ," -> ", ((sum / level_counter)), end = "")
# When level change
sum = 0.0
level_counter = queue.front.level
sum += node.data
# remove element into queue
queue.dequeue()
# last level
print("\n Level ", level_counter ," -> ", ((sum / level_counter)), end = "")
def main() :
# Make object of Binary Tree
tree = BinaryTree()
# Construct Binary Tree
# -----------------------
# 1
# / \
# 2 3
# / / \
# 4 9 6
# / \ \ \
# 7 8 4 10
#
# Add node
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.right.right = TreeNode(6)
tree.root.right.left = TreeNode(9)
tree.root.left.left = TreeNode(4)
tree.root.left.left.left = TreeNode(7)
tree.root.left.left.right = TreeNode(8)
tree.root.right.left.right = TreeNode(4)
tree.root.right.right.right = TreeNode(10)
tree.inorder(tree.root)
tree.level_average()
if __name__ == "__main__": main()Output
7 4 8 2 1 9 4 3 6 10
Level Averages
Level 1 -> 1.0
Level 2 -> 2.5
Level 3 -> 6.333333333333333
Level 4 -> 7.25# Ruby program
# Find average of levels in binary tree
# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# set node value
self.data = data
self.left = nil
self.right = nil
end
end
# Queue Node
class QueueNode
# Define the accessor and reader of class QueueNode
attr_reader :element, :next, :level
attr_accessor :element, :next, :level
def initialize(element, level)
self.element = element
self.next = nil
self.level = level
end
end
# Define custom queue class
class MyQueue
# Define the accessor and reader of class MyQueue
attr_reader :front, :tail
attr_accessor :front, :tail
def initialize()
self.front = nil
self.tail = nil
end
# Add a new node at last of queue
def enqueue(element, level)
new_node = QueueNode.new(element, level)
if (self.front == nil)
# When first node of queue
self.front = new_node
else
# Add node at last position
self.tail.next = new_node
end
self.tail = new_node
end
# Delete first node of queue
def dequeue()
if (self.front != nil)
if (self.tail == self.front)
self.tail = nil
self.front = nil
else
self.front = self.front.next
end
end
end
def is_empty()
if (self.front == nil)
return true
else
return false
end
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
# set initial tree root to null
self.root = nil
end
# Display Inorder view of binary tree
def inorder(node)
if (node != nil)
# Executing left subtree
self.inorder(node.left)
# Print node value
print(" ", node.data)
# Executing right subtree
self.inorder(node.right)
end
end
def level_average()
if (self.root == nil)
print("\n Empty Binary Tree \n")
else
# Get top node in tree
node = self.root
# Define some useful counter variables
level_counter = 1
node_level = 0
sum = 0.0
# Create a Queue
queue = MyQueue.new()
# Add first node at the level of one
queue.enqueue(node, level_counter)
print("\n Level Averages ")
# Execute loop until the queue is not empty
while (queue.is_empty() == false)
node = queue.front.element
node_level = queue.front.level
if (node.left != nil)
# Add left node
queue.enqueue(node.left, node_level + 1)
end
if (node.right != nil)
# Add right node
queue.enqueue(node.right, node_level + 1)
end
if (node_level != level_counter)
print("\n Level ", level_counter ," -> ", (sum / level_counter))
# When level change
sum = 0.0
level_counter = queue.front.level
end
sum += node.data
# remove element into queue
queue.dequeue()
end
# last level
print("\n Level ", level_counter ," -> ", (sum / level_counter))
end
end
end
def main()
# Make object of Binary Tree
tree = BinaryTree.new()
# Construct Binary Tree
# -----------------------
# 1
# / \
# 2 3
# / / \
# 4 9 6
# / \ \ \
# 7 8 4 10
#
# Add node
tree.root = TreeNode.new(1)
tree.root.left = TreeNode.new(2)
tree.root.right = TreeNode.new(3)
tree.root.right.right = TreeNode.new(6)
tree.root.right.left = TreeNode.new(9)
tree.root.left.left = TreeNode.new(4)
tree.root.left.left.left = TreeNode.new(7)
tree.root.left.left.right = TreeNode.new(8)
tree.root.right.left.right = TreeNode.new(4)
tree.root.right.right.right = TreeNode.new(10)
tree.inorder(tree.root)
tree.level_average()
end
main()Output
7 4 8 2 1 9 4 3 6 10
Level Averages
Level 1 -> 1.0
Level 2 -> 2.5
Level 3 -> 6.333333333333333
Level 4 -> 7.25/*
Scala program
Find average of levels in binary tree
*/
//Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Queue Node
class QueueNode(var element: TreeNode,
var next: QueueNode,
var level: Int)
{
def this(element: TreeNode, level: Int)
{
this(element, null, level);
}
}
//Define custom queue class
class MyQueue(var front: QueueNode,
var tail: QueueNode)
{
def this()
{
this(null, null);
}
//Add a new node at last of queue
def enqueue(element: TreeNode, level: Int): Unit = {
var new_node: QueueNode = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
//Add node at last position
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
def dequeue(): Unit = {
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
def is_empty(): Boolean = {
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
//Display Inorder view of binary tree
def inorder(node: TreeNode): Unit = {
if (node != null)
{
// Executing left subtree
this.inorder(node.left);
//Print node value
print(" " + node.data);
// Executing right subtree
this.inorder(node.right);
}
}
def level_average(): Unit = {
if (this.root == null)
{
print("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
var node: TreeNode = this.root;
//Define some useful counter variables
var level_counter: Int = 1;
var node_level: Int = 0;
var sum: Double = 0.0;
//Create a Queue
var queue: MyQueue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, level_counter);
print("\n Level Averages ");
//Execute loop until the queue is not empty
while (queue.is_empty() == false)
{
node = queue.front.element;
node_level = queue.front.level;
if (node.left != null)
{
//Add left node
queue.enqueue(node.left, node_level + 1);
}
if (node.right != null)
{
//Add right node
queue.enqueue(node.right, node_level + 1);
}
if (node_level != level_counter)
{
print("\n Level " + level_counter + " -> " + ((sum / level_counter)));
//When level change
sum = 0.0;
level_counter = queue.front.level;
}
sum += node.data;
//remove element into queue
queue.dequeue();
}
//last level
print("\n Level " + level_counter + " -> " + ((sum / level_counter)));
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Make object of Binary Tree
var tree: BinaryTree = new BinaryTree();
/* Construct Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 9 6
/ \ \ \
7 8 4 10
*/
//Add node
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(6);
tree.root.right.left = new TreeNode(9);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(8);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(10);
tree.inorder(tree.root);
tree.level_average();
}
}Output
7 4 8 2 1 9 4 3 6 10
Level Averages
Level 1 -> 1.0
Level 2 -> 2.5
Level 3 -> 6.333333333333333
Level 4 -> 7.25/*
Swift 4 program
Find average of levels in binary tree
*/
//Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
//set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
// Queue Node
class QueueNode
{
var element: TreeNode? ;
var next: QueueNode? ;
var level: Int;
init(_ element: TreeNode? , _ level : Int)
{
self.element = element;
self.next = nil;
self.level = level;
}
}
//Define custom queue class
class MyQueue
{
var front: QueueNode? ;
var tail: QueueNode? ;
init()
{
self.front = nil;
self.tail = nil;
}
//Add a new node at last of queue
func enqueue(_ element: TreeNode? , _ level : Int)
{
let new_node: QueueNode? = QueueNode(element, level);
if (self.front == nil)
{
//When first node of queue
self.front = new_node;
}
else
{
//Add node at last position
self.tail!.next = new_node;
}
self.tail = new_node;
}
//Delete first node of queue
func dequeue()
{
if (self.front != nil)
{
if (self.tail === self.front)
{
self.tail = nil;
self.front = nil;
}
else
{
self.front = self.front!.next;
}
}
}
func is_empty() -> Bool
{
if (self.front == nil)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
//set initial tree root to null
self.root = nil;
}
//Display Inorder view of binary tree
func inorder(_ node: TreeNode? )
{
if (node != nil)
{
// Executing left subtree
self.inorder(node!.left);
//Print node value
print(" ", node!.data, terminator: "");
// Executing right subtree
self.inorder(node!.right);
}
}
func level_average()
{
if (self.root == nil)
{
print("\n Empty Binary Tree \n", terminator: "");
}
else
{
//Get top node in tree
var node: TreeNode? = self.root;
//Define some useful counter variables
var level_counter: Int = 1;
var node_level: Int = 0;
var sum: Double = 0.0;
//Create a Queue
let queue: MyQueue = MyQueue();
//Add first node at the level of one
queue.enqueue(node, level_counter);
print("\n Level Averages ", terminator: "");
//Execute loop until the queue is not empty
while (queue.is_empty() == false)
{
node = queue.front!.element;
node_level = queue.front!.level;
if (node!.left != nil)
{
//Add left node
queue.enqueue(node!.left, node_level + 1);
}
if (node!.right != nil)
{
//Add right node
queue.enqueue(node!.right, node_level + 1);
}
if (node_level != level_counter)
{
print("\n Level ", level_counter ," -> ", (sum / Double(level_counter)), terminator: "");
//When level change
sum = 0.0;
level_counter = queue.front!.level;
}
sum += Double(node!.data);
//remove element into queue
queue.dequeue();
}
//last level
print("\n Level ", level_counter ," -> ", (sum / Double(level_counter)), terminator: "");
}
}
}
func main()
{
//Make object of Binary Tree
let tree: BinaryTree = BinaryTree();
/* Construct Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 9 6
/ \ \ \
7 8 4 10
*/
//Add node
tree.root = TreeNode(1);
tree.root!.left = TreeNode(2);
tree.root!.right = TreeNode(3);
tree.root!.right!.right = TreeNode(6);
tree.root!.right!.left = TreeNode(9);
tree.root!.left!.left = TreeNode(4);
tree.root!.left!.left!.left = TreeNode(7);
tree.root!.left!.left!.right = TreeNode(8);
tree.root!.right!.left!.right = TreeNode(4);
tree.root!.right!.right!.right = TreeNode(10);
tree.inorder(tree.root);
tree.level_average();
}
main();Output
7 4 8 2 1 9 4 3 6 10
Level Averages
Level 1 -> 1.0
Level 2 -> 2.5
Level 3 -> 6.33333333333333
Level 4 -> 7.25Resultant Output Explanation
The program will print the data of each node in the binary tree in an inorder traversal. For the given binary tree, the inorder traversal will be: 7 4 8 2 1 9 4 3 6 10.
Then, the program will print the averages of each level in the binary tree. In the provided example, the averages are:
Level Averages
Level 1 -> 1.0
Level 2 -> 2.5
Level 3 -> 6.333333333333333
Level 4 -> 7.25
This output shows the average values for each level in the binary tree. For example, the average at level 1 is 1.0, at level 2 is 2.5, and so on.
Time Complexity
The time complexity of the level_average() method is O(N), where N is the number of nodes in the binary tree. This is because each node is visited once during the level-order traversal, and enqueueing and dequeueing operations on the queue take constant time. Overall, the time complexity of the entire program is O(N).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment