.png)
DSA Series Chapter 22 : COUNT LEAF NODES IN BINARY TREE(C Version)
1. Objective
To count the total number of leaf nodes in a Binary Tree using a recursive approach in C.
2. Definition (Exam-Ready)
A leaf node in a binary tree is a node that has no left child and no right child.
3. Example Binary Tree
1
/ \
2 3
/ \
4 5
Leaf Nodes
Leaf nodes: 4, 5, 3
Leaf Count = 3
4. Identification Rule for Leaf Node
A node is a leaf node if:
left == NULL AND right == NULL
5. Core Logic (Recursive)
If tree is empty → return
0If current node is a leaf → return
1Otherwise:
Count leaf nodes in left subtree
Count leaf nodes in right subtree
6. Recursive Formula
leafCount(node) =
0 if node == NULL
1 if node is a leaf
leafCount(left) + leafCount(right) otherwise
7. Structure Definition
struct Node {
int data;
struct Node* left;
struct Node* right;
};
8. Function to Count Leaf Nodes
int countLeafNodes(struct Node* root) {
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
9. Line-by-Line Explanation
if (root == NULL)
return 0;
Base case
Empty tree contributes zero leaf nodes
if (root->left == NULL && root->right == NULL)
return 1;
Checks if current node is a leaf
If yes, count it as one leaf
return countLeafNodes(root->left) + countLeafNodes(root->right);
Recursively count leaf nodes from both subtrees
Add their results
10. 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 countLeafNodes(struct Node* root) {
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
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("Total leaf nodes: %d", countLeafNodes(root));
return 0;
}
11. Output
Total leaf nodes: 3
12. Time and Space Complexity
Time Complexity
O(n)
Every node is visited once.
Space Complexity
O(h) (recursive call stack)
Balanced tree →
O(log n)Skewed tree →
O(n)
13. Important Exam Notes
Leaf node = degree 0
Uses DFS recursion
Do not confuse leaf nodes with internal nodes
Works for any binary tree (not BST-specific)
14. Common Beginner Mistakes
Counting nodes with one child as leaf
Forgetting base case (
root == NULL)Using global variables unnecessarily
Confusing leaf count with total node count
15. Difference: Total Nodes vs Leaf Nodes
| Aspect | Total Nodes | Leaf Nodes |
|---|---|---|
| Includes root | Yes | Only if root is leaf |
| Child condition | Any | No children |
| Formula | 1 + L + R | Conditional |
16. Learning Outcome
After this post, learners can:
Identify leaf nodes correctly
Implement leaf counting in C
Answer exam questions confidently
Extend logic to internal node counting
ALSO CHECK
ALSO CHECK
Comments
Post a Comment