### 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[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**

- Height of a Binary Tree
- Find Minimum Depth of Binary Tree
- How to invert a binary tree
- Find Number of Islands
- Search in Rotated Array

## Comments

## Post a Comment