# 96. Unique Binary Search Trees

Given an integer `n`

, return *the number of structurally unique **BST'**s (binary search trees) which has exactly *`n`

* nodes of unique values from* `1`

*to* `n`

.

**Example 1:**

**Input:** n = 3

**Output:** 5

**Example 2:**

**Input:** n = 1

**Output:** 1

**Constraints:**

`1 <= n <= 19`

Approach 1:

*Dynamic Programming*

As we can see ,

- number of unique BST for a tree with n=1 is 1
- number of unique BST for a tree with n=2 is 2
- number of unique BST for a tree with n=3 is

This is nothing but Catalan’s number

Cn=C0*Cn-1 +C1*Cn-2….. +Cn-1*C0

The code is given below

`class Solution(object):`

def numTrees(self, n):

dp=[0 for i in range(n+2)]

dp[0]=1

dp[1]=1

dp[2]=2

for i in range(2,n+1):

sum_=0

for j in range(0,i):

m,k=j,i-1-j

sum_+=dp[m]*dp[k]

dp[i]=sum_

return dp[n]

Time : O(n²)

Space: O(n)

Approach 2:

Using formula

Simplifying the Catalans number we get

Cn = 2nCn/n+1

`class Solution(object):`

def numTrees(self, n):

return(math.factorial(2*n)/(math.factorial(n)*math.factorial(n+1)))

Assuming the factorial function takes of order of n time.

Time :O(n)

Space :O(1)