# Number of Binary Search Tree

# Number of Binary Search Tree

johnreedprogram1 + 1 comment I see a lot of solutions using "100000007". Where does "100000007" come from?

doxuanthangAsked to answer + 0 comments

maqusss + 0 comments Who used Data.Map.Lazy for memoization?

h503689341 + 0 comments I am just a fresh man in Haskell, and I have already know the lazy evaluation, so I can't understand why my following answer can't get result for the input of 100. Any advice will be appreciated! Thx a lot!

nLevelBST n = rem (sum([nthLevelBST 1 t n | t <- [1..n]])) (10^8 + 7) nthLevelBST l m r | l == m && m == r = 1 | l == m && m /= r = sum([nthLevelBST (m+1) mr r | mr <- [(m+1)..r]]) | l /= m && m == r = sum([nthLevelBST l ml (m-1) | ml <- [l..(m-1)]]) | otherwise = (sum([nthLevelBST l ml (m-1) | ml <- [l..(m-1)]])) * (sum([nthLevelBST (m+1) mr r | mr <- [(m+1)..r]]))

itsbruce + 1 comment In your explanation of Test Case 3, the last two trees are invalid. Those should be 3 / 1 \ 2 and 3 / 2 / 1

abhiranjanChallenge Author + 0 comments Hi @itsbruce, thanks for pointing that out. Now fixed.

Schabronze + 1 comment I enjoyed this challenge, but what really bugged me was the last testcase. I thought my code was actually optimized enough, but it still did not pass.

var data = new Array[Long](k + 1) data(0) = 1 data(1) = 1 def getTrees(n: Int): Long = { if(data(n) != 0) data(n) else {data(n) = (for(i <- 0 until n) yield getTrees(i)*getTrees(n-1-i)%100000007).sum % 100000007; data(n)} }

Did I miss something, because I orinially thought the Point of these challenges was to get the ideas into ones head, and not to write fully optimized code. Or is my Code possibly just bad? (Also: the same code, just with the for-comprehension transformed into a imperative loop passes, so the difference really is just that...)

mcherri + 0 comments A naive question. Do you call getTrees for each n?

Astha_9334 + 0 comments Hi, I tried solving the problem and coded in C. But I am not getting result when N=100. My code is:

void noBST(int N){ unsigned int bst[N+1]; int i,j; bst[0]=1; bst[1]=1; for(i=2;i<=N;i++){ bst[i]=0; for(j=1;j<=i;j++){

`bst[i]=bst[i-j]*bst[j-1]+bst[i]; } }`

printf("%u\n",bst[N]); } int main(){ int T,N,i; scanf("%d",&T); for(i=0;i

No more comments

Sort 7 Discussions, By:

Please Login in order to post a comment