Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

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.

```
{
"n": 1
}
```

Output:

```
1
```

```
{
"n": 2
}
```

Output:

```
2
```

Suppose the values are 1 and 2, then the two trees that are possible are

```
(2) (1)
/ and \
(1) (2)
```

```
{
"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)
```

Constraints:

- 1 <=
`n`

<= 16

We have provided 4 solutions:

- 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. - Recursive solution with memoization:
`How Many Binary Search Trees With N Nodes Solution 2: Other`

Much faster than the recursive one. - Iterative solution:
`optimal_solution.cpp`

Logically the same as the previous one. Though faster by a constant because recursion is removed. - 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!)

```
/*
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;
}
```

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

```
/*
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.

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

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.

```
{
"n": 1
}
```

Output:

```
1
```

```
{
"n": 2
}
```

Output:

```
2
```

Suppose the values are 1 and 2, then the two trees that are possible are

```
(2) (1)
/ and \
(1) (2)
```

```
{
"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)
```

Constraints:

- 1 <=
`n`

<= 16

We have provided 4 solutions:

- 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. - Recursive solution with memoization:
`How Many Binary Search Trees With N Nodes Solution 2: Other`

Much faster than the recursive one. - Iterative solution:
`optimal_solution.cpp`

Logically the same as the previous one. Though faster by a constant because recursion is removed. - 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!)

```
/*
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;
}
```

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

```
/*
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.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart