Unique Binary Search Trees

The problem. Given n, return how many structurally different binary search trees hold exactly the values 1 to n.

Example

n = 1  ->  1
n = 3  ->  5
n = 4  ->  14
n = 19 ->  1767263190

The idea

Choose the root value r. Then 1..r−1 must form the left subtree and r+1..n the right one, and any left shape combines with any right shape. The number of shapes depends only on how many values a side has, not which ones. So with G(k) = the number of BSTs on k values:

G(0) = 1                      (the empty tree is one shape)
G(n) = sum over r = 1..n of  G(r - 1) * G(n - r)

These are the Catalan numbers: 1, 1, 2, 5, 14, 42, 132, …

1. Plain recursion

1function numTrees(n) {2  if (n <= 1) return 1;3  let total = 0;4  for (let r = 1; r <= n; r++) total += numTrees(r - 1) * numTrees(n - r);   // left shapes x right shapes5  return total;6}

Time O(3ⁿ) — the same G(k) is recomputed over and over — space O(n).

2. Bottom-up table

1function numTrees(n) {2  const G = new Array(n + 1).fill(0);3  G[0] = 1;4  G[1] = 1;5  for (let k = 2; k <= n; k++) {           // k values6    for (let r = 1; r <= k; r++) G[k] += G[r - 1] * G[k - r];7  }8  return G[n];9}

Time O(n²), space O(n).

3. The Catalan formula

G(n) = C(2n, n) / (n + 1), and successive Catalan numbers satisfy G(i+1) = G(i) · 2(2i + 1) / (i + 2). Multiply before dividing — the division is always exact.

1function numTrees(n) {2  let g = 1;                               // G(0)3  for (let i = 0; i < n; i++) g = (g * 2 * (2 * i + 1)) / (i + 2);4  return Math.round(g);5}

Time O(n), space O(1). Use 64-bit numbers: the product before dividing outgrows 32 bits long before the answer does.

Comparing the approaches

Edge cases to test

Variations