Unique Binary Search Trees

return the number of structurally unique BSTs. BST tree have left element smaller and right element bigger.

Unique Binary Search Trees

Problem

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

Examples

Example 1

Input: n = 3
Output: 5

• The five trees have these roots: 1, 2 or 3.
• Root 1 has 2 trees, root 2 has 1 tree, and root 3 has 2 trees.

Example 2

Input: n = 1
Output: 1

• There is only one tree: a single node.

Constraints

• 1 <= n <= 19

Main Idea

In a BST, every value in the left subtree is smaller than the root, and every value in the right subtree is bigger.

Let f(n) be the number of unique BSTs with n nodes. We pick each value i from 1 to n as the root:

• The left subtree uses the i - 1 smaller values. It has f(i - 1) possible shapes.
• The right subtree uses the n - i bigger values. It has f(n - i) possible shapes.
• Any left shape can join any right shape, so we multiply: f(i - 1) * f(n - i).

We add the results for all roots:

f(n) = sum of f(i - 1) * f(n - i), for i = 1 to n

Note: Only the count of nodes matters, not the actual values. A subtree of values 4, 5, 6 has the same number of shapes as 1, 2, 3.

Base Cases

• f(0) = 1. An empty tree is one valid shape. We need this, so a root with no left or right child still multiplies correctly.
• f(1) = 1. A single node is one tree.

Solution 1: Plain Recursion

var numTrees = function (n) {
    // empty tree or one node: only one shape
    if (n <= 1) return 1;

    let total = 0;

    // try every value i as the root
    for (let i = 1; i <= n; i++) {
        total += numTrees(i - 1) * numTrees(n - i);
    }

    return total;
};

Complexity

• Time Complexity: O(3^n) roughly, which is exponential
  • The same numTrees(k) is solved again and again.
• Space Complexity: O(n)
  • There is no table. The recursion stack goes as deep as n.

Solution 2: Memoization (Top-Down)

There are only n + 1 different inputs. We save each answer in a dp array.

var numTrees = function (n) {
    // -1 means "not solved yet"
    const dp = Array(n + 1).fill(-1);

    function solve(k) {
        // empty tree or one node: only one shape
        if (k <= 1) return 1;

        // answer is already saved
        if (dp[k] !== -1) return dp[k];

        let total = 0;

        for (let i = 1; i <= k; i++) {
            total += solve(i - 1) * solve(k - i);
        }

        return (dp[k] = total);
    }

    return solve(n);
};

Complexity

• Time Complexity: O(n²)
  • There are n states, and each runs a loop of up to n steps.
• Space Complexity: O(n)
  • The dp array and the recursion stack each use O(n).

Solution 3: Tabulation (Bottom-Up)

Here, dp[k] is the number of unique BSTs with k nodes. We fill it from small k to big k.

var numTrees = function (n) {
    const dp = Array(n + 1).fill(0);

    // base cases
    dp[0] = 1;
    dp[1] = 1;

    for (let k = 2; k <= n; k++) {
        // try every value i as the root
        for (let i = 1; i <= k; i++) {
            dp[k] += dp[i - 1] * dp[k - i];
        }
    }

    return dp[n];
};

How the Code Works

• Step 1: dp[0] = 1 and dp[1] = 1 are the base cases.
• Step 2: For each size k from 2 to n, we try every root i.
• Step 3: The left subtree has i - 1 nodes, and the right subtree has k - i nodes. Both sizes are smaller than k, so their values are already filled.
• Step 4: We multiply the left and right counts, and add the result to dp[k].
• Step 5: dp[n] is the answer.

Dry Run

Let us take n = 3.

For k = 2:

So dp[2] = 2.

For k = 3:

So dp[3] = 2 + 1 + 2 = 5. This matches the expected output.

Complexity

• Time Complexity: O(n²)
  • Two loops, one inside the other.
• Space Complexity: O(n)
  • The dp array holds n + 1 values.
  • There is no recursion stack.

Solution 4: Catalan Number Formula (Optional)

The values of f(n) are the Catalan numbers: 1, 1, 2, 5, 14, 42, .... They follow a simple rule:

C(0) = 1
C(k + 1) = C(k) * 2 * (2k + 1) / (k + 2)

var numTrees = function (n) {
    let c = 1;

    for (let k = 0; k < n; k++) {
        c = (c * 2 * (2 * k + 1)) / (k + 2);
    }

    return c;
};

• It uses one loop and a few variables.
• The division is always exact at each step, so c stays a whole number. For n <= 19, the values are small enough to be safe in JavaScript.

Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

Comparison

Summary

• Pick each value i as the root. The smaller values go left, and the bigger values go right.
• The number of shapes for each side depends only on its size.
• Multiply left and right counts, and add over all roots: f(n) = sum of f(i - 1) * f(n - i).
• f(0) = 1 handles roots that have an empty side.
• Memoization and tabulation run in O(n²) time and use O(n) space.
• The answers are Catalan numbers, so a formula gives O(n) time and O(1) space.