.png)
DSA Series Chapter 23 : COUNT INTERNAL NODES IN BINARY TREE(C Version)
1. Objective
To count the total number of internal nodes in a Binary Tree using a recursive approach in C.
2. Definition (Exam-Ready)
An internal node in a binary tree is a node that has at least one child (left or right).
3. Example Binary Tree
1
/ \
2 3
/ \
4 5
Classification
Internal Nodes: 1, 2
Leaf Nodes: 3, 4, 5
Internal Node Count = 2
4. Identification Rule for Internal Node
A node is an internal node if:
(node->left != NULL OR node->right != NULL)
and
node != NULL
5. Core Logic (Recursive)
If tree is empty → return
0If node is a leaf → return
0Otherwise:
Count the current node as
1Recursively count internal nodes in left subtree
Recursively count internal nodes in right subtree
6. Recursive Formula
internalCount(node) =
0 if node == NULL
0 if node is a leaf
1 + internalCount(left) + internalCount(right) otherwise
7. Structure Definition
struct Node {
int data;
struct Node* left;
struct Node* right;
};
8. Function to Count Internal Nodes
int countInternalNodes(struct Node* root) {
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 0;
return 1 + countInternalNodes(root->left)
+ countInternalNodes(root->right);
}
9. Line-by-Line Explanation
if (root == NULL)
return 0;
Base case
Empty tree has no internal nodes
if (root->left == NULL && root->right == NULL)
return 0;
Leaf node detected
Leaf nodes are not internal nodes
return 1 + countInternalNodes(root->left)
+ countInternalNodes(root->right);
1counts the current internal nodeRecursively count internal nodes in left subtree
Recursively count internal nodes in right subtree
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 countInternalNodes(struct Node* root) {
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 0;
return 1 + countInternalNodes(root->left)
+ countInternalNodes(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 internal nodes: %d", countInternalNodes(root));
return 0;
}
11. Output
Total internal nodes: 2
12. Time and Space Complexity
Time Complexity
O(n)
Each node is visited once.
Space Complexity
O(h) (recursive stack)
Balanced tree →
O(log n)Skewed tree →
O(n)
13. Important Exam Points
Internal node = node with degree ≥ 1
Root can be internal if it has at least one child
Leaf nodes are explicitly excluded
Works for all binary trees
14. Common Beginner Mistakes
Counting leaf nodes as internal nodes
Forgetting base case (
root == NULL)Using
ANDinstead ofORfor child checkConfusing internal node count with total node count
15. Relationship Between Node Counts
Total Nodes = Internal Nodes + Leaf Nodes
(Valid for all non-empty binary trees)
16. Learning Outcome
After completing this post, learners can:
Correctly identify internal nodes
Implement internal node counting in C
Answer exam and interview questions confidently
Derive leaf/internal/total relationships
ALSO CHECK
ALSO CHECK
Comments
Post a Comment