Write a function that returns the number of distinct binary search trees that can be constructed with n nodes.
For the purpose of this exercise, do solve the problem using recursion first even if you see some non-recursive approaches.
Input: 1
Output: 1
Input: 2
Output: 2
Suppose the values are 1 and 2, then the two trees that are possible are
(2) (1)
/ and \
(1) (2)
Example Three
Input: 3
Output: 5
Suppose the values are 1, 2, 3 then the possible trees are
(3)
/
(2)
/
(1)
(3)
/
(1)
\
(2)
(1)
\
(2)
\
(3)
(1)
\
(3)
/
(2)
(2)
/ \
(1) (3)
Notes
Input Parameters: Function has one argument: n.
Output: Function must return an integer value.
Constraints:
• 1 <= n <= 16
1) Recursive solution: brute_force_solution.cpp. In this problem, we only want to practice recursion so constraints are intentionally kept low to allow this solution to pass all the test cases.
2) Recursive solution with memoization: other_solution.cpp. Much faster than the recursive one.
3) Iterative solution: optimal_solution.cpp. Logically the same as the previous one. Though faster by a constant because recursion is removed.
4) Catalan number solution: catalan_number_solution.cpp. If you provide such a solution in an interview without explaining the intuition, it will not be accepted.
First look at the Recursive solution then Recursive solution with memoization and then the Iterative solution.
We expect you to implement the Recursive solution with memoization at least once.
O(Catalan number(n)).
This is a loose bound, tight bound is very complex to derive and explain.
O(n).
Due to the space used by function call stack, during recursive function calls.
O(n).
Auxiliary space used is O(n), input takes O(1). O(n) + O(1) = O(n).
In the recursive function you will notice that function how_many_BSTs is called to calculate the same values many times!
This recalculation can be avoided by using memoization technique. (We can use an array to store the result once it is calculated and afterwards reuse it!)
Adding a few lines of code improves time complexity from O(Catalan number(n))) to O(n^2) and that’s a big difference!
For example, Catalan_number(35) = 3116285494907301262, while 35^2 = 1225.
O(n^2).
O(n).
As we are using array to store the calculated results.
O(n).
Auxiliary space used is O(n), input takes O(1). O(n) + O(1) = O(n).
