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





Was this page helpful? YES NO

Are you a blogger? Join our Blogging forum.



Comments and Discussions


We are using Google to publish ads on our website; Google has its own privacy policies. They may save log, cookies on your system. Google may also collect information of your system like IP address, region, city, country. For more details please go through the Google’s privacy policy.