Home » Data Structure

Find the Number of Nodes in a Binary Search Tree (C++ program)

Learn: How to find the total number of nodes in a Binary Search Tree using C++ program?
Submitted by Abhishek Jain, on July 30, 2017

This section discusses the recursive algorithm which counts the size or total number of nodes in a Binary Search Tree.

Total No. of nodes=Total No. of nodes in left sub-tree + Total no. of node in right sub-tree + 1

Algorithm:

CountNodes(node x)
set n=1    //global variable
If x=NULL
	return 0
[End If]
If(x->left!=NULL)
    n=n+1
CountNode(x->left)
[End If]
If(x->right!=NULL)
    n=n+1
CountNode(x->right)
[End If]
Return n

C++ program to count total number of Nodes in BST

#include<iostream>
using namespace std;

int n=1;

struct node
{
	int data;
	node* left;
	node* right;
};

struct node* getNode(int data)
{
	node* newNode=new node();
	newNode->data=data;
	newNode->left=NULL;
	newNode->right=NULL;
	return newNode;
}

struct node* Insert(struct node* root, int data)
{
	if (root == NULL)
		return getNode(data);
	
	if (data < root->data)
		root->left  = Insert(root->left, data);
	else if (data > root->data)
		root->right = Insert(root->right, data);

	return root;
}


int CountNodes(node*root)
{
	if(root==NULL)
		return 0;
	if(root->left!=NULL)
	{
		n=n+1;
		n=CountNodes(root->left);
	}
	if(root->right!=NULL)
	{
		n=n+1;
		n=CountNodes(root->right);
	}
	return n;
}

int main()
{  
	node* root=NULL;
	root=Insert(root,3);
	Insert(root,4);
	Insert(root,2);
	Insert(root,5);
	Insert(root,1);

	cout<<"Total No. of Nodes in the BST = "<<CountNodes(root)<<endl;

	return 0;
}

Output

Total No. of Nodes in the BST = 5