# Leetcode 96 - Unique Binary Search Trees

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

Meet A MAANG Coach

### 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

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 `n` as input and returns the number of unique BSTs that can be created using the values 1, 2, …, `n`.

For each value `i` from 1 to `n`, we can calculate the number of unique BSTs that can be created using the values 1, 2, …, `i` as follows:

• For each value `j` from 1 to `i`, we can calculate the number of unique BSTs that can be created using the values 1, 2, …, `j-1` as the left subtree and the values `j+1`, …, `i` as the right subtree.
• The total number of unique BSTs that can be created using the values 1, 2, …, `i` is the sum of all of these values.

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

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

Meet A MAANG Coach

Related: