DAA: Density of a Binary Tree Algorithm
The Density of a Binary Tree Algorithm
The density of a binary tree is defined as the ratio of the tree’s size to the tree’s height.
The height of the tree is two, and the size of the tree is 3. Hence the ratio is 1.5
Approach 1
The approach one is simple and quite obvious. Calculate the size of the tree and the height of the tree separately. After that, calculate the ratio.
C++ code:
#include<bits/stdc++.h>
using namespace std;
// Create a binary tree structure
struct Node
{
int data; // the data of the tree
Node *left, *right; // the left and right of the node
};
Node* insertNode(int data) // Allocate memory of new node
{
Node* node = new Node; // create object of node class
node->data = data; // initialise data
node->left = node->right = NULL; // make left and right as NULL
return node;
}
int heigh_And_Size(Node* node, int &size) // compute the size and height of the tree
{
if (node==NULL) // if tree is NULL i.e, base case
return 0;
int l = heigh_And_Size(node->left, size); // recur left subtree for height
int r = heigh_And_Size(node->right, size); // recur right subtree for height
size++; // increment size
return (l > r) ? l + 1 : r + 1; // calculate height from the larger one
}
float density(Node* root) // find density of the tree
{
if (root == NULL)
return 0;
int size = 0; // To store size
// Finds height and size
int _height = heighAndSize(root, size); // get the size and height
return (float)size/_height;
}
int main() // Main function
{
Node* root = insertNode(10);
root->left = insertNode(20);
root->right = insertNode(30);
printf("The density of the binary tree calculated is %f", density(root));
return 0;
}
Output:
The density of the binary tree calculated is 1.5