C++ program for Density of Binary Tree in One Traversal

In this tutorial, we will generate the density of Binary Tree in one traversal using C++. Before going on our main topic, we should have a clear concept of what Binary tree is and how to calculate it’s height and size.

If you don’t know what Binary tree is, don’t worry, we will discuss all these prerequisite concepts from scratch.

Binary Tree: Definition

In Short, a binary tree is a data structure that is defined as a collection of elements called nodes. The topmost element of a binary tree is called the root node.

Each node may contain at most 2 children. Node with zero children is called a terminal node or leaf node.

Height and Size of a tree

The height of a tree is the height of its root node from the most downward leaf node.

The size of a tree is the number of nodes in that tree.

Density of Binary Tree in One Traversal

Density of Binary Tree = Size of the tree / Height of the tree

Examples:

Example 1:
   10
  /  \
 20   30
Height of the tree: 2
Size of the tree: 3
Density: 1.5

Example 2:
     10
      \
       20
        \
         30
Height of the tree = 3
Size of the tree = 3 
Density: 1

Meanwhile the implementation of two traversal approach is easy. Just we have to find the size in one traversal and then find the height in another traversal.

But to solve it in one traversal, we have to compute the size of Binary Tree along with its height.

Following is the implementation Using C++ program.

#include<bits/stdc++.h> 
struct Node 
{ 
    int data; 
    Node *left,*right; 
}; 
  
Node* newNode(int data) 
{ 
    Node* node = new Node; 
    node->data = data; 
    node->left = node->right = NULL; 
    return node; 
} 
int heighAndSize(Node* node, int &size) 
{ 
    if (node==NULL) 
        return 0; 

    int l = heighAndSize(node->left, size); 
    int r = heighAndSize(node->right, size); 
    size++; 
    return (l > r) ? l + 1 : r + 1; 
} 
float density(Node* root) 
{     if (root == NULL) 
        return 0;  
    int size = 0;
    int _height = heighAndSize(root, size); 
  
    return (float)size/_height; 
}

int main() 
{ 
    Node* root = newNode(10); 
    root->left = newNode(20); 
    root->right = newNode(30);
    printf("Density is %f", 
           density(root)); 
    return 0; 
}

Output: 

Density is 1.500000