Diameter Of Binary Tree In C++

// 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;
}

The diameter  is 4

// 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;
}

The diameter of the given binary tree is 4

// 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;
}

The diameter is 4