# 15. Unique Binary Search Trees

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`.

**Example 1:**

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

```
Input: n = 3
Output: 5
```

**Example 2:**

```
Input: n = 1
Output: 1
```

## Approach

**If we take a no of as root as its left subtree has 3 combinations and right subtree has 4 combinations total combinations for R = 3 \* 4**

![](https://1416717093-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-ME49AWTsL3PV5O3FW36%2F-MWhIk1oSds2ZtqdyX-X%2F-MWhIztWpsCJxDQEEAVE%2Fbst.png?alt=media\&token=bc76055d-8d72-466f-9dac-ba15fda58a84)

**If total no of nodes are 4**\
**We can make each node as root once**\
**and count the combinations and add them.**

![](https://1416717093-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-ME49AWTsL3PV5O3FW36%2F-MWhIk1oSds2ZtqdyX-X%2F-MWhJMXHXbjTx-tI57aP%2Fbst2.png?alt=media\&token=84626d10-8cb8-4727-aa8f-1b444ca9f8a0)

## Solution: (DP)

```
class Solution
{
public:
    int numTrees(int n)
    {

        vector<int> dp(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];
    }
};
```
