Find out the Diameter of the Binary Tree in C++
In this tutorial, we will learn how to find the diameter of a binary tree in C++.
We will also see some examples to understand the concept in a better way.
Diameter of binary tree
The diameter of the binary tree is the longest path distance between two end nodes(leaf nodes) in the tree.
Let’s see the diagram,
1 / \ 2 6 \ / \ 3 7 9 diameter is 8 (5-3-2-1-6-9-10-11). / \ \ \ 4 5 8 10 \ 11
In the above diagram, we can see the diameter of the binary tree.
Let’s see the pseudo code,
1. int lh=height of left subtree of given node. 2. int rh=height of right subtree of given node. 3. int ld=diameter of left subtree of given node. 4. int rd=diameter of right subtree of given node. 5. return max(lh+rh+1,max(ld,rd)). 6. recurse the step from 1 to 5.
Now here we will see the code implementation in c++.
How to find the diameter of a binary tree in C++
#include<iostream> #include<bits/stdc++.h> using namespace std; //structure for tree node struct Node{ int data; Node* left; Node* right; }; //function to create node Node* create(int x){ Node* temp=(Node*)malloc(sizeof(Node)); temp->data=x; temp->left=NULL; temp->right=NULL; return temp; } //function to find height from given node int height(Node* root){ if(root==NULL)return 0; int lh=height(root->left); int rh=height(root->right); return max(lh,rh)+1; } //funtion to find the diameter of the tree int findDiameter(Node* root){ if(root==NULL)return 0; int lh=height(root->left); int rh=height(root->right); int ld=findDiameter(root->left); int rd=findDiameter(root->right); return max(lh+rh+1,max(ld,rd)); } //main function int main(){ Node* root=create(1); root->left=create(2); root->left->right=create(3); root->left->right->left=create(4); root->left->right->right=create(5); root->right=create(6); root->right->left=create(7); root->right->left->right=create(8); root->right->right=create(9); root->right->right->right=create(10); root->right->right->right->right=create(11); //d is stored the return value of function findDiameter int d=findDiameter(root); cout<<"Diameter of the given binary tree is : "<<d<<endl; }
Output
Diameter of the given binary tree is : 8
You may also learn,
Leave a Reply