Count Unique Binary Search Trees - The Coding Shala

Last Updated: 19-Jan-2021
Home >> Interview Questions >> Count Unique Binary Search Trees

 In this post, we will learn how to Count Unique Binary Search Trees and will implement its solution in Java.

Count Unique Binary Search Trees Problem

Given N, Find the total number of unique (Binary Search Trees)BSTs that can be made using values from 1 to N.

Example:
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
Unique Binary Search Trees - The Coding Shala

Count Unique Binary Search Trees Java Program

Approach 1

Using Dynamic Programming.

One way to solve this problem is we can generate a list of all possible unique binary search trees and return the size of the list.

We can use dynamic programming to solve this problem. For every value of i here i is the root, then 1 to i-1 numbers will come in the left subtree and i+1 to n numbers come in the right subtree so the answer will be a total of (i-1)*(n-i).

Time complexity: O(n^2).

Java Program: 

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala