Counting Nodes in a BST
What you'll learn: How to calculate the total number of nodes in a Binary Search Tree using recursion.
Core Idea
Counting nodes in a BST follows a beautifully simple recursive pattern. To count all nodes in a tree, you add 1 (for the current node) plus the count of nodes in the left subtree plus the count of nodes in the right subtree. When you reach an empty subtree (null pointer), you return 0.
Think of it like counting people in a family tree: count yourself (1), then ask your left branch how many people they have, ask your right branch how many they have, and sum it all up!
The Recursive Pattern
The base case is straightforward: if the current node is null, there are zero nodes to count. Otherwise, recursively count the left and right subtrees and add 1 for the current node:
def count_nodes(node):
if node is None:
return 0
# Count this node (1) + left subtree + right subtree
left_count = count_nodes(node.left)
right_count = count_nodes(node.right)
return 1 + left_count + right_count
Or more concisely:
def count_nodes(node):
if node is None:
return 0
return 1 + count_nodes(node.left) + count_nodes(node.right)
Why This Works
Every node contributes exactly 1 to the total count. The recursion automatically visits every node once, counting as it goes. The BST property doesn't affect counting—we visit all nodes regardless of their values.
Key Takeaway: Counting nodes in a BST uses recursion: return 0 for null nodes, or 1 plus the sum of left and right subtree counts for non-null nodes. Time complexity is O(n) since every node is visited once.