Do you know what is diameter of Binary Tree? Do you know how to find the diameter of a tree? Let us try to gain some knowledge about the Binary Tree Diameter & try to know how to find the diameter of a tree.
Let’s take a daily life example and know about the diameter of the tree.
Suppose, on the sports day at your school, you have to run the circular field. But the total distance is not provided to you. Also, you have one more condition you have to complete the circle in the 3 minutes. You have the confidence to run at a high speed. But you don’t know the total distance. That is a problem for you.
So, what will you do in such cases? How will you find the distance?
In such cases, as per the mathematical theory, you will calculate the diameter of the circular ground. This will help to know about the length of the race. The same thing goes for the diameter of Binary Tree. Binary Tree diameter helps to get more knowledge about a Binary Tree. We can calculate distance of the binary tree by using nodes
Let us first try to know what is the diameter of a tree from the computer science view. Then we try to know more about the diameter of Binary Tree.
What Is The Diameter Of A Tree? Read Below
Before we talk about the diameter of Binary Tree. Let us first know about the Binary Tree briefly. A Binary Tree is a special kind of data structure. A Binary Tree is a type of Tree data structure. A tree is a non-linear data structure. It is implemented using the linear data structure.
A binary tree is a group of the tree. In this type, there will be two leaves for each node. A Binary Tree is a tree where for each node maximum of two leaves are allowed. But here that topic is not needed. The diameter of the tree is like the width of the tree. It shows the longest distance between the far-away placed nodes.
Like the height of the binary tree, the width or diameter is also calculated. For the height, the maximum distance is calculated from the root node to the lowest leaf node. But in the case of the diameter of Binary Tree, the distance is calculated in the width of the tree. This means we have to calculate a distance where a maximum number of nodes are associated from left to right. This will be clear with more definition & knowledge.
How To Find The Diameter Of A Tree? Get To Know
There is no particular theory for the diameter of a Binary Tree. We have a proper theory for the height of the binary tree. But in the case of the diameter of a binary tree, there is no proper theory is present.
For finding out the diameter of binary tree, we should have first known the three major things. Based on that, we will calculate the diameter. This calculation can’t be done in a theoretical way. This should be implemented using the programming languages. Those three fields are:
- First, we need to calculate the diameter of the left subtree of the main tree. This is also a subpart of the main function. From the step, it is quite understandable that it will do the recursion task.
- Then, we need to find out the diameter of the right subtree. This is the same step as for the left subtree. In this case, also we need to use recursion in the program.
- Then, we need to find out the longest path through the node. This step can be executed with the help of the height of the binary tree.
Among those three, we need to find out the maximum one. That will be the diameter of Binary Tree.
What Are The Types Of Diameter Of Binary Tree?
There are mainly two types of diameters present. in one case, the longest path goes by the root node of the tree. In other cases, the longest path goes without using the root node of the tree. Let us try to know more about those types.
Diameter Through Root Node:
In this case, the longest path will go through the root node of the particular tree. This means the longest path will count the root node as one of the nodes for making the longest path. For the below example, this is a simple binary tree. Here, we can able to see the longest path is going through the root node. Two leave nodes that are indicating the starting and end of the path. The total diameter is four. There are total four nodes in this path.
Diameter Not Through The Root Node:
In this case, the longest path will not use the root node. This means the longest path will be provided not using the root node. This type of diameter is very rare. The structure of the tree in such cases is very weird. For all the trees, where any subtree is more developed than the other subtree shows this type of diameter. For the below example, the root node doesn’t consider finding the longest path. In this case, also, the diameter is four. There’s n root node involved here.
Implementation Of Diameter Of Binary Tree:
To find the diameter of the binary tree, first, we need to take a structure for taking the nodes. This is the traditional approach every time we did. There is no need to discuss more of it. A function needs to be declared which will add nodes to the tree. This will help to first develop the binary tree there. After developing the binary tree, we can move forward.
After creating the binary tree, we need to implement the code for the diameter of binary tree. The diameter of binary tree is depending upon the height of the binary tree. So, we have declared one function, that helps to find out the height of the binary tree. According to the formula of the height, we have implemented the function.
Now, after that, we will start implementing the function for the diameter of binary tree. As per the theory, we will recursively find out the diameter of the left subtree. Along that, we will find out the diameter of the right subtree. Also, we need to find out the height of the tree. Among these values, whichever is the maximum one. That will be considered as the width of the binary tree. That value will be printed.
Example:
#include <stdio.h> #include <stdlib.h>
struct node { int data; struct node *left, *right; };
struct node* newNode(int data); int height(struct node* node);
int max(int a, int b) { return (a > b) ? a : b; }
int diameter(struct node* tree){ // Finding Diameter Of Tree
if (tree == NULL){return 0;}
int lh = height(tree->left); int rh = height(tree->right);
int ld = diameter(tree->left); int rd = diameter(tree->right);
return max(lh + rh + 1, max(ld, rd)); }
// Finding Height Of Tree
int height(struct node* node){
if (node == NULL){return 0;}
return 1 + max(height(node->left), height(node->right)); } // Find Maximum Height
struct node* newNode(int data){ // Function To Add Nodes
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data; node->left = NULL; node->right = NULL;
return (node);}
int main(){
struct node* root = newNode(10); root->left = newNode(12); root->right = newNode(30);
printf(“Diameter Of Tree: %d\n”,diameter(root)); // Printing The Diameter
return 0
Let us try to find out the output of the above code. This will help to understand how to find the diameter of a tree.
Output:
Conclusion:
As we saw, the diameter of Binary Tree is a very important topic.
We have to always remember what is the diameter of a tree. One of the most important operations on the Binary Tree is Binary tree diameter.
It is always advisable to clear the basics of the Data Structures. There is a need to clear the basics of the Binary Tree data structure for a better understanding of the topic.
So, hope you have liked this piece of article. Share your thoughts in the comments section and let us know if we can improve more.
Codingzap also offers a wide range of programming and coding help services for you to benefit from. Don’t miss out! Visit https://codingzap.com/ and our expert team will be there to help you out.
