Do you know what is Height of Binary Tree is? Have you ever thought what is the procedure to implement the Height of Binary Tree? Let’s have the experience to find the Height of Binary Tree.
But before we start the programming aspect for the Height of Binary Tree, let’s know why it is important to know the Height of the Binary Tree.
But before that, letโs assume one scenario.
Suppose, you visited a fair near to your house. There are a lot of joy rids are present. You decided to have fun on a particular joy ride. You went to the ticket counter & booked the ticket for that ride. But when you were going to ride on it, one security guard came toward you. He said that you are not eligible for the ride.
But why you are not eligible for that ride?
They find out that your height is not fulfilling the criteria to have a ride. Means you have a short height.
So, what we can conclude from the above scenario? We find that height plays an important role in our normal life. In any particular field, height is necessary to qualify for any criteria.
The same thing goes for the Height of the Binary Tree. The height of Binary Search Tree is also important from programming aspects.
We will know more about the Height of Binary Search Tree. But before that, let us know briefly what is Binary Tree.
What is a Binary Tree? Read More
The Tree is a special kind of Data Structure. It is Non-Linear Data Structure. The Tree can be classified into more types & categories. Among them, Binary Tree is one of the important ones.
In Binary Tree, generally, every Root must have two Child Nodes. In Binary Tree, there will not be any Root will present which consists of only one Child Node. Then the tree will not be considered a Binary Tree.
Also, a Binary Tree should have a unique representation. The left Child Node of the Root will always have a lower value than the Root value. Also, the right Child Node of the Root will always have a greater value than the Root value. If any Tree follows this structure, then the Tree is considered a Binary Tree.
What is Height Of Binary Tree?
The Height of Binary Tree is an important feature. In this case, we need to find out the depth or height of Binary Tree. This means the longest distance from the Root node to the deepest Child Node.
The Child Node may be present in the Left Sub Tree or Right Sub Tree. The Child Node can be present in any Sub Tree. We need to find out the distance between that & the Root Node. Also, the Child Node must be the last leaf node of the Tree.
Calculate The Height of Binary Tree:
Calculation of the Height of Binary Tree is a very tricky & important process. The main goal of this process is to find out the longest distance between the Root Node & the last Leaf Node. For this purpose, we need to follow a set of steps. Let’s know about the steps:
- Traverse The Left Sub Tree: Here we need to traverse the Left Sub Tree of the Binary Tree. We have to visit each & every node there. We also have to count the value there. Not only the Left Sub Tree, but we also have to visit the Left of the Left Sub Tree & Right of the Left Sub Tree. We have to store the count value in a variable.
- Traverse The Right Sub Tree: Same here, we need to traverse the Right Sub Tree of the Binary Tree. We have to visit each & every node there. We also have to count the value there. Not only the Right Sub Tree, but we also have to visit the Left of the Right Sub Tree & Right of the Right Sub Tree. We have to store the count value in a variable.
- Finding The Maximum: In between the values by traversing the Left & Right Sub Tree, we need to find the maximum among them. As the maximum value will show the last Leaf Node position from the Root node. If the Left Sub Tree Traversal has the maximum value, then the last Leaf Node is in the Left Sub Tree of the Binary Tree. If the Right Sub Tree Traversal has the maximum value, then the last Leaf Node is in the Right Sub Tree of the Binary Tree.
Why Height of Binary Tree Is Important?
The Height of Binary Tree is important when you will try to solve difficult questions related to Binary Tree. As if a Binary Tree has minimum height, but it is providing all the necessary things, then it is appropriate. A Binary Tree having a long height is not a good example of a Tree.
A large height Binary Tree will cause problems from the view of Space & Time Complexity. Space & Time Complexities are two parameters to judge any code or program. If it’s large it will not only uses more space for a program but also will consume time to execute the program.
A good programmer always tries to minimize the Space & Time Complexity of any program. Then it is necessary to find out the Height of the Tree. So that the programmer can optimize the program & make a good version of the existing one.
Program to Implement Height of Binary Tree:
To implement a program to find out the Height of the Binary Tree, we need to follow the Linked List concept. As Tree in Data Structure can be created by using the concept of a Linked List. So, the first step to implementing the Height of Binary Search Tree is to make a Node. Then we will move with the help of the structure.
- Creating Structure for Binary Tree:
Here, we need to create a structure. It will consist of the value of the node. Also, it will accept the address of the Left & Right Leaf Nodes.
// Creating The Structure For A Binary Tree Node
struct node {
int data;
struct node* left, right; };
- Function to Find the Height of Binary Tree:
In this function, we will first check whether the Tree is empty or not. If it is Empty, it will return the 0 to the called function. If the Tree has Nodes, then it will first traverse the Left Sub Tree using the Recursion & save the count value. The same thing will happen to Right Sub Tree. It will also traverse the Right Sub Tree using Recursion & save the value in a variable.
Then we have to check which variable has the maximum value. The larger value will be returned to the called function, incremented by one.
// Function To Calculate The Height
int height(struct node* node){
if (node == NULL)
return 0;
else {
// Computing The Height Of Each Subtree
int lh = height(node->left);
int rh = height(node->right);
// Checking Which One Is Larger
if (lh > rh)
return (lh + 1);
else
return (rh + 1);
}}
- Function to Add New Nodes:
Using the Dynamic memory allocation, we will create a new node in this function. Also, we will link those with the existing tree. We can link them whether to the Left Side or Right Side of the Tree.
// Function To Add New Nodes
struct node* newNode(int data){
// Creating New Nodes Using Dynamic Memory Allocation
struct node* node = (struct node*)malloc(sizeof(struct node));
// Providing The Values
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);}
- Main Function:
Here, we just need to add values to the Binary Tree. After providing values to the Binary Tree, we will call the function to print the Height of Binary Tree.
// Main Function
int main(){
// Providing The Values To Node
struct node* root = newNode(1);
root->left = newNode(2);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right = newNode(3);
root->right->right = newNode(6);
root->right->left = newNode(7);
root->right->left->right = newNode(8);
// Printing The Value Of Height
printf("Height Of Tree Is: %d", height(root));
return 0;}
Above are the code snippets. If needed, you can go through the full source code provided here. The probable output of the Height of Binary Tree will be the following.
Output:
Conclusion:
As we saw Height of the Binary Tree is very important.
We should clear the basics of recursion & function calling for learning the Height of Binary Search Tree.
We should clear the Linked List concept also. That is very important to implement the Height of Binary Tree.
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.
