Unique Binary Search Trees II

The counting recurrence is only half the problem. To generate every tree, you must materialize every left/right subtree combination.

The contract and the recursive direction

Given n, return roots for every structurally unique BST using the values 1 through n exactly once. The output order does not matter, and the constraint is 1 <= n <= 8.

The useful state is an inclusive value range:

build(lo, hi) = every BST whose values are exactly lo, lo + 1, ..., hi

For each possible root r:

• Values lo through r - 1 must form the left subtree.
• Values r + 1 through hi must form the right subtree.
• Every valid left tree can pair with every valid right tree.

That last point is the distinction between the generation problem and the neighboring count-only problem. Counting uses multiplication:

number of trees with root r
= left_count * right_count

Generation must perform the corresponding Cartesian product:

for every left tree:
    for every right tree:
        create a tree rooted at r

The recursion is therefore:

build(lo, hi):
    if lo > hi:
        return [None]

    result = []

    for r in [lo, hi]:
        left_trees = build(lo, r - 1)
        right_trees = build(r + 1, hi)

        for left in left_trees:
            for right in right_trees:
                result.append(Node(r, left, right))

    return result

The empty interval is deliberately represented by a one-element collection containing None. That detail is what allows a root at either boundary to have a missing child without deleting the entire combination.

Recognize interval tree-family DP

This problem exposes three signals that point toward interval-based two-dimensional dynamic programming:

1. The values are ordered.
2. Choosing a root divides the remaining values into two independent contiguous ranges.
3. The requirement is to generate every valid construction, not select one.

The two coordinates are lo and hi. Conceptually, the state is not a number in a matrix. It is a family of trees associated with an interval:

F(lo, hi) = all unique BSTs containing exactly [lo, hi]

That distinction matters. In many two-dimensional DP problems, a state stores a scalar such as a minimum cost or number of ways. Here, a state stores a collection of tree roots. The state payload is larger because the output itself is combinatorial.

A naive recursive implementation repeatedly rebuilds the same interval families. For example, several different parent choices may ask for the trees in [3, 4]. Memoization can cache that family once and reuse it.

But memoization does not make the whole task polynomial. It removes repeated work between overlapping interval states; it cannot avoid returning every requested tree.

Recognition rule: when an ordered range chooses a pivot and the pivot creates two independent subranges, define the state over the interval and combine the two returned families.

This is the tree-specific form of BST construction DP. It is not generic enumeration over arbitrary subsets. The BST ordering is doing the heavy work: once the root is chosen, the remaining values are forced into two intervals.

Derive the range recurrence

Define F(lo, hi) as the list of all structurally unique BST roots using every value in the inclusive interval [lo, hi].

Empty interval

If lo > hi, there are no values available for a subtree. There is exactly one way to represent that situation: an empty subtree.

So:

F(lo, hi) = [None] when lo > hi

Returning [None] means “there is one valid empty-subtree choice.”

Returning [] means “there are no valid choices,” which is different. If the left interval is empty and you return [], the nested loop over left trees executes zero times and discards valid trees.

Non-empty interval

For each r in [lo, hi]:

left_family  = F(lo, r - 1)
right_family = F(r + 1, hi)

Then construct one root for every pair:

for left in left_family:
    for right in right_family:
        add Node(r, left, right)

The count recurrence hidden inside this construction is:

|F(lo, hi)|
= sum over r of |F(lo, r - 1)| * |F(r + 1, hi)|

The sum comes from different root values. The product comes from independent left and right choices for one root.

The n = 3 decomposition

For values [1, 3], consider each root.

Root 1

left:  F(1, 0) = [None]
right: F(2, 3)

The root has no left child. Every tree generated from F(2, 3) becomes a valid right-heavy tree.

Root 2

left:  F(1, 1)
right: F(3, 3)

Each side has exactly one tree, so this produces the tree with 2 at the root and one child on each side.

Root 3

left:  F(1, 2)
right: F(4, 3) = [None]

