# 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;
}
{
return 0;
int size = 0; // To store size
return (float)size / hei;
}
int main()
{
`Density of given binary tree is- 1.5`