Pseudo-code:

text
function count(n):
    if n <= 1 return 1
    total = 0
    for i from 1 to n:
        total += count(i - 1) * count(n - i)
    return total

Complexity Analysis: The time complexity of this brute force approach is exponential. Specifically, the recurrence relation $T(n) = \sum_{i=1}^{n} T(i-1)T(n-i)$ describes the Catalan numbers. Without memoization, the algorithm repeatedly solves the same subproblems (e.g., calculating count(2) multiple times for different branches of the recursion tree). For $N=19$, this would result in a massive number of redundant calculations, leading to a Time Limit Exceeded (TLE) error.

Core Insight for Unique Binary Search Trees

The crucial insight needed to move from brute force to an optimal solution is understanding how a BST is constructed relative to its root.

1. Root Selection: If we select a number $i$ ($1 \le i \le n$) as the root, all nodes in the left subtree must be less than $i$ (values $1$ to $i-1$), and all nodes in the right subtree must be greater than $i$ (values $i+1$ to $n$).
2. Structural Equivalence: The number of unique BSTs formed by a sequence of consecutive numbers depends only on the count of numbers, not their specific values. For example, the number of unique BSTs formed by $\{1, 2, 3\}$ is exactly the same as the number of unique BSTs formed by $\{4, 5, 6\}$. Both sets contain 3 elements.
3. Cartesian Product: For a fixed root $i$, the total number of unique BSTs is the product of the number of valid left subtrees and the number of valid right subtrees. This is because every unique left structure can be paired with every unique right structure.

Therefore, we can define a function $G(n)$ as the number of unique BSTs of length $n$. To calculate $G(n)$, we sum over all possible roots $j$: $G(n) = \sum_{j=1}^{n} G(j-1) \times G(n-j)$

Here, $G(j-1)$ represents the count of left subtrees (nodes smaller than root $j$), and $G(n-j)$ represents the count of right subtrees (nodes larger than root $j$).

Execution Flow

Let's trace the algorithm for n = 3.

1. Initialize DP Array: dp array of size 4 (indices 0 to 3). dp[0] = 1, dp[1] = 1.

2. Calculate dp[2] (Trees with 2 nodes):

   • Root 1: Left has 0 nodes (dp[0]), Right has 1 node (dp[1]). Product: $1 \times 1 = 1$.
   • Root 2: Left has 1 node (dp[1]), Right has 0 nodes (dp[0]). Product: $1 \times 1 = 1$.
   • Total for dp[2]: $1 + 1 = 2$.

3. Calculate dp[3] (Trees with 3 nodes):

   • Root 1: Left has 0 nodes (dp[0]), Right has 2 nodes (dp[2]). Product: $1 \times 2 = 2$.
   • Root 2: Left has 1 node (dp[1]), Right has 1 node (dp[1]). Product: $1 \times 1 = 1$.

4. Output: Return dp[3], which is 5.

Proof of Correctness

The correctness relies on the exhaustive partition property of Binary Search Trees. Every BST must have a root. If we group all valid BSTs of size $n$ by their root value, we create disjoint sets of trees. The size of the set where $k$ is the root is determined strictly by the number of ways to arrange the remaining nodes into the left and right subtrees. Since the choices for the left subtree and right subtree are independent, the Multiplication Principle applies. By summing these products for all possible roots $1$ through $n$, we guarantee that every structurally unique BST is counted exactly once.

Reference Implementation

C++ Solution for LeetCode 96

cpp
class Solution {
public:
    int numTrees(int n) {
        // dp[i] stores the number of unique BSTs with i nodes
        std::vector<int> dp(n + 1, 0);
        
        // Base cases
        dp[0] = 1; // Empty tree
        dp[1] = 1; // Single node tree
        
        // Build up the solution for lengths 2 to n
        for (int i = 2; i <= n; ++i) {
            // Iterate through all possible roots j for a tree of length i
            for (int j = 1; j <= i; ++j) {
                // dp[i] += (left subtrees count) * (right subtrees count)
                // Left subtree has j-1 nodes
                // Right subtree has i-j nodes
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        
        return dp[n];
    }
};

Java Solution for LeetCode 96

java
class Solution {
    public int numTrees(int n) {
        // dp[i] stores the number of unique BSTs with i nodes
        int[] dp = new int[n + 1];
        
        // Base cases
        dp[0] = 1; // Empty tree
        dp[1] = 1; // Single node tree
        
        // Build up the solution for lengths 2 to n
        for (int i = 2; i <= n; i++) {
            // Iterate through all possible roots j for a tree of length i
            for (int j = 1; j <= i; j++) {
                // dp[i] += (left subtrees count) * (right subtrees count)
                // Left subtree has j-1 nodes
                // Right subtree has i-j nodes
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        
        return dp[n];
    }
}

Python Solution for LeetCode 96

python
class Solution:
    def numTrees(self, n: int) -> int:
        # dp[i] stores the number of unique BSTs with i nodes
        dp = [0] * (n + 1)
        
        # Base cases
        dp[0] = 1  # Empty tree
        dp[1] = 1  # Single node tree
        
        # Build up the solution for lengths 2 to n
        for i in range(2, n + 1):
            # Iterate through all possible roots j for a tree of length i
            for j in range(1, i + 1):
                # dp[i] += (left subtrees count) * (right subtrees count)
                # Left subtree has j-1 nodes
                # Right subtree has i-j nodes
                dp[i] += dp[j - 1] * dp[i - j]
                
        return dp[n]