How Many Binary Search Trees With N Nodes 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

{
"n": 1
}

Output:

1

Example Two

{
"n": 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

{
"n": 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

Constraints:

• 1 <= n <= 16

We have provided 4 solutions:

1. Recursive solution: How Many Binary Search Trees With N Nodes Solution 1: Brute Force 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: How Many Binary Search Trees With N Nodes Solution 2: Other 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.

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

Code For How Many Binary Search Trees With N Nodes Solution 1: Brute Force

/*
Asymptotic complexity in terms of \`n\`:
* Time: O(Catalan number(n)).
* Auxiliary space: O(n).
* Total space: O(n).
*/

long long int how_many_bsts(int n) {
    // If base case.
    if (n == 0) {
        return 1LL;
    }
    /*
    Any BST with n nodes can be divided in 3 parts,
    1) root.
    2) left sub-BST.
    3) right sub-BST.

    There will be always one root hence structure of BST will only depend on the left sub-BST and
    the right sub-BST.

    We have 1 root fixed hence we have n - 1 nodes in left sub-BST + right sub-BST.
    So that is,
    n - 1 = nodes in left sub-BST + nodes in right sub-BST.
    To get all the possibilities we can fix nodes in left sub-BST and get nodes in right sub-BST!
    So from the above formula,

    nodes in left sub-BST -> nodes in right sub-BST

    0 -> n - 1
    1 -> n - 2
    2 -> n - 3
    ...
    n - 3 -> 2
    n - 2 -> 1
    n - 1 -> 0

    Now suppose we take one fixed possibility 2 (nodes in left sub-BST) -> n - 3
    (nodes in right sub-BST), then if we can get total number of BSTs possible with 2 nodes
    (let's say it is x) and total number of BSTs possible with n - 3 nodes (let's say it is y),
    then we can get the total number of BSTs possible with n nodes for the current possibility
    (WHEN IN LEFT SUB-BST WE HAVE 2 NODES AND IN RIGHT SUB-BST WE HAVE n - 3 NODES) by x * y. Now
    question is why x * y? For BST with n nodes we will fix one root, on the left subBST we fix 1
    tree out of x possible BSTs, then to create BST with n nodes, we can use any of the y possible
    BSTs on the right sub-BST. So for one fixed sub-BST on left side we have generated y BSTs with
    n nodes. Now doing this for all x sub-BSTs possible on left side, total number of generated
    BSTs = y + y + ... y (total x times) and that is x * y. (This will be difficult to understand
    unless you try some examples yourself.)

    Now as we have done for 2 -> n - 3, we can try all possibilities and get the final answer
    denoting total number of BSTS possible with n nodes!

    Let's take a small example n = 3 and see how every possible BST is covered in one of the
    parition.
    All possible BSTs with 3 nodes are,
    1) root, root->left, root->left->left
    2) root, root->left, root->left->right
    3) root, root->right, root->right->right
    4) root, root->right, root->right->left
    5) root, root->left, root->right

    Now if we try:
    0 -> 2
    1 -> 1
    2 -> 0

    then we can divide the above 5 possibilities as:
    0 -> 2 :     3) root, root->right, root->right->right
                4) root, root->right, root->right->left
    1 -> 1 :     5) root, root->left, root->right
    2 -> 0 :     1) root, root->left, root->left->left
                2) root, root->left, root->left->right
    */
    long long int BSTs = 0LL;
    // Try all possibilities by taking number of nodes in left subBST from 0 to n - 1.
    for (int number_of_nodes_in_left_subBST = 0; number_of_nodes_in_left_subBST < n;
         number_of_nodes_in_left_subBST++) {
        int number_of_nodes_in_right_subBST = n - 1 - number_of_nodes_in_left_subBST;
        BSTs += how_many_bsts(number_of_nodes_in_left_subBST) *
                how_many_bsts(number_of_nodes_in_right_subBST);
    }
    return BSTs;
}

other_solution.cpp

Adding a few lines of code improves time complexity from O(Catalan number(n))) to O(n²) and that’s a big difference!

For example, Catalan_number(35) = 3116285494907301262, while 35² = 1225.

Time Complexity

O(n²).

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

Code For How Many Binary Search Trees With N Nodes Solution 2: Other

/*
Asymptotic complexity in terms of \`n\`:
* Time: O(n^2).
* Auxiliary space: O(n).
* Total space: O(n).
*/

/*
Global variable used to store the results.
memorized_BSTs[i] == -1, indicates that number of binary search trees possible with i nodes is
remaining to calculate.
memorized_BSTs[i] != -1, indicates that number of binary search trees possible with i nodes i
calculated once and now onwards we can reuse it, no need to recalculate.
*/
vector<long long int> memorized_BSTs(16 + 1, -1);

long long int how_many_bsts(int n) {
    // If base case.
    if (n == 0) {
        return 1LL;
    }
    // If we have already calculated the value then return it, do not recalculate.
    if (memorized_BSTs[n] != -1LL) {
        return memorized_BSTs[n];
    }
    /*
    Any BST with n nodes can be divided in 3 parts,
    1) root.
    2) left sub-BST.
    3) right sub-BST.

    There will be always one root hence structure of BST will only depend on the left sub-BST and
    the right sub-BST.

    We have 1 root fixed hence we have n - 1 nodes in left sub-BST + right sub-BST.
    So that is,
    n - 1 = nodes in left sub-BST + nodes in right sub-BST.
    To get all the possibilities we can fix nodes in left sub-BST and get nodes in right sub-BST!
    So from the above formula,

    nodes in left sub-BST -> nodes in right sub-BST

    0 -> n - 1
    1 -> n - 2
    2 -> n - 3
    ...
    n - 3 -> 2
    n - 2 -> 1
    n - 1 -> 0

    Now suppose we take one fixed possibility 2 (nodes in left sub-BST) -> n - 3
    (nodes in right sub-BST), then if we can get total number of BSTs possible with 2 nodes
    (let's say it is x) and total number of BSTs possible with n - 3 nodes (let's say it is y),
    then we can get the total number of BSTs possible with n nodes for the current possibility
    (WHEN IN LEFT SUB-BST WE HAVE 2 NODES AND IN RIGHT SUB-BST WE HAVE n - 3 NODES) by x * y. Now
    question is why x * y? For BST with n nodes we will fix one root, on the left subBST we fix 1
    tree out of x possible BSTs, then to create BST with n nodes, we can use any of the y possible
    BSTs on the right sub-BST. So for one fixed sub-BST on left side we have generated y BSTs with
    n nodes. Now doing this for all x sub-BSTs possible on left side, total number of generated
    BSTs = y + y + ... y (total x times) and that is x * y. (This will be difficult to understand
    unless you try some examples yourself.)

    Now as we have done for 2 -> n - 3, we can try all possibilities and get the final answer
    denoting total number of BSTS possible with n nodes!

    Let's take a small example n = 3 and see how every possible BST is covered in one of the
    parition.
    All possible BSTs with 3 nodes are,
    1) root, root->left, root->left->left
    2) root, root->left, root->left->right
    3) root, root->right, root->right->right
    4) root, root->right, root->right->left
    5) root, root->left, root->right

    Now if we try:
    0 -> 2
    1 -> 1
    2 -> 0

    then we can divide the above 5 possibilities as:
    0 -> 2 :     3) root, root->right, root->right->right
                4) root, root->right, root->right->left
    1 -> 1 :     5) root, root->left, root->right
    2 -> 0 :     1) root, root->left, root->left->left
                2) root, root->left, root->left->right
    */
    long long int BSTs = 0LL;
    // Try all possibilities by taking number of nodes in left subBST from 0 to n - 1.
    for (int number_of_nodes_in_left_subBST = 0; number_of_nodes_in_left_subBST < n;
         number_of_nodes_in_left_subBST++) {
        int number_of_nodes_in_right_subBST = n - 1 - number_of_nodes_in_left_subBST;
        BSTs += how_many_bsts(number_of_nodes_in_left_subBST) *
                how_many_bsts(number_of_nodes_in_right_subBST);
    }
    // Store the calculated result, nowonwards do not recalculate it for n nodes.
    memorized_BSTs[n] = BSTs;
    return BSTs;
}

We hope that these solutions to unique binary search trees problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.