# LeetCode 96. Unique Binary Search Trees

## 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 = 3
Output: 5
```

Example 2:

```Input: n = 1
Output: 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).