We will be given the number of nodes used to create a Binary Search Tree (BST). We have to find the number of BSTs that we can create that have exactly the given number of nodes. For instance, if n=3 then the answer will be 5 as we can create 5 BSTs that contain exactly 3 nodes.
We recommend you refer to the NUMBER OF BSTs VIDEO to understand the question if you have any doubts regarding it. We suggest you try to solve the problem yourself first and then refer to the solution.
Algorithm:
1. The number of Binary Search Trees that can be made using n nodes is equal to the nth Catalan number. So, we will follow the algorithm to calculate the nth Catalan number.
2. Create a dp array of size n+1 where n is the input Catalan number.
3. Fill dp[0]=1 and dp[1]=1 and then start the outer loop from i=2 to i=n.
4. Start the inner loop from j=0 to less than I i.e. j=0 to j
5. Use the formula dp[i] += dp[j] x dp[i-j-1] inside the inner loop to fill the array with the Catalan numbers.
6. Print dp[n] as the answer.
Explanation:
Let us start by exploring the number of BSTs that we can create with different inputs.
0 nodes: The number of BSTs that we can create if we are not given any node is 1. This is because a tree with no node does not disobey the Binary Search Tree Property (BTP).
1 node: A tree with only a single node will have only one Binary Search Tree. Say if the data of the node was 10 for instance, we will have only one BST with the only node with data 10 as the root node.
2 nodes: If we are given 2 nodes, there can be two BSTs possible:
This is because once we will select one node as the root node and the other time the other.
3 nodes: Now things will get interesting for us. Let us assume the three nodes given to us are 10, 20, and 30. Let us try to make BSTs from them.
So, we have made 5 BSTs from the given number. The important thing here is not the trees that we have made, rather, how we concluded that there will be 5 BSTs. So, let us look at that:
When we choose 10 to be selected as the root node, following the BST Property, we will not have any nodes in the left subtree and we have the remaining 2 nodes in the right subtree. Now, we know that the remaining subtree should also be a BST. We have 2 nodes in the right subtree and we can make 2 BSTs from these 2 nodes (discussed in the previous point). While we can generate 2 BSTs in the right subtree we have to generate a BST in the left subtree as well and we can generate 1 BST when we do not have any node (also discussed above).
So, we have to generate 1 BST in the left subtree AND 2 BSTs in the right subtree. So, we multiply both the numbers and get the count of the BSTs that we can make from this BST. These two BSTs that we can make from the first BST shown are given below:
So, we have now understood how we counted the number of BST's by taking 10 as the root node. Similarly, we have counted the number of BSTs by taking 20 and 30 as the root nodes as well.
We have added these values because we can either have 10 as the root node OR 20 as the root node OR 30 as the root node. Hope you got it!!!
So, we want you to think about the number of BSTs that we can generate from 4 nodes. Try to apply the same method as we did.
4 nodes: We will not generate all the BSTs. Let us just calculate the count by generating the 4 BSTs where each value will be kept as the root node once.
So, according to the diagram above, 14 BSTs can be generated from 4 nodes. So, we hope that you have understood what we are doing here. Did you notice anything in the procedure?
Have a look at the procedure carefully again. The Catalan number is also calculated in the same way. Oh, wait!!! This is nothing but the Catalan number only.
Yes, the 0th Catalan number is 1 and the 1st Catalan number is also 1 and the number of BSTs with 0 and 1 nodes respectively is also 1. Similarly, the third Catalan number is 5, and the number of BSTs with 3 nodes is also 5.
Hence the number of BSTs that can be generated from n nodes is equal to the nth Catalan number.
So, we just have to find the nth Catalan number and that will be our answer.
You may refer to the solution video to understand the above-explained section of the article.
We recommend you refer to the CATALAN NUMBERS VIDEO to watch how we can generate the nth Catalan number. The process is explained in short here too.
Generating nth Catalan Number:
1. Storage and Meaning:
So, we will create a dp array of size n+1 (as there are n+1 Catalan numbers from 0 to n) and each element of the array will store that indexed Catalan number. (if input n=8 then look at the image shown below)
For instance, the element at index 3 will be the third Catalan number C3.
2. The direction of solving:
This is also very simple. We already know the values of the 0th Catalan number and the 1st Catalan number i.e. 1. We have to find the nth Catalan number. So, the problem size increases when we move from 0 to n, and the same will be the direction of solving.
3. Travel and Solve:
So, let us take a look at some of the Catalan numbers that we can derive from the formula above.
Every term comprises multiplication of the two terms. So, if we are calculating the nth Catalan number, the first number in every term starts from index 0 till the index n-1 for n terms.
Have a look at the image below:
If we number the Catalan terms from 0 to n-1 when we are calculating the nth Catalan number, we see that the ith term in the nth Catalan number is Ci x Cn-i-1.
So, by using the above formula, we can easily fill the complete dp array. The dp array filled for n=5 is shown below:
Let us now write the code for generating the nth Catalan number that is also the solution for this problem.
Java Code
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scn=new Scanner(System.in);
int n=scn.nextInt();
long[] dp = new long[n + 1];
dp[0] = 1; //since 0th Catalan number is 1
dp[1] = 1; //since 1st Catalan number is also 1
for(int i = 2; i < dp.length; i++){
for(int j = 0; j < i; j++){
dp[i] += dp[j] * dp[i - 1 - j];
}
}
System.out.println(dp[n]); //nth Catalan number
}
}
java;
true";
You may refer to the solution video to understand the above code if you have any doubts regarding the same. Let us now analyze the time and space complexity of the above code.
Analysis:
Time Complexity:O(n2)
The time complexity of the above solution is O(n2) where n is the input number. This is because the inner loop runs for "i" number of times and the outer loop runs for n times.
So, the inner loop runs n(n+1)/2 times. Why? Think about this!!! This is what makes the time complexity go O(n2).
Space Complexity:O(n)
The space complexity is O(n) as we make an array of size n+1.
So, dear reader, we hope that you got the time and space complexity as well. We recommend you refer to the complete solution video once to clear all your doubts if any. With this, we have completed this problem.
Suggestions:
Here are some suggestions from our side that you do not want to miss:
You need to understand how we related the generation of BSTs to the Catalan number. This is explained in detail in the solution video . We recommend you refer to it so that your concepts get strong.
You should be well prepared with Catalan Numbers as you will see a lot of indirect problems based on them in the coding rounds and interviews.
All the best for an exciting future!
Happy Coding!
