Unique Binary Search Trees

Problem

Given n, return the number of structurally unique BSTs with n nodes (values 1 to n).

Key insight: G(n) = sum over i=1..n of G(i-1) * G(n-i) — this is the Catalan number formula.

Solutions

// C
int numTrees(int n) {
    int dp[20] = {0};
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            dp[i] += dp[j-1] * dp[i-j];
    return dp[n];
}

// C++
int numTrees(int n) {
    vector<int> dp(n+1, 0);
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            dp[i] += dp[j-1] * dp[i-j];
    return dp[n];
}

// Java
public int numTrees(int n) {
    int[] dp = new int[n+1];
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            dp[i] += dp[j-1] * dp[i-j];
    return dp[n];
}

// JavaScript
function numTrees(n) {
    const dp = Array(n+1).fill(0);
    dp[0] = dp[1] = 1;
    for (let i = 2; i <= n; i++)
        for (let j = 1; j <= i; j++)
            dp[i] += dp[j-1] * dp[i-j];
    return dp[n];
}

# Python
def numTrees(n):
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        for j in range(1, i + 1):
            dp[i] += dp[j - 1] * dp[i - j]
    return dp[n]

Complexity

Time: O(n²)
Space: O(n)

Pattern — Catalan Numbers

C(0)=1, C(1)=1, C(2)=2, C(3)=5, C(4)=14, C(5)=42... Formula: C(n) = C(2n, n) / (n+1)