96. Unique Binary Search Trees

Description

The numTrees function computes the number of unique binary search trees (BSTs) that can be formed with n distinct nodes, where each node contains values from 1 to n. This problem is a classic example of dynamic programming and is related to the Catalan numbers.

Intuition

The key observation is that the number of unique BSTs that can be formed with n nodes is determined by considering each value as a possible root and calculating the number of possible left and right subtrees recursively. Specifically, for each possible root k, the left subtree must contain nodes with values less than k, and the right subtree must contain nodes with values greater than k. The total number of BSTs is the sum of the products of the number of possible left and right subtrees for each possible root.

Approach

1. Dynamic Programming Array: - Initialize an array sol of size n+1 to store the number of unique BSTs for each number of nodes from 0 to n. Set sol[0] and sol[1] to 1, as there is exactly one BST that can be formed with 0 or 1 node.
2. Filling the DP Array: - Iterate over the number of nodes i from 2 to n. - For each i, iterate over possible root values j from 1 to i. - For each root value j, the number of unique BSTs with i nodes is the sum of the products of the number of BSTs that can be formed with j-1 nodes on the left (stored in sol[j-1]) and the number of BSTs that can be formed with i-j nodes on the right (stored in sol[i-j]).
3. Final Result: - After filling the DP array, the value sol[n] gives the number of unique BSTs that can be formed with n nodes.

Complexity

Time Complexity:

The time complexity is (O(n^2)), where n is the input number. This is because, for each number of nodes i, we iterate through all possible root values j, leading to a nested loop structure.

Space Complexity:

The space complexity is (O(n)), where n is the size of the DP array sol. This array stores the number of unique BSTs for each possible number of nodes from 0 to n.

Code

C++

class Solution {
public:
    int numTrees(int n) {
        // Create 'sol' vector to store the solution...
        std::vector sol(n + 1, 0);
        sol[0] = sol[1] = 1;

        // Run a loop from 2 to n...
        for (int i = 2; i <= n; i++) {
            // Within the above loop, run a nested loop from 1 to i...
            for (int j = 1; j <= i; j++) {
                // Update the i-th position of the vector by adding the multiplication of the respective index...
                sol[i] += sol[i - j] * sol[j - 1];
            }
        }
        // Return the value of the nth index of the vector to get the solution...
        return sol[n];
    }
};

Python

class Solution:
    def numTrees(self, n: int) -> int:
        # Create 'sol' list to store the solution...
        sol = [0] * (n + 1)
        sol[0], sol[1] = 1, 1

        # Run a loop from 2 to n...
        for i in range(2, n + 1):
            # Within the above loop, run a nested loop from 1 to i...
            for j in range(1, i + 1):
                # Update the i-th position of the list by adding the multiplication of the respective index...
                sol[i] += sol[i - j] * sol[j - 1]
                
        # Return the value of the nth index of the list to get the solution...
        return sol[n]

Java

class Solution {
    public int numTrees(int n) {
        // Create 'sol' array to store the solution...
        int[] sol = new int[n + 1];
        sol[0] = sol[1] = 1;

        // Run a loop from 2 to n...
        for (int i = 2; i <= n; i++) {
            // Within the above loop, run a nested loop from 1 to i...
            for (int j = 1; j <= i; j++) {
                // Update the i-th position of the array by adding the multiplication of the respective index...
                sol[i] += sol[i - j] * sol[j - 1];
            }
        }
        // Return the value of the nth index of the array to get the solution...
        return sol[n];
    }
}

JavaScript

var numTrees = function (n) {
    // Create 'sol' array to store the solution...
    var sol = [1, 1];
    // Run a loop from 2 to n...
    for (let i = 2; i <= n; i++) {
        sol[i] = 0;
        // Within the above loop, run a nested loop from 1 to i...
        for (let j = 1; j <= i; j++) {
            // Update the i-th position of the array by adding the multiplication of the respective index...
            sol[i] += sol[i - j] * sol[j - 1];
        }
    }
    // Return the value of the nth index of the array to get the solution...
    return sol[n];
};