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,

• Build Binary Tree in C++ (Competitive Programming)