Unique Binary Search Trees — LeetCode 96 Catalan Numbers Decoded

Problem Statement#

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

Constraints:

• 1 <= n <= 19

Input:  n = 3
Output: 5

Input:  n = 1
Output: 1

Why This Problem Matters#

LeetCode 96 — Unique Binary Search Trees — is one of the cleanest demonstrations of Catalan numbers in interviews and shows up regularly at Amazon, Google, Bloomberg, and Microsoft. The constraint n <= 19 hints at exact integer counting, and the problem appears innocuous until you realize the answer grows like 4^n / n^1.5.

Interviewers use this problem to test pattern recognition: candidates who already know Catalan numbers write the closed form in seconds, while everyone else must derive a recurrence. Either way, the underlying skill — recognizing that the root of a BST partitions remaining keys into two independent subproblems — is the same skill needed for LC 95 Unique BSTs II, LC 894 All Possible Full Binary Trees, and many divide-and-conquer questions.

This is a classic Bloomberg phone-screen warmup and a Google onsite first-question. Mastering it solidifies BST structural reasoning and DP on integer sequences.

The Core Insight#

Let G(n) be the number of structurally unique BSTs that store n nodes. Pick any value i (from 1 to n) as the root. Then:

• The left subtree must store values 1..i-1 — that's G(i-1) shapes.
• The right subtree must store values i+1..n — that's G(n-i) shapes (only the count matters; the values are interchangeable due to BST symmetry).

So G(n) = sum over i=1..n of G(i-1) * G(n-i). Base cases: G(0) = G(1) = 1. This recurrence is the definition of the Catalan numbers C_n. The closed form is C_n = C(2n, n) / (n+1).

Visual Dry Run#

For n = 3:

Total G(3) = 2 + 1 + 2 = 5. The 5 BSTs correspond to roots 1 (right-leaning chain or fork), 2 (balanced), and 3 (left-leaning shapes).

Solution (Optimal)#

class Solution:
    def numTrees(self, n: int) -> int:
        # G[i] = number of unique BSTs that store i nodes
        G = [0] * (n + 1)
        G[0] = 1
        G[1] = 1
        for nodes in range(2, n + 1):
            for root in range(1, nodes + 1):
                G[nodes] += G[root - 1] * G[nodes - root]
        return G[n]

var numTrees = function(n) {
    const G = new Array(n + 1).fill(0);
    G[0] = 1;
    G[1] = 1;
    for (let nodes = 2; nodes <= n; nodes++) {
        for (let root = 1; root <= nodes; root++) {
            G[nodes] += G[root - 1] * G[nodes - root];
        }
    }
    return G[n];
};

Time: O(n^2) — two nested loops up to n. Space: O(n) — DP array of length n+1.

For an O(n) solution, use the Catalan closed form C_{n+1} = C_n * 2(2n+1) / (n+2).

class Solution:
    def numTrees(self, n: int) -> int:
        c = 1
        for i in range(n):
            c = c * 2 * (2 * i + 1) // (i + 2)
        return c

Common Mistakes#

• Confusing "structurally unique" with "value-different" — values are fixed at 1..n, only shapes vary.
• Off-by-one on the recurrence: forgetting G(0) = 1 (the empty tree counts as one shape).
• Recursion without memoization yields exponential time and TLEs on n = 19.
• Integer overflow in 32-bit languages: C_19 = 1767263190 fits in 32-bit, but intermediate products can overflow if you re-derive larger values.
• Treating left and right subtrees as the same problem with relabeling — the count function only depends on size, not on the specific keys.

Interview Tips#

• Say the magic phrase: "This is the n-th Catalan number." Most interviewers immediately accept the recurrence.
• Draw the 5 BSTs for n=3 to anchor the explanation.
• Mention that LC 95 Unique BSTs II asks you to enumerate the trees, not just count, and it uses the same recursive structure.
• If asked for the closed form, derive it briefly: C_n = (2n)! / ((n+1)! n!).

Follow-up Questions#

• "Generate all the trees" — LC 95: recursion that builds left and right subtree lists and combines.
• "What if values are 1..n but skewed?" — Same count; values do not affect structure.
• "Count unique BSTs whose height is at most h" — Add a height dimension to the DP, O(n^2 * h).
• "Number of full binary trees with n nodes" — LC 894, similar Catalan-style recurrence with odd n only.
• "Probability a random BST is balanced" — Ratio of balanced count to C_n.

Key Takeaways#

• LeetCode 96 Unique Binary Search Trees counts n-node BST shapes — the answer is the n-th Catalan number.
• The recurrence G(n) = sum of G(i-1) * G(n-i) runs in O(n^2) time and O(n) space.
• The closed-form C_n = C(2n, n) / (n+1) gives an O(n) solution.
• G(0) = 1 is the convention that makes the recurrence work — the empty tree counts as one shape.
• Catalan numbers also count balanced parens, mountain ranges, triangulations, and full binary trees.
• This is a recurring Amazon, Google, and Bloomberg interview question for early-onsite slots.
• The same divide-by-root insight powers LC 95 Unique BSTs II, which builds the trees explicitly.