Unique Binary Search Trees

medium tree bst dp math

Problem

Given an integer n, return the number of structurally unique BSTs (binary search trees) that can store exactly n nodes with values 1..n.

Inputn = 3

Output5

G(n) = sum over root i of G(i-1) * G(n-i) — the Catalan recurrence.

def num_trees(n):
    g = [0] * (n + 1)
    g[0] = 1
    for i in range(1, n + 1):
        for j in range(1, i + 1):
            g[i] += g[j - 1] * g[i - j]
    return g[n]

function numTrees(n) {
  const g = new Array(n + 1).fill(0);
  g[0] = 1;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= i; j++) {
      g[i] += g[j - 1] * g[i - j];
    }
  }
  return g[n];
}

class Solution {
    public int numTrees(int n) {
        int[] g = new int[n + 1];
        g[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                g[i] += g[j - 1] * g[i - j];
            }
        }
        return g[n];
    }
}

int numTrees(int n) {
    vector<long> g(n + 1, 0);
    g[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            g[i] += g[j - 1] * g[i - j];
        }
    }
    return (int)g[n];
}

Explanation

Here we only need to count the unique BSTs, not build them. We use an array g where g[i] is the number of distinct BSTs you can make from i nodes. Remarkably, the labels don't matter for counting — only how many nodes are on each side.

The base case is g[0] = 1: an empty tree is one valid shape.

To fill g[i], we try each node as the root. If the root is the j-th smallest value, then j-1 nodes go left and i-j go right. The number of trees for that root is g[j-1] · g[i-j], and we sum this over all roots: g[i] += g[j-1] * g[i-j].

This is the famous Catalan recurrence. Each smaller g value is already computed before we need it, so the table fills cleanly.

Example: n = 3. Root 1 gives g[0]·g[2] = 2, root 2 gives g[1]·g[1] = 1, root 3 gives g[2]·g[0] = 2. Total g[3] = 5.

Time: O(n²) Space: O(n)