In this blog, we will cover the recursive and iterative ways of finding the height of a tree. We will also learn working of program of both methods.
Table of Contents
Click here and learn more about Data Structures and Algorithms right from scratch:
What is the Height of a Tree?
To be able to find the height of a tree, one first needs to understand the basic structure of a tree and the terminologies related to it. The tree is a nonlinear data structure in which nodes are connected through edges. The height of a tree is a measure used to calculate its depth, or in other words, it determines the length of the longest path from the root node to the deepest leaf node. A tree comprises three essential components:
- Root Node: It is the topmost node and is used as the starting point while traversing the tree.
- Leaf Nodes: Leaf nodes are nodes without any children. They are situated at the ends of the branches of the tree.
- Edges: Edges are connections or links between nodes in a tree. The height is typically measured in terms of edges.
The height of a tree is determined by the length of the longest path from the root node to the deepest leaf node. This length is measured in terms of the number of edges traversed from the root to the deepest leaf. This determines the number of edges in the longest path of a tree. The height of a tree is a significant metric used to analyze and understand the performance of various tree-based algorithms and operations.
Let’s understand how we can find the length of a tree with the help of one example:
In the above tree, you can see that the height of this tree is 3 because from the root node `A` to the deepest leaf node `G`, there are three edges (`A` to `B` to `E` to `G`).
There are mainly two types of Height that we can determine for a tree:
- Height of a Node: Refers to the length of the longest path from that node to a leaf node.
- Height of a Tree: As previously explained, it’s the length of the longest path from the root node to the deepest leaf node.
If you want to learn Data Structures in C and master various aspects of C programming language, make sure to check out Data Structures Course from Intellipaat.
How to Find the Height of a Tree
The height of a tree can be determined using various algorithms, but in this blog, we have covered the two most common approaches, recursion and iterative methods. Here is how you can find the height of a tree using recursion in a simple binary tree:
Recursive Method to Find the Height of a Tree
This recursive approach effectively computes the height of a binary tree by traversing through its nodes and incrementally calculating the maximum height between its left and right subtrees, ultimately determining the overall height of the tree from the root node. Adjust the node structure and tree creation logic to suit your specific tree representation. Let’s understand step-by-step how we can find the height of a binary tree with the help of recursion:
Step 1: Creation of Nodeof tree Structure
struct treenode {
int val;
treenode* left;
treenode* right;
treenode(int x) : val(x), left(nullptr), right(nullptr) {}
};
Step 2: Recursive Function for Height Calculation:
int maxHeight(treenode* root) {
// Base case: if the node is null, return -1 (indicating no nodes).
if (root == nullptr) {
return -1;
}
// Recursively calculate the height of the left and right subtrees.
int leftHeight = maxHeight(root->left);
int rightHeight = maxHeight(root->right);
// Return the maximum height between the left and right subtrees, adding 1 for the current node.
return 1 + max(leftHeight, rightHeight);
}
Let’s now understand the workings of above code:
- If the node passed to the function is `nullptr`, it means there are no nodes, so return `-1` (considering the height from the empty tree is `-1`).
- After that `maxHeight` function recursively call for the left and right subtrees of the current node. This recursion will continue until it reaches the leaf nodes (nodes without children).
- Then function calculates the height of the left subtree and the right subtree. It returns the maximum height between the left and right subtrees, adding 1 for the current node. The `max` function is used to find the maximum between left and right subtree heights.
- Call the `maxHeight` function by passing the root node of the binary tree to find its height.
Example: Here is an example of the above implementation:
int main() {
// Create a sample binary tree
treenode* root = new treenode(1);
root->left = new treenode(2);
root->right = new treenode(3);
root->left->left = new treenode(4);
root->left->right = new treenode(5);
// Calculate the height of the tree
int treeHeight = maxHeight(root);
cout << "Height of the binary tree: " << treeHeight << endl;
return 0;
}
Check out Intellipaat’s C Programming Tutorial.
Iterative Method to Find the Height of a Tree
This iterative approach calculates the height of a tree by traversing level by level, incrementing the height count after processing each level. It uses a queue to maintain the nodes at each level and is an alternative method to recursively find the height of a tree. Here is a step-by-step implementation of the iterative method of tree traversal that will give us the height of tree:
Step 1: Define the Structure of Node
struct treenode {
int val;
treenode* left;
treenode* right;
treenode(int x) : val(x), left(nullptr), right(nullptr) {}
};
Step 2: Implement the Height Calculation Function:
#include <queue>
int getHeight(treenode* root) {
if (root == nullptr) {
return 0; // Return 0 if the tree is empty.
}
std::queue<treenode*> levelQueue;
levelQueue.push(root);
int height = 0;
while (!levelQueue.empty()) {
int levelSize = levelQueue.size(); // Get the number of nodes at the current level.
// Process nodes at the current level and push their children to the queue.
while (levelSize > 0) {
treenode* current = levelQueue.front();
levelQueue.pop();
if (current->left) {
levelQueue.push(current->left);
}
if (current->right) {
levelQueue.push(current->right);
}
levelSize--;
}
height++; // Increment the height after processing each level.
}
return height;
}
Let’s now understand the workings of the above function for iterative traversal:
- The `getHeight` function takes the root node of the tree as an argument.
- It initializes a queue (`levelQueue`) to perform level order traversal and a variable `height` to store the tree height.
- Level order traversal is conducted using a while loop until all levels are traversed.
- At each level, the nodes are processed, and their children (if any) are enqueued for the next level.
- The height is incremented after processing each level, eventually providing the overall height of the tree.
Go through these Top Data Structures Interview Questions and Answers to crack your interviews.
Conclusion
The height of a tree in data structures is fundamental for analyzing tree efficiency and performance. Whether calculated recursively or iteratively, the height represents the longest path from the root to the deepest leaf node. An optimal tree height ensures efficient traversal and manipulation, which emphasizes the importance of mastering techniques to determine and manage tree heights for enhanced data structure implementation. Simply put, knowing and managing tree height are essential skills that affect how well algorithms and systems perform in different areas of computer science and programming.
Get any of your queries cleared about Data Structures from Intellipaat’s Community.