This mirrors the root-1 case.

The three root choices produce five total trees. The important part is not memorizing the number five. It is seeing where the five come from: each root contributes the product of its left and right family sizes.

Prove the construction is exact

Use this invariant for every interval:

F(lo, hi) contains every valid BST using exactly the values in [lo, hi], contains no invalid tree, and contains no duplicate structure.

The proof has three parts.

Soundness

Take any tree constructed by the recurrence.

Its root is some r in [lo, hi]. The left subtree came from F(lo, r - 1), so it contains exactly the values smaller than r. The right subtree came from F(r + 1, hi), so it contains exactly the values larger than r.

By induction, both subtrees are valid BSTs. Attaching them to r preserves the BST ordering and uses every interval value exactly once.

Therefore every returned tree is valid.

Completeness

Take any valid BST using exactly [lo, hi].

Its root must contain some value r in that interval. Because it is a BST:

• Every value smaller than r must be in the left subtree.
• Every value larger than r must be in the right subtree.

So its subtrees must use exactly [lo, r - 1] and [r + 1, hi]. By the induction hypothesis, the recursive calls generate those subtree structures. The nested loops eventually select the exact left/right pair from the original tree and reconstruct it.

Therefore every valid tree appears.

Structural uniqueness

Two constructions with different root values cannot produce the same tree: their root values differ.

If the root value is the same, then two different left structures or two different right structures produce different trees below that root. The Cartesian product creates one result for each distinct pair.

Therefore no structural duplicate is generated.

Output order has no role in this proof. The judge may accept any ordering because correctness depends on the family of trees, not on list position.

Implement the generator in Python

The following version memoizes interval families. It assumes the judge provides the usual TreeNode class.

from functools import cache
from typing import Optional


class Solution:
    def generateTrees(self, n: int) -> list[Optional["TreeNode"]]:
        # The supplied contract has n >= 1.
        # This guard supports platform variants that allow n == 0.
        if n == 0:
            return []

        @cache
        def build(lo: int, hi: int) -> tuple[Optional["TreeNode"], ...]:
            # One empty choice keeps leaf-side combinations alive.
            if lo > hi:
                return (None,)

            trees = []

            for root_value in range(lo, hi + 1):
                left_trees = build(lo, root_value - 1)
                right_trees = build(root_value + 1, hi)

                # Materialize the Cartesian product of both families.
                for left in left_trees:
                    for right in right_trees:
                        root = TreeNode(root_value)
                        root.left = left
                        root.right = right
                        trees.append(root)

            return tuple(trees)

        return list(build(1, n))

The return type inside build is a tuple so that the cached result is immutable as a collection. The tree nodes themselves are still mutable objects supplied by the judge.

The important implementation decisions are these:

• lo and hi identify the exact value obligation for the state.
• build(lo, root_value - 1) constructs the only values allowed on the left.
• build(root_value + 1, hi) constructs the only values allowed on the right.
• [None] is represented as (None,), preserving one empty-subtree choice.
• A new TreeNode is created for every left/right pair.

Creating the root inside the innermost loop is essential. Reusing one root and changing its children would overwrite trees already stored in trees.

Memoization causes interval families to be reused. That is safe for the standard problem because the returned trees are treated as output values. If a caller later mutates one returned tree, shared subtree objects can make that mutation visible in another output tree. A consumer that requires every output to be independently mutable would need deep copies or a construction strategy that avoids sharing. The judge contract does not require that extra isolation.

Dry-run the output geometry

For n = 3, the top-level call is:

build(1, 3)

Root 2

The recursive calls are:

build(1, 1) -> [tree rooted at 1]
build(3, 3) -> [tree rooted at 3]

There is one left choice and one right choice, so their Cartesian product has one pair:

    2
   / \
  1   3

Root 1

The calls are:

build(1, 0) -> [None]
build(2, 3) -> two trees

The None choice means the root has no left child. The two right-subtree choices produce:

