Code Implementation

class Solution:
    def numTrees(self, n: int) -> int:
        # dp[i] will store the number of unique BSTs with i nodes
        dp = [0] * (n + 1)
        dp[0] = 1  # Empty tree
        dp[1] = 1  # Single node tree

        for nodes in range(2, n + 1):
            for root in range(1, nodes + 1):
                left = root - 1
                right = nodes - root
                dp[nodes] += dp[left] * dp[right]
        return dp[n]
    

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;
        for (int nodes = 2; nodes <= n; ++nodes) {
            for (int root = 1; root <= nodes; ++root) {
                int left = root - 1;
                int right = nodes - root;
                dp[nodes] += dp[left] * dp[right];
            }
        }
        return dp[n];
    }
};
    

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int nodes = 2; nodes <= n; nodes++) {
            for (int root = 1; root <= nodes; root++) {
                int left = root - 1;
                int right = nodes - root;
                dp[nodes] += dp[left] * dp[right];
            }
        }
        return dp[n];
    }
}
    

var numTrees = function(n) {
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    for (let nodes = 2; nodes <= n; nodes++) {
        for (let root = 1; root <= nodes; root++) {
            let left = root - 1;
            let right = nodes - root;
            dp[nodes] += dp[left] * dp[right];
        }
    }
    return dp[n];
};
    

Problem Description

Given an integer n, find how many structurally unique binary search trees (BSTs) can be formed using all the values from 1 to n. Each value from 1 to n must be used exactly once in each BST. The structure of the BSTs must be unique, not just the values.

• Each tree must be a valid binary search tree.
• All n values must be used in each tree, with no repetitions.
• Return the total number of unique BST structures possible with n nodes.

Thought Process

At first glance, it seems like we could try to generate all possible BSTs with n nodes and count them. However, this brute-force approach quickly becomes infeasible as n increases, since the number of trees grows rapidly.

Instead, we should look for a pattern or recursive relationship. Since the root of the BST can be any value between 1 and n, and the left and right subtrees are themselves BSTs with the remaining numbers, we can break the problem into smaller subproblems.

The key insight is to realize that the number of unique BSTs for n nodes is determined by the number of unique BSTs on the left and right of each possible root. This leads us toward a dynamic programming or recursive solution.

Solution Approach

• Subproblem Definition: Let dp[i] represent the number of unique BSTs that can be constructed with i nodes.
• Base Cases:
  • dp[0] = 1 (an empty tree is a valid BST)
  • dp[1] = 1 (a single node is a valid BST)
• Recursive Relation:
  • For each number root from 1 to n, consider it as the root of the BST.
  • The number of nodes in the left subtree is root - 1, and in the right subtree is n - root.
  • The total number of BSTs with n nodes and root as the root is dp[root-1] * dp[n-root].
  • Sum this quantity over all possible roots to get dp[n].
• Dynamic Programming:
  • Build up the dp array iteratively from 2 to n using the above relation.
  • Return dp[n] as the result.

This approach avoids redundant computation by storing results for subproblems, making it very efficient.

Example Walkthrough

Let's work through an example with n = 3:

• Possible roots: 1, 2, or 3.
• Root = 1:
  • Left subtree: 0 nodes (dp[0] = 1), Right subtree: 2 nodes (dp[2])
• Root = 2:
  • Left subtree: 1 node (dp[1] = 1), Right subtree: 1 node (dp[1] = 1)
• Root = 3:
  • Left subtree: 2 nodes (dp[2]), Right subtree: 0 nodes (dp[0] = 1)
• Now, let's compute dp[2] first:
  • Root = 1: left = 0, right = 1 → 1 * 1 = 1
  • Root = 2: left = 1, right = 0 → 1 * 1 = 1
  • So, dp[2] = 2
• Now, for dp[3]:
  • Root = 1: 1 * 2 = 2
  • Root = 2: 1 * 1 = 1
  • Root = 3: 2 * 1 = 2
  • Total: 2 + 1 + 2 = 5
• So, there are 5 unique BSTs that can be constructed with 3 nodes.

Time and Space Complexity

• Brute-force approach: Exponential time, since it would generate all possible tree structures and check for uniqueness. This is not feasible for large n.
• Dynamic Programming approach:
  • Time Complexity: O(n^2). For each i from 2 to n, we loop through all possible roots (up to i), so the total work is proportional to the sum 1 + 2 + ... + n = O(n^2).
  • Space Complexity: O(n), since we store dp[0] to dp[n].

Summary

The Unique Binary Search Trees problem is a classic example of using dynamic programming to count combinatorial structures efficiently. By recognizing the recursive structure of BSTs and storing subproblem results, we avoid redundant computations and achieve a solution that scales well even for large n. The solution is elegant because it leverages the properties of BSTs and dynamic programming to reduce a seemingly complex problem to a simple iterative process.