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

DAA: Density of a Binary Tree Algorithm