Unique Binary Search Trees II — LC 95 Catalan Tree Generation

Problem Statement#

Given an integer n, return all structurally unique BSTs (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Constraints:

• 1 <= n <= 8

Input:  n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Input:  n = 1
Output: [[1]]

Why This Problem Matters#

LeetCode 95 Unique Binary Search Trees II is a Medium-difficulty problem asked at Google, Amazon, Meta, and Microsoft. It is one of the cleanest combinatorial recursion exercises — the answer count is the n-th Catalan number, growing as O(4^n / n^1.5), so candidates need to recognize that brute enumeration is fine for small n but the recursive structure must mirror BST partitioning.

Interviewers use this question to assess whether candidates can decompose a problem along a "choose the root, then recurse on left and right ranges" axis. The same pattern appears in matrix-chain multiplication, optimal BST construction, and the burst-balloons family of DP problems.

This question pairs well with LC 96 (just count, don't build). Strong candidates often discuss the count formula first as a sanity check.

The Core Insight#

A unique BST on [start, end] is fully described by its root value i. For each choice of i:

• The left subtree is any unique BST on [start, i - 1].
• The right subtree is any unique BST on [i + 1, end].

So gen(start, end) = \{ TreeNode(i, L, R) | i in [start, end], L in gen(start, i - 1), R in gen(i + 1, end) \}.

Base case: start > end yields [None] (one empty subtree). Without this sentinel, leaves would not pair properly.

The number of trees follows the Catalan recurrence C(n) = sum(C(i) * C(n - 1 - i)). Memoization avoids recomputing the same range, but for n <= 8 it is rarely necessary.

Visual Dry Run#

For n = 3, considering root = 2:

Total = 5 = C(3). Catalan number confirms correctness.

Solution (Optimal)#

class Solution:
    def generateTrees(self, n):
        if n == 0:
            return []
        def gen(start, end):
            if start > end:
                return [None]
            result = []
            for i in range(start, end + 1):
                left_trees = gen(start, i - 1)
                right_trees = gen(i + 1, end)
                for L in left_trees:
                    for R in right_trees:
                        node = TreeNode(i, L, R)
                        result.append(node)
            return result
        return gen(1, n)

var generateTrees = function(n) {
    if (n === 0) return [];
    const gen = (start, end) => {
        if (start > end) return [null];
        const result = [];
        for (let i = start; i <= end; i++) {
            const leftTrees = gen(start, i - 1);
            const rightTrees = gen(i + 1, end);
            for (const L of leftTrees) {
                for (const R of rightTrees) {
                    result.push(new TreeNode(i, L, R));
                }
            }
        }
        return result;
    };
    return gen(1, n);
};

Time: O(n * C(n)) where C(n) is the n-th Catalan number — total trees produced. Space: O(n * C(n)) for the output list, plus O(n) recursion depth.

Common Mistakes#

• Returning [] instead of [None] for empty ranges — single-child BSTs go missing.
• Sharing the same TreeNode across multiple parents — mutating one breaks others.
• Generating subtrees by value lists rather than ranges — duplicates work and is harder to memoize.
• Off-by-one on range endpoints — [start, end] vs [start, end) mistakes.
• Forgetting n = 0 returns an empty list (not [None]).

Interview Tips#

• Open with the count: "There are C(n) such trees — Catalan number."
• Sketch the recursive case on the whiteboard with i = root.
• Confirm whether nodes can be shared (usually NO — fresh nodes per tree).
• Mention memoization possibility for large n if the interviewer relaxes constraints.
• Trade off: brute generates and stores all; if only count is needed, LC 96 DP is O(n^2).

Follow-up Questions#

• Just count (LC 96)? DP: C(n) = sum_{i=0..n-1} C(i) * C(n - 1 - i). O(n^2) time.
• Memoize the recursion? Cache gen(start, end) keyed by (start, end) — saves redundant subtree generation.
• Lazy iterator instead of list? Yield trees one at a time to avoid O(C(n)) memory upfront.
• Generalize to a sorted array of distinct values? Same recursion, indices instead of values.
• Random unique BST? Sample uniformly using Catalan-weighted random choice.

Key Takeaways#

• LeetCode 95 is a Medium-difficulty FAANG recursion question asked at Google, Amazon, and Meta.
• The optimal pattern is "choose root, recurse on [start, root-1] and [root+1, end]".
• Empty ranges must return [None], not [], so single-child constructions work.
• The number of unique BSTs on n nodes is the n-th Catalan number C(n).
• Time complexity is O(n * C(n)) bounded by output size; space matches.
• Memoization helps for large n but is unnecessary at n <= 8 per problem constraints.
• The pattern transfers to optimal BST DP, matrix chain multiplication, and burst-balloons style problems.