# 96. Unique Binary Search Trees

## Problem Statement

<br>

Given an integer `n`, return *the number of structurally unique **BST'**&#x73; (binary search trees) which has exactly* `n` *nodes of unique values from* `1` *to* `n`.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg)

<pre><code><strong>Input: n = 3
</strong><strong>Output: 5
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: n = 1
</strong><strong>Output: 1
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= n <= 19`<br>

## Intuition

```
Approach 1: Formula

        /*
        2n
         C
          n
        ----
        (n+1)

        Catalan number

        Since Double loses precision 
        We use repetative approach to calculate

        nCk

        6C3 = 6*5*4/3*2*1
        Run for 1 to k  
        at each step multiply by n and divide by 1
        */

Approach 2 :

Using Dp

Lets take n = 2
  1 2 
Root as 1 ; Left = 0 right = 1 elements
Root as 2 ; Left = 1 right = 0 elements

n = 3
0 2
1 1
2 0
Add all 

So on

Total n elements -> i ) 1 ( n-i-1 



```

### Links

<https://leetcode.com/problems/unique-binary-search-trees/description/>

### Video Links

### Approach 1:

```
Catalan Formula Approach
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int numTrees(int n) {
        long long ans = 1;
        int x = 2*n;

        for(int i=1; i<=n; i++){
            ans *= x;
            x--;
            ans /= i;
        }

        return ans / (n+1);

        /*
        2n
         C
          n
        ----
        (n+1)

        Catalan number

        Since Double loses precision 
        We use repetative approach to calculate

        nCk

        6C3 = 6*5*4/3*2*1
        Run for 1 to k  
        at each step multiply by n and divide by 1
        */
    }
};
```

{% endcode %}

### Approach 2:

```
Memoization    
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    unordered_map<int,int> mp;
    int numTrees(int n) {
        if(n == 1 or n == 0)
            return 1;

        if(mp.find(n) != mp.end())
            return mp[n];

        int ans = 0;

        for(int i=0; i<n; i++)
            ans += numTrees(i) * numTrees(n-i-1);

        return mp[n] = ans;
    }
};
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###