Last Updated: 18 Nov, 2021
Ninja and the BSTs
Moderate
Asked in companies
Ninja and Bob were playing the game. Ninja challenged Bob to solve the following problem.
Given an integer 'N' Bob has to find the total number of different binary search trees that can be formed with 'N' different nodes.
Your task is to help Bob to solve the task given by Ninja to him.
Print the answer modulo 1000000007.
Example:
Input: ‘N’ = 2
Output: 2
Explanation: We can form two different BSTs with two nodes only.
One with node one as a root and the other with node two as a root.
Input Format :
The first line of input contains an integer ‘T', denoting the number of test cases.
Each test case contains a single integer 'N' denoting the number of nodes.
Output format :
For each test case, print the total number of different binary search trees that can be formed.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 10
1 <= 'N' <= 10^2
Timit Limit: 1 sec
Approaches
Approach: We will start by taking any of the node 1...n as the root node. Let the chosen root node be i. Then, we have a BST where the root node is i; the left child consists of all nodes from 1...i-1 (since the left sub-tree must have only less than root value), and the right child consists of all nodes from i+1...n. We will recursively call it for all possible cases and count the number of BSTs.
Algorithm :
- Check for base case if 'N' <= 1 return 1.
- Initialize the variable 'ans' to store the answer.
- Initialize variable ‘mod’ by ‘1000000007’
- Run a for loop ‘i’ from 1 to 'N' and add the following multiplicand in the 'ans' numberOfBSTs(‘N’ - i) * numberOfBSTs(‘i’ - 1).
- Update ‘ans’ with ‘ans % mod’
- Return 'ans'.
Approach: This approach and code will be very similar to the first one. The only change is that every time we calculate the result for numberOfBSTs(i), we store the result in dp[i] and return it. Hence will optimize it by Memoization.
Algorithm :
- Make one array 'dp' of size 'N + 1'.
- Make two functions ‘add’ and ‘mult’ to get the modular addition and multiplication of two numbers.
- Make one function ‘numberOfBSTsHelper’ and pass parameter ‘N’ and ‘dp’ into it.
- If 'N' is less than or equal to 1 then return 1.
- If 'dp[N]' is not -1 then return 'dp[N]'.
- Initialize variable ‘res’ with 0.
- Run a loop ’i’ from 1 to 'N' add the following multiplicand in the ‘res' add(res, mult(numberOfBSTsHelper(i - 1, dp), numberOfBSTsHelper(n - i, dp)))
- Return 'dp[N]' = ‘res’.
- Return ‘solve(n, dp)’.
Approach: We can also solve this problem using iterative dynamic programming. The approach is similar to the recursive approach with a slight change.
We will start from the base conditions instead of the other way around.
We have base conditions of dp[0] = dp[1] = 1. Then we will calculate a result for each number of nodes i from 2...n one after another. For i nodes. We will consider each of the node j from 1...i as the root node of BST.
Algorithm :
- Make one array 'dp' of size 'N + 1'.
- Make two functions ‘add’ and ‘mult’ to get the modular addition and multiplication of two numbers.
- Initialize ‘dp[0]’ and ‘dp[1]’ by 1
- Run a loop from with variable ‘I’ 2 to ‘N’ and run another nested loop from 1 to ‘I’
- Update ‘dp[I]’ with ‘add(dp[i], mult(dp[j - 1], dp[i - j]))’
- Return ‘dp[N]’
Similar problems