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

1. i-1 nodes are there in left subtree.
2. 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
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates