In this tutorial, we will explore the calculation of the diameter of binary trees in C++ through illustrative examples.
The count of edges linking the most extended routes between any pair of nodes within a binary tree offers a way to compute the diameter of the binary tree. The diameter of the binary tree serves as a common metric for defining its width. The route taken relies on the binary tree's diameter and can either involve or bypass the binary tree's root. Within this path, there exist two terminal nodes, each with its own diameter that can be computed. Two approaches exist for identifying the longest route between two nodes that represent the binary tree's diameter:
- Utilizing the Root Node: This method involves passing through the binary tree's root node and considering it in the count.
- Excluding the Root Node: In this scenario, the selected path avoids the binary tree's root node and does not incorporate it within the path.
Approach 1:
The measurement of the diameter of a tree T is the greatest of the following:
- The left sub-tree length
- The right sub-tree length
- The longest path connecting leaves that runs through T's root (calculated using the heights of T's subtrees)
Filename: DiameterOfbtree.cpp
// the recursive approach
#include <bits/stdc++.h>
using namespace std;
//A binary tree node has two pointers: one to the left child and the other for the other child. It also has data.
struct node {
int data;
struct node *left, *right;
};
// function for the creation of new node
struct node* newNode(int data);
// the function which will return the maximum of the numbers
int max(int a1, int b1) { return (a1 > b1) ? a1 : b1; }
// Function for calculating the height of a tree.
int heightoftree(struct node* node);
// function for computing the diameter
int diameter_length(struct node* tree)
{
// the base case for an empty binary tree
if (tree == NULL)
return 0;
// variables for finding the length from the left and right subtree
int leftheight = heightoftree(tree->left);
int rightheight = heightoftree(tree->right);
// variables for storing diameter value
int leftdiameter = diameter_length(tree->left);
int rightdiameter = diameter_length(tree->right);
//Return the maximum of the following three
// 1) left subtree width
// 2) right subtree width
// 3) length of left subtree + length of right subtree +
// 1
return max(leftheight + rightheight + 1,
max(leftdiameter, rightdiameter));
}
// the function which is used to compute the height of a tree
//Height is the total number of nodes connecting the root node to the greatest leaf node across the longest path.
int heightoftree(struct node* node)
{
// base. condition
if (node == NULL)
return 0;
//if the tree is not empty, then increment the height
return 1 + max(heightoftree(node->left), heightoftree(node->right));
}
// A function that creates a new node with the specified data and NULL left and right references.
struct node* newNode(int data)
{
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
// Driver Code
int main()
{
/* the constructed binary tree is
4
/ \
5 6
/ \
7 8
*/
struct node* root = newNode(4);
root->left = newNode(5);
root->right = newNode(6);
root->left->left = newNode(7);
root->left->right = newNode(8);
//the function Calling
cout << "The diameter is"
<< diameter_length(root);
return 0;
}
Output:
The diameter is 4
Approach 2:
Efficient Approach:
You have the option to employ the following method to address the issue:
The previous solution could see enhancement by calculating the height in the same loop iteration instead of invoking the heightoftree function separately.
// An optimized approach for finding the diameter of the binary tree
#include <bits/stdc++.h>
using namespace std;
//A binary tree node has two pointers: one to the left child and the other for the other child.
struct node {
int data;
struct node *left, *right;
};
// creation of new node
struct node* newNode(int data);
int diameterOpts(struct node* root, int* height)
{
// lheight--> the height of the left subtree
// rheight --> the height of the right subtree
int lheight = 0, rheight = 0;
// leftdiameter --> the diameter of the left subtree
// rdiameter --> the diameter of the right subtree
int leftdiameter = 0, rightdiameter = 0;
if (root == NULL) {
*height = 0;
return 0;
}
// Calculate the heights of the left and right subtrees in lheight and // rheight. And store the results in left diameter and //right diameter.
leftdiameter = diameterOpts(root->left, &lheight);
rightdiameter = diameterOpts(root->right, &rheight);
//The total height of the current node is equal to the product of the left and right subtree heights + 1.
*height = max(lheight, rheight) + 1;
return max(lheight + rheight + 1, max(leftdiameter, rightdiameter));
}
// new node creation
struct node* newNode(int data)
{
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
int main()
{
/* the structure of the binary tree is
7
/ \
8 9
/ \
10 11
*/
struct node* root = newNode(7);
root->left = newNode(8);
root->right = newNode(9);
root->left->left = newNode(10);
root->left->right = newNode(11);
int initial_height = 0;
// printing the result as the diameter of binary tree
cout << "The diameter of the given binary tree is "
<< diameterOpts(root, &initial_height);
return 0;
}
Output:
The diameter of the given binary tree is 4
Approach 3: Using the Morris Traversal Algorithm
The Morris Traversal Technique alters the structure of a binary tree by connecting the rightmost node of the left subtree to its parent node. This method enables traversal of the tree without requiring additional space for a stack or recursive function.
To put the above idea into implementation, follow the steps below:
- Use a current_node initialized as the binary tree's root to navigate the binary tree.
- Perform the previous step if current_node is not NULL.
- If the selected node's left child is NULL , proceed to the right child.
- If the currently selected node's left child is not NULL, find the right-most node in the current node's left subtree.
- Set the right child of the rightmost elements to the presently selected node and go on to the leftmost element of the current node when it is NULL.
- If the right child is present in the rightmost node and is not NULL, visit the current node and proceed to the right child.
- Using the maximum function , determine the left and right subtree heights for every visited node, and then update the diameter to be the maximum value of the heights of the subtrees combined with the existing diameter.
- return diameter
Filename: Morris_Traversal.cpp
// code for finding the diameter of the binary tree using Morris Traversal
#include <algorithm>
#include <iostream>
using namespace std;
// Node creation
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// New node addition
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Morris traversal approach to finding the diameter of the tree
int findtheDiameter(Node* root)
{
int answer = 0;
Node* current = root;
while (current != NULL) {
if (current->left == NULL) {
current = current->right;
}
else {
Node* previ = current->left;
while (previ->right != NULL && previ->right != current)
previ = previ->right;
if (previ->right == NULL) {
previ->right = current;
current = current->left;
}
else {
previ->right = NULL;
int left_Height = 0, right_Height = 0;
Node* t = current->left;
while (t != NULL) {
left_Height++;
t = t->right;
}
t = current->right;
while (t != NULL) {
right_Height++;
t = t ->left;
}
answer = max(answer,
left_Height + right_Height + 1);
current = current->right;
}
}
}
return answer;
}
int main()
{
//Node creation in a binary tree
Node* root = newNode(5);
root->left = newNode(4);
root->right = newNode(3);
root->left->left = newNode(2);
root->left->right = newNode(1);
int d = findtheDiameter(root);
//print the diameter of the binary tree
cout << "The diameter is "
<< d << endl;
return 0;
}
Output:
The diameter is 4
Complexities:
The time complexity is O(N), where N represents the total count of nodes within a binary tree.
The space complexity of Morris Traversal is O(1) as it avoids using extra data structures such as stacks or queues. Conversely, recursive stack implementation increases space complexity to O(h), where h represents the height of the binary tree.
