Given N, The task is to find the total number of unique BSTs that can be made using values from 1 to N.
Examples:
Input: N = 3
Output: 5
Explanation: For N = 3, preorder traversal of Unique BSTs are:
1 2 3
1 3 2
2 1 3
3 1 2
3 2 1Input: N = 4
Output: 14
Approach:
The solution is based on Dynamic Programming. For all possible values of i, consider i as root, then [1 . . . i-1] numbers will fall in the left subtree and [i+1 . . . N] numbers will fall in the right subtree.
The count of all possible BST’s will be count(N) = summation of (count(i-1)*count(N-i)) where i lies in the range [1, N].
Follow the below steps to Implement the idea:
- Create an array DP of size n+1
- DP[0] = 1 and DP[1] = 1.
- Run for loop from i = 2 to i <= n
- Run a loop from j = 1 to j <= i
- DP[i] = DP[i] + (DP[i – j] * DP[j – 1])
- Run a loop from j = 1 to j <= i
- Return DP[n]
Below is the implementation of the above approach:
C++
// C++ code to find number of unique BSTs// Dynamic Programming solution#include <bits/stdc++.h>using namespace std;// Function to find number of unique BSTint numberOfBST(int n){ // DP to store the number of unique BST with key i int dp[n + 1]; fill_n(dp, n + 1, 0); // Base case dp[0] = 1; dp[1] = 1; // fill the dp table in bottom-up approach. for (int i = 2; i <= n; i++) { for (int j = 1; j <= i; j++) { // n-i in right * i-1 in left dp[i] = dp[i] + (dp[i - j] * dp[j - 1]); } } return dp[n];}// Driver Codeint main(){ int N = 3; // Function call cout << "Number of structurally Unique BST with " << N << " keys are : " << numberOfBST(N) << "\n"; return 0;}// This code is contributed by Aditya kumar (adityakumar129) |
C
// C code to find number of unique BSTs// Dynamic Programming solution#include <stdio.h>// DP to store the number of unique BST with key iint dp[20];// Function to find number of unique BSTint numberOfBST(int n){ // Base case if (n <= 1) return 1; // In case if the value is already present in the array // just return it and no need to calculate it if (dp[n]) return dp[n]; for (int i = 1; i <= n; i++) dp[n] += numberOfBST(i - 1) * numberOfBST(n - i); return dp[n];}// Driver Codeint main(){ int N = 3; // Function call printf("Number of structurally Unique BST with %d keys " "are : %d", N, numberOfBST(N)); return 0;}// This code is contributed by Aditya kumar (adityakumar129) |
Java
// Java code to find number// of unique BSTs Dynamic// Programming solutionimport java.io.*;import java.util.Arrays;class GFG { public static int dp[] = new int[20]; static int numberOfBST(int n) { // Base case if (n <= 1) return 1; // In case if the value is already present in the // array just return it and no need to calculate it if (dp[n] > 0) return dp[n]; for (int i = 1; i <= n; i++) dp[n] += numberOfBST(i - 1) * numberOfBST(n - i); return dp[n]; } // Driver Code public static void main(String[] args) { int n = 3; System.out.println("Number of structurally " + "Unique BST with " + n + " keys are : " + numberOfBST(n)); }}// This code is contributed by Aditya kumar (adityakumar129) |
Python3
# Python3 code to find number of unique# BSTs Dynamic Programming solution# Function to find number of unique BSTdef numberOfBST(n): # DP to store the number of unique # BST with key i dp = [0] * (n + 1) # Base case dp[0], dp[1] = 1, 1 # fill the dp table in top-down # approach. for i in range(2, n + 1): for j in range(1, i + 1): # n-i in right * i-1 in left dp[i] = dp[i] + (dp[i - j] * dp[j - 1]) return dp[n]# Driver Codeif __name__ == "__main__": n = 3 print("Number of structurally Unique BST with", n, "keys are :", numberOfBST(n))# This code is contributed# by Rituraj Jain |
C#
// C# code to find number// of unique BSTs Dynamic// Programming solutionusing System;class GFG { static int numberOfBST(int n) { // DP to store the number // of unique BST with key i int[] dp = new int[n + 1]; // Base case dp[0] = 1; dp[1] = 1; // fill the dp table in // top-down approach. for (int i = 2; i <= n; i++) { for (int j = 1; j <= i; j++) { // n-i in right * i-1 in left dp[i] = dp[i] + (dp[i - j] * dp[j - 1]); } } return dp[n]; } // Driver Code public static void Main() { int n = 3; Console.Write("Number of structurally " + "Unique BST with " + n + " keys are : " + numberOfBST(n)); }}// This code is contributed// by shiv_bhakt. |
PHP
<?php// PHP code to find number // of unique BSTs Dynamic// Programming solution// Function to find number // of unique BSTfunction numberOfBST($n){ // DP to store the number // of unique BST with key i $dp = array($n + 1); for($i = 0; $i <= $n + 1; $i++) $dp[$i] = 0; // Base case $dp[0] = 1; $dp[1] = 1; // fill the dp table // in top-down approach. for ($i = 2; $i <= $n; $i++) { for ($j = 1; $j <= $i; $j++) { // n-i in right * // i-1 in left $dp[$i] += (($dp[$i - $j]) * ($dp[$j - 1])); } } return $dp[$n];}// Driver Code$n = 3;echo "Number of structurally ". "Unique BST with " , $n , " keys are : " , numberOfBST($n) ;// This code is contributed// by shiv_bhakt.?> |
Javascript
<script>// javaScript code to find number of unique // BSTs Dynamic Programming solution // Function to find number of unique BST function numberOfBST(n){ // DP to store the number of unique // BST with key i let dp = new Array(n + 1).fill(0) // Base case dp[0] = 1, dp[1] = 1 // fill the dp table in top-down // approach. for(let i=2;i<n + 1;i++){ for(let j=1;j<i + 1;j++){ // n-i in right * i-1 in left dp[i] = dp[i] + (dp[i - j] * dp[j - 1]) } } return dp[n] }// Driver Code let n = 3document.write("Number of structurally Unique BST with", n, "keys are :", numberOfBST(n)) // This code is contributed by shinjanpatra</script> |
Output
Number of structurally Unique BST with 3 keys are : 5
Time Complexity: O(N2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
