# Leetcode 96 - Unique Binary Search Trees

### Grow Your Tech Career. Meet Expert coaches from top companies

### Understanding the problem

LeetCode 96 is a problem where you are given a positive integer ** n** and you need to find the number of unique binary search trees (BSTs) that can be created using the values 1, 2, …,

**.**

`n`

Here is an example:

Input: n = 3

Output: 5

### Plan your solution

To solve this problem, we can use dynamic programming. We can start by calculating the number of BSTs that can be created using the values 1, 2, …, ** n-1**, and then use that information to calculate the number of BSTs that can be created using the values 1, 2, …,

**.**

`n`

To do this, we can use a recursive function ** numTrees**, which takes an integer

**as input and returns the number of unique BSTs that can be created using the values 1, 2, …,**

`n`

**.**

`n`

For each value ** i** from 1 to

**, we can calculate the number of unique BSTs that can be created using the values 1, 2, …,**

`n`

**as follows:**

`i`

- For each value
from 1 to`j`

, we can calculate the number of unique BSTs that can be created using the values 1, 2, …,`i`

as the left subtree and the values`j-1`

, …,`j+1`

as the right subtree.`i`

- The total number of unique BSTs that can be created using the values 1, 2, …,
is the sum of all of these values.`i`

### Implement your solution

Here is the implementation of the ** numTrees** function:

```
class Solution:
def numTrees(self, n: int) -> int:
# Base case: if n is 0 or 1, there is only 1 BST that can be created
if n == 0 or n == 1:
return 1
# Initialize the total number of BSTs to 0
total = 0
# For each value i from 1 to n
for i in range(1, n+1):
# Calculate the number of BSTs that can be created using the values 1, 2, ..., i-1 as the left subtree
left = self.numTrees(i-1)
# Calculate the number of BSTs that can be created using the values i+1, ..., n as the right subtree
right = self.numTrees(n-i)
# Add the product of the left and right subtrees to the total number of BSTs
total += left * right
# Return the total number of BSTs
return total
```

### Test your solution

Here are test cases that you can use to test the ** numTrees** function:

```
# Test case 1
n = 0
expected_output = 1
assert Solution().numTrees(n) == expected_output
# Test case 2
n = 1
expected_output = 1
assert Solution().numTrees(n) == expected_output
# Test case 3
n = 2
expected_output = 2
assert Solution().numTrees(n) == expected_output
# Test case 4
n = 3
expected_output = 5
assert Solution().numTrees(n) == expected_output
# Test case 5
n = 4
expected_output = 14
assert Solution().numTrees(n) == expected_output
```

### Grow Your Tech Career. Meet Expert coaches from top companies

**Related:**