Using recursion to find the number of binary tree nodes in Python

A binary tree is a tree data structure with a maximum of two children per node. In this Answer, we will learn to count the number of nodes present in a binary tree using recursion in Python.

Algorithm

  • If the root node is empty, our algorithm will return 0.

  • If the root node is not empty, the algorithm will return 1 + count of left sub-tree + count of right sub-tree.

We will use pre-order traversal using recursion to traverse the binary tree.

Let's take a look at an example of this.

Example

The following diagram shows an example of a binary tree:

%0 node_1 1 node_2 2 node_1->node_2 node_3 3 node_1->node_3 node_1665366078050 4 node_2->node_1665366078050 node_1665366143839 5 node_2->node_1665366143839 node_1665366167064 6 node_3->node_1665366167064 node_1665366146156 7 node_3->node_1665366146156
This figure illustrates the structure of a binary tree. Notice each node has a maximum of two children.

It can be seen in the figure above that it has a total of seven nodes. This is what we want our algorithm to return. Now let's look into the code to calculate the number of nodes for the tree shown above.

Code

# Node class created
class Node(): 
    def __init__(self, data): 
        self.data = data
        self.left = None
        self.right = None
# insert nodes starting from the root
root = Node(1) 
root.left = Node(2) 
root.right = Node(3) 
root.left.left = Node(4) 
root.left.right = Node(5) 
root.right.left = Node(6) 
root.right.right = Node(7)
# function to count the number of nodes 
def count_nodes(root):
    if root == None:
        return 0
    
    return 1 + count_nodes(root.left) + count_nodes(root.right)
    
    
# function call
print("The total number of nodes is",count_nodes(root))

Explanation

In the code snippet above,

  • Lines 2–6: We create a class Node to create nodes for a binary tree.

  • Lines 9–15: We insert nodes into the binary tree as shown in the image above.

  • Lines 18–22: We declare and define a function count_nodes(), which accepts root node as a parameter and returns the total nodes in the binary tree.

  • Line 27: We call the function count_nodes() with the root node as a parameter and print the returned result.

Free Resources

Copyright ©2026 Educative, Inc. All rights reserved