Home »
C++ programs
C++ program to find number of BSTs with N nodes (Catalan numbers)
Here, we are implementing a C++ program to find number of BSTs with N Nodes (Catalan numbers).
Submitted by Saksham Bhayana, on December 09, 2018
Problem statement: C++ program to find number of binary search trees with n nodes.
Input format: single integer n
Constraints: 0=<n<=15
Sample input: 4
Sample output: 14 binary search tree/trees are there for 4 nodes
Problem explanation:
The number of BSTs with n vertices is given by Catalan numbers. For n=0,1,2,3,4... Catalan numbers are 1,1,2,5,14... and so on.
Catalan numbers are given by Cn = (2n)!/(n+1)!*n! = count of BSTs with nodes n.
Catalan numbers are used here to find the count of BSTs because both satisfy same recurrence relation that is:
For n=0 number of trees is 1 i.e. empty tree. For subsequent values:
And, so on...
Solution:
If we consider root as the ith node then:
- i-1 nodes are there in left subtree.
- n-i nodes are there in right subtree.
Let’s denote count of BST by Bn for n elements
The 2 subtrees here will be independent of each other. Therefore it will be ( B i-1 * B n-i ) for Bi . For n nodes (as i has n choices) it will be :
Since the recurrence relation is same as of catalan numbers , so count of BST is given by Cn.
Recurrence relation:
This gives complexity O(4^n). Complexity can be reduced to O(n^2) by using DP.
C++ implementation:
#include <iostream>
using namespace std;
int CN(int n){
int Cn =0;
// base case
if(n==0) // empty tree
{
return 1;
}
for(int i=1;i<n+1;i++)
{
Cn+= CN(i-1)*CN(n-i);
}
return Cn;
}
int main(){
int n;
cout<<"Enter number of nodes: ";
cin>>n;
cout<<n<<endl;
int trees=CN(n);
cout<<trees<<" binary search trees are there for "<<n<<" nodes"<<endl;
return 0;
}
Output
Enter number of nodes: 4
14 binary search trees are there for 4 nodes