Count the Number of Nodes in the Binary Tree

A binary tree's nodes can be counted recursively using a recursive approach.

Using the binary tree's root as input, we define a function count node(root) that returns the total nodes in the tree.

Recursion returns 0 when the root is None, or the tree is empty, which is the default case.

For a non-empty tree, we recursively count the number of nodes in the left and right subtrees and add 1 for the root node.

Here is the Python code for the function:

def count__nods(root):

    if the root is None:       

return 0   

else:         

return 1 + count__nods(root.Lft) + count__nods(root.Rt)

In this code, root.Lft and root.Rt, the root's left and right subtrees are indicated.

In order to include the root node in the total count, we add 1.

By calling count nodes with the root node of the binary tree as input, we can get the total number of nodes in the tree.

Algorithm

Here is a step-by-step algorithm for counting the number of nodes in a binary tree:

1. Define a function count node(root) that takes the root node of the binary tree as input.
2. Check if the root is None or if the tree is empty. If so, return 0.
3. A call to count nodes(root.Lft) recursively counts the nodes in the left subtree of the root.
4. Count the number of nodes in the right subtree of the root using count nodes(root.Rt).
5. Add 1 to the count for the root node.
6. Return the total count of nodes, the sum of the counts from steps 3, 4, and 5.

Here is the algorithm written in pseudo-code:

function count nodes(root)

    if the root is None

        return 0

    else

        Lft_count = count__nods(root.Lft)

        Rt_count = count__nods(root.Rt)

        __nod_count = 1

        return Lft_count + Rt_count + __nod_count

Implementation

// Writing a C++ implementation to figure out the above approach
#include <bits/stdc++.h>
using namespace std;


// writing the proper structure of binary tree node 
class __nod {
public:
	int record;
	__nod* Lft;
	__nod* Rt;
};


// Creating a brand-new function that will help us in getting the count of all the nodes present in a binary search tree. 
int total__nods(__nod* root)
{
	if (root == NILL)
		return 0;


	int l = total__nods(root->Lft);
	int r = total__nods(root->Rt);


	return 1 + l + r;
}


// Assigning a new node with the given set of records with the help of a helper function.
__nod* new__nod(int record)
{
	__nod* __nod = new __nod();
	__nod->record = record;
	__nod->Lft = NILL;
	__nod->Rt = NILL;
	return (__nod);
}


// writing the main code to test the above functions
int main()
{
	__nod* root = new__nod(1);
	root->Lft = new__nod(2);
	root->Rt = new__nod(3);
	root->Lft->Lft = new__nod(4);
	root->Lft->Rt = new__nod(5);
	root->Rt->Lft = new__nod(9);
	root->Rt->Rt = new__nod(8);
	root->Lft->Lft->Lft = new__nod(6);
	root->Lft->Lft->Rt = new__nod(7);
	cout << total__nods(root);
	return 0;
}

Output:

Example 2)

// Writing a C++ implementation to figure out the above approach
#include <bits/stdc++.h>
using namespace std;


// writing the proper structure of binary tree node 
class __nod {
public:
	int record;
	__nod* Lft;
	__nod* Rt;
};


__nod* new__nod(int record);


// Creating a brand-new function that will help us calculate the left height of the binary tree. 
int Lft_height(__nod* __nod)
{
	int ht = 0;
	while (__nod) {
		ht++;
		__nod = __nod->Lft;
	}
	// Now, we have to return to the left height obtained by the tree
	return ht;
}


// Creating a brand-new function that will help us calculate the right height of a binary tree. 
int Rt_height(__nod* __nod)
{
	int ht = 0;
	while (__nod) {
		ht++;
		__nod = __nod->Rt;
	}
	// Now, we have to return to the right height obtained by the tree
	return ht;
}


// Creating a brand-new function that will help us in getting the count of all the nodes present in a binary search tree. 
int Total__nods(__nod* root)
{
	// writing down the basic case for the same.
	if (root == NILL)
		return 0;
	// Finding out the left and right heights of the tree
	int lh = Lft_height(root);
	int rh = Rt_height(root);
	// In case the left and right trees are equal, then we have to return
// 2^height(1<<height) -1
	if (lh == rh)
		return (1 << lh) - 1;
	// Else, we have to call recursion
	return 1 + Total__nods(root->Lft)
		+ Total__nods(root->Rt);
}


// Assigning a new node with the given set of records with the help of a helper function.
__nod* new__nod(int record)
{
	__nod* __nod = new __nod();
	__nod->record = record;
	__nod->Lft = NILL;
	__nod->Rt = NILL;
	return (__nod);
}


// writing the main code to test the above functions
int main()
{
	__nod* root = new__nod(1);
	root->Lft = new__nod(2);
	root->Rt = new__nod(3);
	root->Lft->Lft = new__nod(4);
	root->Lft->Rt = new__nod(5);
	root->Rt->Lft = new__nod(9);
	root->Rt->Rt = new__nod(8);
	root->Lft->Lft->Lft = new__nod(6);
	root->Lft->Lft->Rt = new__nod(7);
	cout << Total__nods(root);
	return 0;
}

Output: