Find Density of Binary Tree in One Traversal in C++

In this tutorial, you will learn to find the density of a given binary tree in one traversal using C++C. At the end of the tutorial, you will have knowledge of the formula to find density and the code.

The formula for Density of Binary Tree

Density = Size/Height

Size is the number of elements in the tree whereas,
Height is the number of branches.

Examples

This is an example of finding the density.

Input: 
   1
  / \
 2   3

Output: 1.5
Height of given tree = 2
Size of given tree = 3

Input: 
     1
    /   
   2   
 /
3
Output: 1
Height of given tree = 3
Size of given tree = 3

Program: Density of Binary Tree in One Traversal in C++

Let’s look at the code for finding the density of a binary tree in one traversal

#include<iostream>
#include<stdio.h> 
using namespace std; 
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 p = heighAndSize(node->left, size); 
	int q = heighAndSize(node->right, size); 
	size++;
	return (p > q) ? p + 1 : q + 1; 
}
float density(Node* head)
{
	if (head == NULL)
		return 0; 
	int size = 0; // To store size
	int hei = heighAndSize(head, size); 
	return (float)size / hei;
}
int main() 
{ 
	Node* head = newNode(1);
	head->left = newNode(2); 
	head->right = newNode(3);
	cout << "Density of given binary tree is- " << density(head);
	return 0;
}

Output:

Density of given binary tree is- 1.5

Also: Perfect Binary Tree Specific Level Order Traversal in C++