We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I'm just gonna assume your code is conceptually correct. The issue is memoization. If you don't know what that is, definitely read about it.
What's happening here is that once, say, nthLevelBST 1 4 5 is given to nthLevelBST 1 5 7, it is thrown away. Then, when nthLevelBST 1 5 6 asks for nthLevelBST 1 4 5, it needs to be recalculated all over again. This means exponential time. However, if you store your results in some data structure (apparently even a normal list works), it is saved so it only is calculated once. In this case, it's possible and maybe even neater code to make nLevelBST in terms of nLevelBST so you only have to memoize with one variable.
The source that helped me most and serves as a model for my code is the very first memoized_fib on HaskellWiki.
Number of Binary Search Tree
You are viewing a single comment's thread. Return to all comments →
I'm just gonna assume your code is conceptually correct. The issue is memoization. If you don't know what that is, definitely read about it.
What's happening here is that once, say,
nthLevelBST 1 4 5
is given tonthLevelBST 1 5 7
, it is thrown away. Then, whennthLevelBST 1 5 6
asks fornthLevelBST 1 4 5
, it needs to be recalculated all over again. This means exponential time. However, if you store your results in some data structure (apparently even a normal list works), it is saved so it only is calculated once. In this case, it's possible and maybe even neater code to makenLevelBST
in terms ofnLevelBST
so you only have to memoize with one variable.The source that helped me most and serves as a model for my code is the very first
memoized_fib
on HaskellWiki.My code if you want spoilers. I use obscure syntax because it feels fancy.