.png)
DSA Series Chapter 21 : COUNT TOTAL NODES IN BINARY TREE(C Version)
1. Objective
To count the total number of nodes present in a Binary Tree using a recursive Depth First Search (DFS) approach in C.
2. What Does “Counting Nodes” Mean?
Definition (Exam-Ready)
Counting total nodes in a binary tree means determining the number of all nodes (including root, internal nodes, and leaf nodes) present in the tree.
3. Example Binary Tree
1
/ \
2 3
/ \
4 5
Total Nodes
Nodes = {1, 2, 3, 4, 5}
Count = 5
4. Core Idea Behind Counting Nodes
If tree is empty → count = 0
Otherwise:
Count nodes in left subtree
Count nodes in right subtree
Add 1 for current node
5. Formula Used
count(node) = count(left) + count(right) + 1
Base Condition
count(NULL) = 0
6. Data Structure Used
Node Structure
struct Node {
int data;
struct Node* left;
struct Node* right;
};
7. Count Function (Core Logic)
int countNodes(struct Node* root) {
if (root == NULL)
return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
8. Line-by-Line Explanation
int countNodes(struct Node* root)
Function returns total number of nodes
rootrepresents current node
if (root == NULL)
return 0;
Base case
Empty tree contributes zero nodes
return 1 + countNodes(root->left) + countNodes(root->right);
1→ current nodeRecursive calls → left and right subtrees
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 countNodes(struct Node* root) {
if (root == NULL)
return 0;
return 1 + countNodes(root->left) + countNodes(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 number of nodes: %d\n", countNodes(root));
return 0;
}
10. Output
Total number of nodes: 5
11. Time and Space Complexity
Time Complexity
O(n) — every node is visited once
Space Complexity
O(h) — recursion stack
Worst case (skewed tree): O(n)
12. Important Exam Notes
DFS recursion is preferred
BFS can also be used but is not necessary
Base condition must return
0Counting nodes includes all nodes
13. Common Student Mistakes
Forgetting
+1for current nodeReturning
1for NULLConfusing total nodes with leaf nodes
Using global counters unnecessarily
14. Comparison: Height vs Count
| Feature | Height | Node Count |
|---|---|---|
| Formula | 1 + max() | 1 + left + right |
| Result | Depth | Quantity |
| Base Case | 0 | 0 |
15. Learning Outcome
After this post, students can:
Count total nodes in a binary tree
Apply recursive DFS logic
Write clean C code for tree problems
Answer exam questions confidently
ALSO CHECK
ALSO CHECK
Comments
Post a Comment