Course contentsShow
← Computer Science
Lesson 515 of 2,87212. Binary Search TreesFree lesson

Counting Nodes in a BST

Count total nodes recursively by summing 1 plus the counts of left and right subtrees.

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.