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:
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 createdclass Node():def __init__(self, data):self.data = dataself.left = Noneself.right = None# insert nodes starting from the rootroot = 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 nodesdef count_nodes(root):if root == None:return 0return 1 + count_nodes(root.left) + count_nodes(root.right)# function callprint("The total number of nodes is",count_nodes(root))
Explanation
In the code snippet above,
Lines 2–6: We create a class
Nodeto 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 acceptsrootnode as a parameter and returns the total nodes in the binary tree.Line 27: We call the function
count_nodes()with therootnode as a parameter and print the returned result.
Free Resources
