Unique Binary Search Trees II

Problem

Given n, return all structurally unique BSTs with exactly n nodes with values 1 to n.

Key insight: For each root value i, left subtree uses 1..i-1 and right subtree uses i+1..n. Recurse and combine.

Approach — Recursive + Memoization

generate(start, end) → all trees using values [start..end]
for each root r in [start..end]:
    for each left tree L from generate(start, r-1):
        for each right tree R from generate(r+1, end):
            combine

Solutions

// C++
map<pair<int,int>, vector<TreeNode*>> memo;
vector<TreeNode*> gen(int s, int e) {
    if (s > e) return {nullptr};
    if (memo.count({s,e})) return memo[{s,e}];
    vector<TreeNode*> res;
    for (int r = s; r <= e; r++) {
        for (auto l : gen(s, r-1))
            for (auto ri : gen(r+1, e)) {
                auto root = new TreeNode(r);
                root->left = l; root->right = ri;
                res.push_back(root);
            }
    }
    return memo[{s,e}] = res;
}
vector<TreeNode*> generateTrees(int n) { return gen(1, n); }

// Java
public List<TreeNode> generateTrees(int n) {
    return gen(1, n);
}
List<TreeNode> gen(int s, int e) {
    List<TreeNode> res = new ArrayList<>();
    if (s > e) { res.add(null); return res; }
    for (int r = s; r <= e; r++) {
        for (TreeNode l : gen(s, r-1))
            for (TreeNode ri : gen(r+1, e)) {
                TreeNode root = new TreeNode(r);
                root.left = l; root.right = ri;
                res.add(root);
            }
    }
    return res;
}

// JavaScript
function generateTrees(n) {
    function gen(s, e) {
        if (s > e) return [null];
        const res = [];
        for (let r = s; r <= e; r++) {
            for (const l of gen(s, r - 1))
                for (const ri of gen(r + 1, e)) {
                    const root = new TreeNode(r);
                    root.left = l; root.right = ri;
                    res.push(root);
                }
        }
        return res;
    }
    return gen(1, n);
}

# Python
def generateTrees(n):
    def gen(s, e):
        if s > e:
            return [None]
        res = []
        for r in range(s, e + 1):
            for left in gen(s, r - 1):
                for right in gen(r + 1, e):
                    root = TreeNode(r)
                    root.left = left
                    root.right = right
                    res.append(root)
        return res
    return gen(1, n)

Complexity

Time: O(Catalan(n) * n)
Space: O(Catalan(n) * n)

Key Insight

Catalan number C(n) counts the number of unique BSTs — around 4^n / (n^1.5 * sqrt(pi)).