Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# 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(n2) and that’s a big difference!

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

O(n2).

## 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:

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# 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(n2) and that’s a big difference!

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

O(n2).

## 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: