Unique Binary Search Trees

Problem

Given an integer n, return the number of structurally distinct BSTs that store the values 1, 2, …, n.

Intuition

Pick a root. Say you root the tree at value i. Then:

• The left subtree must hold values 1..=i-1 — that's i - 1 values, arranged as a BST.
• The right subtree must hold values i+1..=n — that's n - i values, arranged as a BST.

Crucially, the count of BSTs depends only on the size, not the specific values: dp[k] = "how many BSTs can you build with k distinct ordered values?" The root i splits n total values into i - 1 on the left and n - i on the right, and the two subtrees are independent. Multiply their counts; sum over all root choices:

dp[n] = Σ_{i=1..n} dp[i - 1] * dp[n - i]

Base: dp[0] = 1 (the empty tree counts as one structure) and dp[1] = 1.

This is the Catalan recurrence. The sequence 1, 1, 2, 5, 14, 42, 132, … counts dozens of combinatorial structures: balanced parentheses, non-crossing chord diagrams, monotonic lattice paths, full binary trees. The BST count is the tree-shaped instance of that family.

Approach

impl Solution {
    pub fn num_trees(n: i32) -> i32 {
        let n = n as usize;
        let mut dp = vec![0i64; n + 1];
        dp[0] = 1;
        for k in 1..=n {
            for i in 1..=k {
                dp[k] += dp[i - 1] * dp[k - i];
            }
        }
        dp[n] as i32
    }
}

function numTrees(n: number): number {
  const dp = new Array<number>(n + 1).fill(0);
  dp[0] = 1;
  for (let k = 1; k <= n; k++) {
    for (let i= 1; i <= k; i++) {
      dp[k] = dp[i - 1] * dp[k - i];
    }
  }
  return dp[n];
}

Trace

Fill for n = 3:

Return dp[3] = 5. ✓

Edge cases

• n = 0 — return 1 (the empty tree). The LC problem guarantees n ≥ 1, but the DP handles it for free via dp[0] = 1.
• n = 19 — 1,767,263,190, still fits in i32. n = 20 would overflow; LC bounds the input accordingly.
• Large n off-platform — switch to i64 or BigInt, or use the closed form.

Takeaway

When a problem asks "how many structures of size n?" and you can split it by a pivot choice, the answer is often Catalan. The template is: fix a pivot, multiply independent sub-counts, sum over pivot choices. That's Catalan for BSTs (pivot = root), parentheses (pivot = matching brace), full binary trees (pivot = root), and non-crossing chords (pivot = the chord from vertex 1).

This is also your first interval-DP-adjacent problem. The recurrence "split a range into two halves, recurse on each" generalizes to #241 Different Ways to Add Parentheses (pivot = operator), #95 Unique BSTs II (this problem plus tree reconstruction), and the interval-DP workhorses in Stage 3's final track.