# 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++

## Leave a Reply