algoadvance

LeetCode 96: Unique Binary Search Trees

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

Clarifying Questions

  1. Range of n: What are the constraints on the value of n?
    • Typically, n ranges from 1 to about 19 based on practical problem constraints.
  2. Unique values: Do the nodes indeed have to be unique values from 1 to n?
    • Yes, they are unique and range from 1 to n.
  3. Expected output: Is the output just the count of unique BSTs?
    • Yes, just the count is required.

Strategy

The number of unique BSTs that can be formed with n nodes is given by the nth Catalan number. We can compute this using dynamic programming.

Here is the detailed breakdown:

  1. Dynamic Programming (DP) Array Definition:
    • Let dp[i] represent the number of unique BSTs that can be formed with i nodes.
  2. Initial State:
    • dp[0] = 1 (empty tree is considered as one BST).
    • dp[1] = 1 (one node tree has exactly one structure).
  3. Filling DP Table:
    • For each i from 2 to n, calculate dp[i] by summing the product of the counts of left and right subtrees.
    • The left subtree can have j nodes, and right subtree can have i-j-1 nodes (for every possible root).

    The formula for dp[i] becomes:

    dp[i] = sum(dp[j] * dp[i-j-1] for j in range(0, i))

Code

Here’s the implementation in Python:

def numTrees(n: int) -> int:
    if n == 0:
        return 1
        
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    
    for i in range(2, n + 1):
        total = 0
        for j in range(i):
            total += dp[j] * dp[i-j-1]
        dp[i] = total
        
    return dp[n]

# Test case
print(numTrees(3))  # Output should be 5

Time Complexity

The time complexity of this algorithm is (O(n^2)) because we have a nested loop where for each i from 2 to n, we sum up to i terms.

Space complexity is (O(n)) for storing the DP array.

This approach ensures that we compute the number of unique BSTs efficiently using dynamic programming, taking care of the subproblem dependencies naturally.

Try our interview co-pilot at AlgoAdvance.com