Unique Binary Search Trees II

medium tree bst dp backtracking

Problem

Given an integer n, return every structurally unique BST that stores exactly the values 1, 2, …, n.

Inputn = 3

Output5 trees (Catalan number C₃)

For each root r in [1..n], recursively build all BSTs from [1..r-1] (left subtree) and [r+1..n] (right subtree); the cross product gives every tree rooted at r.

n (1–4)

def generate_trees(n):
    def build(lo, hi):
        if lo > hi: return [None]
        out = []
        for r in range(lo, hi + 1):
            for L in build(lo, r - 1):
                for R in build(r + 1, hi):
                    out.append(TreeNode(r, L, R))
        return out
    return build(1, n) if n else []

function generateTrees(n) {
  if (!n) return [];
  function build(lo, hi) {
    if (lo > hi) return [null];
    const out = [];
    for (let r = lo; r <= hi; r++) {
      for (const L of build(lo, r - 1)) {
        for (const R of build(r + 1, hi)) {
          out.push({ val: r, left: L, right: R });
        }
      }
    }
    return out;
  }
  return build(1, n);
}

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
        return build(1, n);
    }
    List<TreeNode> build(int lo, int hi) {
        List<TreeNode> out = new ArrayList<>();
        if (lo > hi) { out.add(null); return out; }
        for (int r = lo; r <= hi; r++)
            for (TreeNode L : build(lo, r - 1))
                for (TreeNode R : build(r + 1, hi))
                    out.add(new TreeNode(r, L, R));
        return out;
    }
}

vector<TreeNode*> build(int lo, int hi) {
    if (lo > hi) return { nullptr };
    vector<TreeNode*> out;
    for (int r = lo; r <= hi; r++)
        for (auto* L : build(lo, r - 1))
            for (auto* R : build(r + 1, hi))
                out.push_back(new TreeNode(r, L, R));
    return out;
}
vector<TreeNode*> generateTrees(int n) { return n ? build(1, n) : vector<TreeNode*>{}; }

Explanation

We need to actually build every distinct BST holding the values 1..n. The core idea is recursion: pick each value as the root, then build all possible left and right subtrees for it.

The helper build(lo, hi) returns a list of every BST shape that uses exactly the values lo..hi. If lo > hi the range is empty, so it returns [None] — the single "empty tree", which is important so a node can have a missing child.

For each chosen root r in lo..hi, the BST rule forces all smaller values lo..r-1 into the left subtree and all larger values r+1..hi into the right. We recursively get every left shape and every right shape, then take their cross product: pair each L with each R to make a new tree rooted at r.

Example: n = 3. Choosing root 2 gives exactly one left subtree (1) and one right subtree (3), producing one tree; roots 1 and 3 each produce two shapes. Altogether that is 5 trees — the Catalan number C₃.

So the answer is just build(1, n), the full list of every structurally unique BST.

Time: O(n · C_n) Space: O(n · C_n)