algorithm - Number of Binary Search Trees of a given Height -

how can find number of bsts upto given height h , discard bsts height greater h given set of unique numbers?

i have worked out code using 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;     } } 

you can speed adding memoization @davideisenstat suggested in comments.

you create memoization table store values of computed results. in example, -1 indicates value has not been computed yet.

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 value here using recursion     }     return memo[h][n]; }  ...  int main(){     memset(memo,-1,sizeof memo);     bst(102,89); } 

this execute in o(h*n) compute bst once each possible pair of n , h. advantage of technique once table filled up, bst respond in o(1) (for values in range of table). careful not call function values above max_h , man_n. keep in mind memoization memory-time tradeoff, meaning program run faster, use more memory too.

more info: https://en.wikipedia.org/wiki/memoization