.png)
DSA Series Chapter 21 : COUNT TOTAL NODES IN BINARY TREE(Python Version)
1. Objective
To count the total number of nodes present in a Binary Tree using a recursive Depth First Search (DFS) approach implemented in Python.
2. Definition (Exam-Ready)
Counting total nodes in a binary tree means calculating the number of all nodes present in the tree, including root, internal nodes, and leaf nodes.
3. Example Binary Tree
1
/ \
2 3
/ \
4 5
Total Nodes
Nodes: {1, 2, 3, 4, 5}
Count = 5
4. Core Logic
If the tree is empty → return
0Otherwise:
Count nodes in left subtree
Count nodes in right subtree
Add
1for the current node
5. Recursive Formula
count(node) = 1 + count(left) + count(right)
Base Case
count(None) = 0
6. Binary Tree Node Class
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
7. Function to Count Total Nodes
def count_nodes(root):
if root is None:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
8. Line-by-Line Explanation
def count_nodes(root):
Function receives the root of the tree
if root is None:
return 0
Base case
Empty subtree contributes zero nodes
return 1 + count_nodes(root.left) + count_nodes(root.right)
1→ current nodeRecursive call on left subtree
Recursive call on right subtree
9. Complete Python Program
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def count_nodes(root):
if root is None:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
# Driver Code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Total number of nodes:", count_nodes(root))
10. Output
Total number of nodes: 5
11. Time and Space Complexity
Time Complexity
O(n)
Each node is visited exactly once.
Space Complexity
O(h) due to recursion stack
Best case (balanced tree):
O(log n)Worst case (skewed tree):
O(n)
12. Important Exam Points
DFS recursion is the most common method
Base condition must return
0Do not confuse node count with height
Includes all nodes, not only leaves
13. Common Mistakes by Beginners
Returning
1whenroot is NoneForgetting to add
+1for current nodeUsing global counters unnecessarily
Mixing BFS logic in DFS recursion
14. Comparison with C Version
| Feature | C | Python |
|---|---|---|
| NULL check | root == NULL | root is None |
| Recursion | Function call | Function call |
| Memory mgmt | Manual | Automatic |
15. Learning Outcome
After this post, learners can:
Implement node counting in Python
Understand recursive DFS clearly
Solve exam and interview questions
Extend logic to leaf/internal node counting
ALSO CHECK
ALSO CHECK
Comments
Post a Comment