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

Related Posts

• Leetcode 424 - Longest Repeating Character Replacement
• Two Sum and Its Variants
• Leetcode 1004 - Max Consecutive Ones III
• Leetcode 222 - Count Complete Tree Nodes
• Leetcode 1027 - Longest Arithmetic Subsequence
• Question 1299 on leetcode
• Leetcode 240 - Search a 2D Matrix II
• Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
• Leetcode 239 - Sliding Window Maximum
• Leetcode 209 - Minimum Size Subarray Sum
• LeetCode 230 - Kth Smallest Element in a BST with Code
• advanced-applications-of-binary-search
• Leetcode 540 - Single Element in a Sorted Array
• Leetcode 1283 - Find the Smallest Divisor Given a Threshold
• Leetcode 74 - Search a 2D Matrix
• Leetcode 300 - Longest Increasing Subsequence
• Leetcode 930 - Binary Subarrays With Sum
• Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
• Leetcode 704 - Binary Search
• Leetcode 643 - Maximum Average Subarray I
• LeetCode - Two Sum Solution with Code
• a-binary-search-template
• Leetcode 1358 - Number of Substrings Containing All Three Characters
• Leetcode 33 - Search in Rotated Sorted Array
• Leetcode 1151 - Minimum Swaps to Group All 1’s Together