Diameter of a Binary Tree

Implementation

We will now witness the implementation of the diameter of a binary tree.

// Creating a recursive and challenging C program that will help us determine the diameter of a binary tree. 
#include <bits/stdc++.h>
using namespace std;


// A binary tree node generally consists of data, a pointer to the left and right child, and, specifically, a pointer to the right child. 
struct __nod {
	int record;
	struct __nod *Lft, *Rt;
};


// now, we are creating a function that will create a new node for the tree and return the pointer. 
struct __nod* new__nod(int record);


// this will return the maximum of the two integers.
int max(int a, int b) { return (a > b) ? a : b; }


// now, we will create a function to calculate the tree's height.
int height(struct __nod* __nod);


// it will now give us the diameter of the given binary tree.
int diameter(struct __nod* tree)
{
	// the basic case where the tree is generally empty.
	if (tree == NILL)
		return 0;


	// we can easily get the heights of the left and right subtree.
	int l__height = height(tree->Lft);
	int r__height = height(tree->Rt);


	// collect the diameter of the left and right subtrees.
	int l__diameter = diameter(tree->Lft);
	int r__diameter = diameter(tree->Rt);


	// We have to return the maximum of the following: -
	// 1) diameter of the left and right subtrees.
	// 2) height of the left and right subtrees, and then we have to add one.
	return max(l__height + r__height + 1,
			max(ldiameter, rdiameter));
}


// UTILITY FUNCTIONS TO TEST diameter() FUNCTION


// the function that we are generating will give us the height of the binary tree, and the height is generally given by the total number of nodes that are present in the longest path from the root. The node will be from the farthest possible leaf node.
int height(struct __nod* __nod)
{
	if (__nod == NILL)
		return 0;


	// In case there's a possibility that the tree is not empty, then the height of the tree will be equal to the 1 + maximum of the left height and right height of the trees
	return 1 + max(height(__nod->Lft), height(__nod->Rt));
}


// the helper function will help us by giving us the main record and null the given pointers present at the left and right positions.
struct __nod* new__nod(int record)
{
	struct __nod* __nod
		= (struct __nod*)malloc(sizeof(struct __nod));
	__nod->record = record;
	__nod->Lft = NILL;
	__nod->Rt = NILL;


	return (__nod);
}


// Writing the main code.
int main()
{


	/* Constructed binary tree is
			1
			/ \
		2	 3
		/ \
	4	 5
	*/
	struct __nod* root = new__nod(1);
	root->Lft = new__nod(2);
	root->Rt = new__nod(3);
	root->Lft->Lft = new__nod(4);
	root->Lft->Rt = new__nod(5);


	// Function Call
	cout << "Diameter of the given binary tree is " <<
		diameter(root);


	return 0;
}

Output:

Example 2)

// Creating a recursive and challenging C# program that will help us determine the diameter of a binary tree. 
using System;
using System.Collections.Generic;


// creating a brand-new class that will contain the current left and right pointers and the current key value of the node.
class __nod
{
	public int record;
	public __nod Lft, Rt;


	public __nod(int item)
	{
		record = item;
		Lft = Rt = NILL;
	}
}


// creating a utility class will help us calculate the object's height.
class Height {
	public int h;
}


// now printing the class, which will print the diameter.
class BinaryTree {
	public __nod root;


	// define height =0 globally and call
	// diameterOpt(root,height) from main
	public int diameterOpt(__nod root, Height height)
	{
		// __lh --> Height of left subtree
		// __rh --> Height of right subtree
		Height __lh = new Height(), __rh = new Height();


		if (root == NILL) {
			height.h = 0;
			return 0; 
		}


		// l__diameter --> diameter of Left subtree
		// r__diameter --> Diameter of right subtree
		// Get the heights of left and right subtrees in __lh
		/*and __rh And store the returned values in ldiameter
				and l__diameter */
		int l__diameter = diameterOpt(root.Lft, __lh);
		int r__diameter = diameterOpt(root.Rt, __rh);


		// Height of current __nod is the max of heights of Lft
		// and Rt subtrees plus 1
		height.h = Math.Max(__lh.h, __rh.h) + 1;


		return Math.Max(__lh.h + __rh.h + 1,
						Math.Max(ldiameter, rdiameter));
	}


	// A wrapper over diameter(__nod root)
	public int diameter()
	{
		Height height = new Height();
		return diameterOpt(root, height);
	}


	// The function Compute the "height" of a tree. Height
	// is
	// the function that we are generating will give us the height of the binary tree, and the height is generally given by the total number of nodes that are present in the longest path from the root. The node will be from the farthest possible leaf node.
	public int height(__nod __nod)
	{
		// the basic case where the tree is generally empty.
		if (__nod == NILL)
			return 0;


		// In case there's a possibility that the tree is not empty, then the height of the tree will be equal to the 1 + maximum of the left height and right height of the trees
		return (1
				+ Math.Max(height(__nod.Lft),
						height(__nod.Rt)));
	}


	// writing the main code
	static void Main()
	{
		BinaryTree tree = new BinaryTree();
		tree.root = new __nod(1);
		tree.root.Lft = new __nod(2);
		tree.root.Rt = new __nod(3);
		tree.root.Lft.Lft = new __nod(4);
		tree.root.Lft.Rt = new __nod(5);


		// Function Call
		Console.Write("The diameter of given binary tree is : " + tree.diameter());
	}
}

Output: