# Number of Binary Search Tree

# Number of Binary Search Tree

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

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 + 0 comments In your explanation of Test Case 3, the last two trees are invalid. Those should be 3 / 1 \ 2 and 3 / 2 / 1

Schabronze + 0 comments 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...)

Sort 8 Discussions, By:

Please Login in order to post a comment