Number of Unique BST with a given key | Dynamic Programming

0 0 5 minutes read

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 1

Input: 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])
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 BST
int 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 Code
int 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 i
int dp[20];
 
// Function to find number of unique BST
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])
        return dp[n];
    for (int i = 1; i <= n; i++)
        dp[n] += numberOfBST(i - 1) * numberOfBST(n - i);
    return dp[n];
}
 
// Driver Code
int 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 solution
import 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 BST
 
 
def 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 Code
if __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 solution
using 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 BST
function 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 = 3
document.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(N²)
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 zambiatek!