Given an integer n, return the number of structurally unique BST’s (binary search trees) that have exactly n nodes with values from 1 to n.

Examples

Example 1:

Input: n = 3
Output: 5
Explanation: For n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Example 2:

Input: n = 1
Output: 1

Constraints

  • 1 <= n <= 19

Thinking Process

There are three main approaches to solve this problem:

  1. Dynamic Programming: Build up the solution using the recurrence relation
  2. Catalan Numbers: Use the mathematical formula for Catalan numbers
  3. Optimized DP: Slight variations in DP implementation

The key insight is that the number of unique BSTs follows the Catalan number sequence.

BST count: split at root root = 2 2 1 3 C(1) C(1) C(n) = Σ C(j-1)·C(n-j) pick root j, multiply subtrees

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Solution

class Solution {
        public int numTrees(int n) {
        public int[] cache(n + 1, 1);
        for(int i = 2; i <= n; i++) {
        int sum = 0;
            for(int j = 1; j <= i; j++) {
                int left = j - 1;
                int right = i - j;
                sum += cache[left] * cache[right];
            }
            cache[i] = sum;
        }
        return cache[n];
    }
}

Solution Explanation

Approach: 1D DP (this problem)

Key idea: There are three main approaches to solve this problem:

How the code works:

  1. Dynamic Programming: Build up the solution using the recurrence relation
  2. Catalan Numbers: Use the mathematical formula for Catalan numbers
  3. Optimized DP: Slight variations in DP implementation

Walkthrough — input n = 3, expected output 5:

For n = 3, there are a total of 5 unique BST’s:

Step-by-Step Example (Solution 1)

For n = 3:

  1. Initial: cache = [1, 1, 1, 1]
  2. i = 2:
    • j = 1: left = 0, right = 1 → cache[0] * cache[1] = 1 * 1 = 1
    • j = 2: left = 1, right = 0 → cache[1] * cache[0] = 1 * 1 = 1
    • cache[2] = 1 + 1 = 2
  3. i = 3:
    • j = 1: left = 0, right = 2 → cache[0] * cache[2] = 1 * 2 = 2
    • j = 2: left = 1, right = 1 → cache[1] * cache[1] = 1 * 1 = 1
    • j = 3: left = 2, right = 0 → cache[2] * cache[0] = 2 * 1 = 2
    • cache[3] = 2 + 1 + 2 = 5

Final result: 5

Mathematical Insight

The number of unique BSTs with n nodes is the n-th Catalan number:

C(n) = (2n)! / ((n+1)! * n!) = (1/(n+1)) * C(2n,n)

The recurrence relation is: C(n) = Σ(i=1 to n) C(i-1) * C(n-i)

Common Mistakes

  1. Not understanding the recurrence relation for BST counting
  2. Integer overflow in Catalan number calculation
  3. Incorrect base cases in DP approach
  4. Confusing with permutation problems instead of combination
  • n = 1: return 1 (single node)
  • n = 2: return 2 (two possible BSTs)
  • n = 0: return 1 (empty tree)

References

Key Takeaways

  1. Recurrence Relation: For each root i, left subtree has i-1 nodes, right subtree has n-i nodes
  2. Catalan Numbers: The sequence follows Catalan number pattern
  3. Dynamic Programming: Build up solutions from smaller subproblems
  4. Mathematical Formula: Direct calculation using Catalan number formula