We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Unique Binary Search Trees

Difficulty: Medium

Problem Description

Given an integer n, return the number of structurally unique BSTs (binary search trees) which have exactly n nodes of unique values from 1 to n.

Key Insights

  • The number of unique BSTs can be calculated using Catalan numbers.
  • A BST with n nodes has a root node and left and right subtrees.
  • For each node i (1 to n), the number of unique BSTs can be calculated by considering i as the root and multiplying the number of unique BSTs formed by the left and right subtrees.
  • This leads to a recursive formula: C(n) = ∑ (C(i-1) * C(n-i)) for i from 1 to n, where C(0) = 1.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

To solve the problem, we can use dynamic programming to build up the number of unique BSTs for each number of nodes from 1 to n. We use an array to store the results of subproblems, where each index represents the number of nodes. The final result will be stored in the last index of the array.

Code Solutions

def numTrees(n: int) -> int:
    # Create an array to store the number of unique BSTs for each number of nodes
    dp = [0] * (n + 1)
    # Base case: There is one unique BST for 0 nodes and one unique BST for 1 node
    dp[0], dp[1] = 1, 1

    # Fill the dp array for all nodes from 2 to n
    for nodes in range(2, n + 1):
        for root in range(1, nodes + 1):
            # The number of unique BSTs is the product of the left and right subtrees
            dp[nodes] += dp[root - 1] * dp[nodes - root]
    
    return dp[n]
← Back to All Questions