.png)
[Follow here] for daily coding insights
DSA Series Chapter 20 – HEIGHT OF BINARY TREE(C Version)
1. Objective
To compute the height of a Binary Tree using a recursive approach in C.
2. What is Height of a Binary Tree?
Definition (Exam-Standard)
The height of a binary tree is the number of nodes on the longest path from the root node to the deepest leaf node.
***** Some books define height in edges.*****
In this post, we follow node-based height, which is most common in Indian university syllabi.
3. Example Binary Tree
1
/ \
2 3
/ \
4 5
Height Calculation
Longest path:
1 → 2 → 4Number of nodes = 3
Hence, Height = 3
4. Key Concept Behind Height Calculation
Height depends on maximum depth
Recursively compute:
Height of left subtree
Height of right subtree
Take maximum of both
Add 1 for current node
5. Formula Used
height(node) = 1 + max(height(left), height(right))
Base Condition
height(NULL) = 0
6. Data Structure Used
Node Structure
struct Node {
int data;
struct Node* left;
struct Node* right;
};
7. Height Function (Core Logic)
int height(struct Node* root) {
if (root == NULL)
return 0;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
8. Line-by-Line Explanation
int height(struct Node* root)
Function returns an integer (height)
rootis current node
if (root == NULL)
return 0;
Empty tree has height 0
Acts as base case
int leftHeight = height(root->left);
Recursively compute left subtree height
int rightHeight = height(root->right);
Recursively compute right subtree height
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
Take maximum height
Add 1 for current node
9. Complete C Program
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int height(struct Node* root) {
if (root == NULL)
return 0;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Height of Binary Tree: %d\n", height(root));
return 0;
}
10. Output
Height of Binary Tree: 3
11. Time and Space Complexity
Time Complexity
O(n) — every node visited once
Space Complexity
O(h) — recursion stack
Worst case (skewed tree): O(n)
12. Important Exam Notes
Height is calculated using DFS (recursion)
BFS is not required
Base condition must return
0Difference between height and depth is important
13. Common Student Mistakes
Returning
-1instead of0Forgetting
+1Mixing node-based and edge-based height
Using BFS unnecessarily
14. Height vs Depth (Quick Comparison)
| Term | Meaning |
|---|---|
| Height | Longest path from root to leaf |
| Depth | Distance from root to a node |
15. Learning Outcome
After this post, students can:
Define height of a binary tree
Implement recursive height calculation
Analyze time & space complexity
Answer exam questions confidently
ALSO CHECK
ALSO CHECK
Comments
Post a Comment