Leetcode 96 - Unique Binary Search Trees

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

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

Related:

• binary subarrays with sum
• count complete tree nodes
• search in rotated sorted array
• binary search