Unique Binary Search Trees II

MediumTree DP · Divide & Conquer on Ranges🧩 Tree & Graph DP LeetCode #95 ↗Updated Oct 30, 2026

Problem

Given n, return every structurally different binary search tree whose nodes hold exactly the values 1..n, in any order.

Inputn = 1Output[[1]]

Inputn = 3Output5 trees, e.g. [2,1,3]

1 ≤ n ≤ 8 · answer size = Catalan number C_n (C₈ = 1430)

Try it yourself

Java

class Solution {
    public List<TreeNode> generateTrees(int n) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Fix the root value i: the BST property forces the left subtree to use exactly [lo, i-1] and the right [i+1, hi]; pair every left option with every right option.

PatternTree & Graph DP

Instinct A node's best answer depends only on its children's answers - post-order DFS that returns a tiny tuple of states per node.

Memory hack Kids report up, parent decides - every subtree hands its parent a small report card, and the parent never re-reads the kids' homework.

Open the Tree & Graph DP guide →

Approaches

Brute ForceAll Insertion Orders + Dedupe

Time O(n!·n²)Space O(n·C_n)

Every BST on 1..n is produced by inserting some permutation of the values. Insert all n! permutations and keep one tree per distinct pre-order signature; many orders give the same shape.

Java

public List<TreeNode> generateTrees(int n) {
    Map<String, TreeNode> unique = new LinkedHashMap<>();
    permute(new int[n], new boolean[n + 1], 0, unique);
    return new ArrayList<>(unique.values());
}
private void permute(int[] order, boolean[] used, int pos, Map<String, TreeNode> unique) {
    if (pos == order.length) {
        TreeNode root = null;
        for (int v : order) root = insert(root, v);
        unique.putIfAbsent(key(root), root);
        return;
    }
    for (int v = 1; v < used.length; v++) {
        if (used[v]) continue;
        used[v] = true; order[pos] = v;
        permute(order, used, pos + 1, unique);
        used[v] = false;
    }
}
private TreeNode insert(TreeNode node, int v) {
    if (node == null) return new TreeNode(v);
    if (v < node.val) node.left = insert(node.left, v);
    else node.right = insert(node.right, v);
    return node;
}
private String key(TreeNode node) { // pre-order shape signature
    return node == null ? "#" : node.val + "," + key(node.left) + "," + key(node.right);
}

Obviously correct, but factorial work for a Catalan-sized answer.

BetterRecursion on Value Ranges

Time O(3ⁿ + C_n)Space O(C_n)

build(lo, hi): for each root i, get all left trees of [lo, i-1] and right trees of [i+1, hi], and join every pair under a new root (empty range → [null]). Subtrees are shared, so each tree costs O(1) nodes, but ranges are rebuilt: 3ⁿ calls (C_n ≈ 4ⁿ/n^1.5).

Java

public List<TreeNode> generateTrees(int n) {
    return build(1, n);
}
private List<TreeNode> build(int lo, int hi) {
    List<TreeNode> all = new ArrayList<>();
    if (lo > hi) all.add(null); // the empty tree
    for (int i = lo; i <= hi; i++) {
        List<TreeNode> lefts = build(lo, i - 1), rights = build(i + 1, hi);
        for (TreeNode l : lefts)
            for (TreeNode r : rights) all.add(new TreeNode(i, l, r));
    }
    return all;
}

Builds only valid shapes, yet re-solves each sub-range many times.

OptimalMemoized Ranges (Top-Down DP)

Time O(n³ + C_n)Space O(n² + C_n)

Only n²/2 ranges exist, so cache the list for each [lo, hi]. Each is solved once (O(n) roots); each output tree costs O(1) new nodes. The C_n output term is unavoidable.

Java

private List<TreeNode>[][] memo;

@SuppressWarnings("unchecked")
public List<TreeNode> generateTrees(int n) {
    memo = new List[n + 2][n + 2];
    return build(1, n);
}
private List<TreeNode> build(int lo, int hi) {
    if (memo[lo][hi] != null) return memo[lo][hi];
    List<TreeNode> all = new ArrayList<>();
    if (lo > hi) all.add(null);
    for (int i = lo; i <= hi; i++) {
        for (TreeNode l : build(lo, i - 1))
            for (TreeNode r : build(i + 1, hi)) all.add(new TreeNode(i, l, r));
    }
    return memo[lo][hi] = all;
}

Work matches the output size; trees share immutable subtrees.

At a glance

Level	Approach	Time	Space
Brute Force	All Insertion Orders + Dedupe	`O(n!·n²)`	`O(n·C_n)`
Better	Recursion on Value Ranges	`O(3ⁿ + C_n)`	`O(C_n)`
Optimal	Memoized Ranges (Top-Down DP)	`O(n³ + C_n)`	`O(n² + C_n)`

Common pitfalls

Empty range must give [null], not [], or no pairs form.
Reusing one root object across (left, right) pairs.
Mixing it up with Unique BSTs I, which only counts.

Interview tips

Argue the root split: BST order fixes each subtree's range.
Output size C_n is a hard lower bound on time.
Mention shared subtrees; deep-copy if callers mutate.

Pattern

Range DP / divide & conquer on roots → enumerate or count structures built from a split point (BSTs, parenthesisations).

My notes saved in this browser