How Many Binary Search Trees With n Nodes Problem

Problem Statement

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.

Example One

Input: 1

Output: 1

Example Two

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

Solutions

We have provided 4 solutions:

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. 

‍

1) Recursive solution: brute_force_solution.cpp

Time Complexity: 

O(Catalan number(n)).

This is a loose bound, tight bound is very complex to derive and explain.

Auxiliary Space Used:

O(n).

Due to the space used by function call stack, during recursive function calls. 

Space Complexity: 

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!)

2) Recursive solution with memoization: other_solution.cpp

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.

Time Complexity:

O(n^2).

Auxiliary Space Used:

O(n).

As we are using array to store the calculated results. 

Space Complexity:

O(n).

Auxiliary space used is O(n), input takes O(1). O(n) + O(1) = O(n).