# 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`