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