1
 \
  2
   \
    3

and

1
 \
  3
 /
2

Root 3

This is the mirror image:

3
/
2
/
1

and

  3
 /
1
 \
  2

Together with the root-2 tree, these are the five unique structures for n = 3.

The two most common implementation failures are visible here:

1. Returning [] for an empty interval removes every tree where a boundary root has a missing child.
2. Selecting only one left/right pair loses valid structures whenever either subtree family contains multiple trees.

A fast debugging loop is:

• Run n = 1; expect one single-node tree.
• Run n = 2; expect two skewed trees.
• Run n = 3; expect five structures.
• Serialize each tree and compare the set of serializations, not the list order.

The recurrence provides an independent debugging oracle. For every interval, verify:

tree_count(lo, hi)
= sum(left_count * right_count) over every root

If the count is wrong, inspect the interval boundaries before inspecting the tree-node code. Most failures occur at the state contract, not at the object constructor.

Complexity is governed by the output

Let C_n be the nth Catalan number. It counts the structurally unique BSTs that can be built from n ordered values, and it grows asymptotically like:

C_n = Θ(4^n / n^(3/2))

There are only O(n^2) possible inclusive intervals, so the number of DP states is small. That fact can be misleading. The requested output contains C_n trees, and each tree contains n nodes when viewed as a fully materialized result.

A practical output-sensitive bound is:

Time:  O(n * C_n)
Space: O(n * C_n) for explicit tree output

The time bound reflects the work required to construct the returned tree nodes across the output family. The storage bound reflects keeping the generated results.

Memoization reduces repeated construction of the same interval families. It does not remove the Catalan-scale cost of producing the top-level result. A cache can prevent us from rebuilding a component; it cannot make the component disappear from the answer.

There is one representation detail worth separating from the asymptotic contract. With memoization, different output roots may reference the same previously generated subtree objects. That can reduce the number of physically allocated node objects compared with storing every tree as a completely independent deep copy. The caller still receives C_n root references, and the conceptual output remains Catalan-sized. If independent mutation is required, deep-copying restores the full materialized-node cost.

This is also why the count-only problem has a different complexity profile. A count-only DP stores integers and can keep compact interval or size-based states. Unique Binary Search Trees II must return the structures themselves. Do not transfer the count-only complexity claim to a generation problem.

Edge cases and interview checks

Use the following checks before trusting the implementation:

• n = 1 returns exactly one root with no children.
• n = 2 returns the two possible skewed trees.
• Every empty internal interval returns exactly one None choice.
• Under the supplied contract, the top-level result is a list of actual roots because n >= 1.
• Every output contains each value from 1 through n exactly once.
• Every output satisfies the BST ordering at every node.
• Different outputs are structurally unique, regardless of list order.
• A fresh root is created for every left/right pair.
• No loop reuses a root and mutates it after storing it.
• The count for each interval matches the sum of left-count times right-count across candidate roots.

The defensive n == 0 branch is a platform-compatibility choice, not part of the supplied constraint. At the top level, some variants expect [] for zero nodes. Inside the recurrence, however, an empty interval must still return one empty choice. Those are different contracts at different levels:

top-level n == 0: []
internal empty interval: [None]

That distinction is easy to miss and central to correctness.

The transferable pattern

When an ordered range allows you to choose a pivot, ask what the pivot forces.

Here, choosing the root forces two contiguous value ranges. Define the answer as a family for each range. Represent a missing child with one empty-choice element. Then combine every left family member with every right family member.

The reusable mental model is:

ordered interval
→ choose pivot
→ split into independent intervals
→ generate both families
→ take their Cartesian product

The final interview check is equally important: separate the number of DP states from the size of the requested output. O(n^2) intervals do not make a Catalan-sized generation task polynomial. The state space may be compact; the answer may still be enormous.

Read the interval boundaries. Trace the empty choice. Count the Cartesian products. Then let the output—not a memorized recurrence—prove that the construction is complete.