Unique Binary Search Trees

XXX. Unique Binary Search Trees

Dynamic Programming

Recursion

Problem Statement:

Given an integer n, return the number of structurally unique binary search trees (BSTs) that store values 1 to n.

Algorithm:

1. Use dynamic programming to store the results of subproblems in an array dp.
2. Define the base cases: dp[0] = dp[1] = 1 (one unique BST for empty tree or single node).
3. Compute the number of unique BSTs using two approaches:
   • Top-Down: Use recursion with memoization to calculate the result for each subproblem.
   • Bottom-Up: Iteratively build the solution by calculating the result for smaller values of n first.

Complexity:

Time Complexity: O(n²), where n is the given input.
Space Complexity: O(n) for the dynamic programming array.

Java Implementation:

public class Solution {
    // Top-Down Solution with Recursion and Memoization
    public int numTrees(int n) {
        int[] dp = new int[n + 1]; // Create DP array to store intermediate results
        dp[0] = dp[1] = 1; // Base cases: 1 BST for 0 or 1 node
        return numTreesHelper(n, dp);
    }

    private int numTreesHelper(int n, int[] dp) {
        if (dp[n] != 0) return dp[n]; // Return result if already computed

        int count = 0;
        for (int i = 1; i <= n; i++) 
            count += numTreesHelper(i - 1, dp) * numTreesHelper(n - i, dp); // Calculate left and right combinations
        

        dp[n] = count; // Store the result in DP array
        return count;
    }

    // Bottom-Up Solution
    public int numTreesBottomUp(int n) {
        int[] dp = new int[n + 1]; // DP array to store results
        dp[0] = dp[1] = 1; // Base cases

        for (int i = 2; i <= n; ++i) // Iterate over the number of nodes
            for (int j = 1; j <= i; ++j) // Consider each node as the root
                dp[i] += dp[j - 1] * dp[i - j]; // Calculate left and right combinations
            
        

        return dp[n]; // Return the result for n nodes
    }
}
                

Python Implementation:

def num_trees(n):
    # Top-Down Solution with Recursion and Memoization
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1  # Base cases

    def helper(n):
        if dp[n] != 0:
            return dp[n]  # Return result if already computed

        count = 0
        for i in range(1, n + 1):
            count += helper(i - 1) * helper(n - i)  # Calculate left and right combinations

        dp[n] = count  # Store the result in DP array
        return count

    return helper(n)

def num_trees_bottom_up(n):
    # Bottom-Up Solution
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1  # Base cases

    for i in range(2, n + 1):  # Iterate over the number of nodes
        for j in range(1, i + 1):  # Consider each node as the root
            dp[i] += dp[j - 1] * dp[i - j]  # Calculate left and right combinations

    return dp[n]  # Return the result for n nodes
                

C++ Implementation:

#include 
using namespace std;

// Top-Down Solution with Recursion and Memoization
int numTreesHelper(int n, vector& dp) {
    if (dp[n] != 0) return dp[n]; // Return result if already computed

    int count = 0;
    for (int i = 1; i <= n; ++i) {
        count += numTreesHelper(i - 1, dp) * numTreesHelper(n - i, dp); // Calculate left and right combinations
    }

    dp[n] = count; // Store the result in DP array
    return count;
}

int numTrees(int n) {
    vector dp(n + 1, 0); // Create DP array to store intermediate results
    dp[0] = dp[1] = 1; // Base cases
    return numTreesHelper(n, dp);
}

// Bottom-Up Solution
int numTreesBottomUp(int n) {
    vector dp(n + 1, 0); // DP array to store results
    dp[0] = dp[1] = 1; // Base cases

    for (int i = 2; i <= n; ++i) { // Iterate over the number of nodes
        for (int j = 1; j <= i; ++j) { // Consider each node as the root
            dp[i] += dp[j - 1] * dp[i - j]; // Calculate left and right combinations
        }
    }

    return dp[n]; // Return the result for n nodes
}