/* following prog. takes no of elements as input and return no of possible BST on that number */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
long int bst(long int a);
long int BST[100];
//array to store solutions of subproblems.assume that n should less the 100 here.
//you can increase this value.
long int n;
int main()
{
int i;
long int total;
printf("\n enter no. of elements = \n");//take the no for which u want to calculate no of BST.
scanf("%ld",&n);
//initial set all subproblems sol. to 0.
for (i=2;i<=n-1;i++)
BST[i]=0;
BST[0]= 1;//set no of BST for nodes 1,0, equal 1.
BST[1] = 1;
//pass the value to function bst.
total = bst(n);
//total holds the final result
printf("\n the possible no of binary search tree on %ld elements is %ld",n,total);
return 0;
}
long int bst(long int a)
{
int i;long int count;
//if no_of elements 0 or 1 return 1.
if(a == 0 || a == 1 )
return 1;
//if solution of subproblem is there return the value.
else if(BST[a] != 0)
return BST[a];
else
{
count=0;
for (i=1;i<=a;i++)
{
//choose 1 to n roots at one time then call for both subtrees left and right recursivley.
count= count+ bst(i-1)*bst(a-i);
printf(" \n the count is on nodes is = %ld \n",count);
}
BST[a]=count;
return count;
}
}
