### 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:

## 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 = 1;
dp = 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