Number of binary search trees of a given height
How can I find the number of BSTs up to a given height h and discard all BSTs with a height greater than h for a given set of unique numbers?
I have developed the code using a recursive approach
static int bst(int h,int n){
if(h==0&&n==0)return 1;
else if(h==0&&n==1)return 1;
else if(h==0&&n>1)return 0;
else if(h>0&&n==0)return 1;
else{
int sum=0;
for(int i=1;i<=n;i++)
sum+=bst(h-1,i-1)*bst(h-1,n-i);
return sum;
}
}
source to share
You can speed it up by adding memoization like @DavidEisenstat suggested in the comments.
You are creating a memoization table to store the values of the already computed results. This example -1
indicates that the value has not yet been calculated.
Example in C ++
long long memo[MAX_H][MAX_N];
long long bst(int h,int n){
if(memo[h][n] == -1){
memo[h][n] = //Compute the value here using recursion
}
return memo[h][n];
}
...
int main(){
memset(memo,-1,sizeof memo);
bst(102,89);
}
This will be done in O(h*n)
because you will only compute bst
once for each possible pair of n
and h
. Another advantage of this method is that after filling the table, bst will respond in O (1) (for values in the table range). Be careful not to call the function with values above MAX_H
and MAN_N
. Also remember that memoization is a tradeoff between memory and time, which means your program will run faster, but it will also use more memory.
More information: https://en.wikipedia.org/wiki/Memoization
source to share