## Description

https://leetcode.com/problems/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 = 3Output:5

**Example 2:**

Input:n = 1Output:1

**Constraints:**

`1 <= n <= 19`

## Explanation

For 0 <= i <= n, all values less than i go to the left tree, all values greater than i go to the right tree. Count how many possible ways to build a left tree and how many possible ways to build a right tree, and multiply the count to get the result.

## Python Solution

```
class Solution:
def numTrees(self, n: int) -> int:
results = {
0: 1,
1: 1,
2: 2
}
return self.helper(n, results)
def helper(self, n , results):
if n in results:
return results[n]
else:
result = 0
for i in range(n):
result += self.helper(i, results) * self.helper(n - i - 1, results)
results[n] = result
return result
```

- Time Complexity: O(N^2).
- Space Complexity: O(N).

I found that solution very popular and helpful:

https://www.youtube.com/watch?v=ElV3nrMaso8&ab_channel=EricProgramming