.png)
DSA Series Chapter 22 – COUNT LEAF NODES IN BINARY TREE(Python Edition)
1. Objective
To count the total number of leaf nodes in a Binary Tree using a recursive Depth First Search (DFS) approach implemented in Python.
2. Definition (Exam-Ready)
A leaf node is a node in a binary tree 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. Condition to Identify Leaf Node
node.left is None AND node.right is None
5. Core Logic
If the tree is empty → return
0If current node is a leaf → return
1Otherwise:
Count leaf nodes in left subtree
Count leaf nodes in right subtree
Add the results
6. Recursive Formula
leafCount(node) =
0 if node is None
1 if node is a leaf
leafCount(left) + leafCount(right) otherwise
7. Binary Tree Node Class
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
8. Function to Count Leaf Nodes
def count_leaf_nodes(root):
if root is None:
return 0
if root.left is None and root.right is None:
return 1
return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)
9. Line-by-Line Explanation
def count_leaf_nodes(root):
Function receives the root node of the tree
if root is None:
return 0
Base case
Empty subtree has no leaf nodes
if root.left is None and root.right is None:
return 1
Checks whether current node is a leaf
If yes, count it as one leaf
return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)
Recursively counts leaf nodes in both subtrees
Adds both counts
10. Complete Python Program
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def count_leaf_nodes(root):
if root is None:
return 0
if root.left is None and root.right is None:
return 1
return count_leaf_nodes(root.left) + count_leaf_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 leaf nodes:", count_leaf_nodes(root))
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 Points
Leaf node has degree 0
DFS recursion is most commonly used
Works for all binary trees (not BST-specific)
Root can also be a leaf if it has no children
14. Common Beginner Mistakes
Counting nodes with only one child as leaf
Forgetting the base case
Using global counters unnecessarily
Mixing leaf node logic with total node logic
15. Comparison: C vs Python
| Aspect | C | Python |
|---|---|---|
| NULL check | root == NULL | root is None |
| Memory | Manual | Automatic |
| Recursion | Function calls | Function calls |
16. Learning Outcome
After completing this post, learners can:
Correctly identify leaf nodes
Implement leaf node counting in Python
Solve exam and interview questions
Extend logic to internal node counting
ALSO CHECK
ALSO CHECK
Comments
Post a Comment