Unique Binary Search Trees II: Generate All Valid BSTs

Given an integer n, return all structurally unique BSTs (binary search trees) that have exactly n nodes, where each node contains a unique value from 1 to n. This is LeetCode 95: Unique Binary Search Trees II.

For n = 3, there are exactly 5 unique BSTs:

The challenge is not just counting how many exist. You need to construct and return every single one of them. That means your solution has to build actual tree nodes, not just compute a number.

The key insight: choosing a root splits the problem

Pick any value i from 1 to n as the root. Because this is a BST, every value less than i must go in the left subtree, and every value greater than i must go in the right subtree. That gives you two smaller subproblems:

• Left subtree: all structurally unique BSTs from values [1, i-1]
• Right subtree: all structurally unique BSTs from values [i+1, n]

For each root choice, you recursively generate every possible left subtree and every possible right subtree. Then you combine every left-right pair by creating a new root node pointing to one left subtree and one right subtree. This is a Cartesian product: if there are L left subtrees and R right subtrees, you get L * R unique trees for that root.

Repeat this for every root choice from 1 to n, and collect all the results.

The recursive generation, step by step

Let's trace through n = 3 and see how each root choice produces a set of trees.

Python solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def generate_trees(n):
    if n == 0:
        return []

    def build(lo, hi):
        if lo > hi:
            return [None]
        all_trees = []
        for root_val in range(lo, hi + 1):
            left_trees = build(lo, root_val - 1)
            right_trees = build(root_val + 1, hi)
            for left in left_trees:
                for right in right_trees:
                    root = TreeNode(root_val, left, right)
                    all_trees.append(root)
        return all_trees

    return build(1, n)

Walkthrough

The outer function generate_trees handles the edge case of n = 0 and then calls the inner build function with the full range [1, n].

Inside build(lo, hi):

1. Base case: if lo > hi, the range is empty. Return [None], a list containing a single null node. This represents "no subtree here." Returning a list with one element (instead of an empty list) is critical. If you returned an empty list, the Cartesian product loop would produce zero combinations, and you would lose valid trees.

2. Recursive case: for each value root_val from lo to hi, you recursively generate all left subtrees from build(lo, root_val - 1) and all right subtrees from build(root_val + 1, hi).

3. Combination: the nested loop over left_trees and right_trees produces every possible pair. For each pair, you create a fresh TreeNode with root_val as the value and attach the left and right subtrees.

4. Collect: all trees for all root choices go into all_trees, which gets returned to the caller.

The recursion naturally handles the splitting. When root_val is 1, the left range is [1, 0] (empty, producing [None]), and the right range is [2, n]. When root_val is n, the right range is [n+1, n] (empty), and the left range is [1, n-1].

Complexity analysis

Here, C(n) is the nth Catalan number, which counts the number of structurally unique BSTs with n nodes. The Catalan numbers grow as C(n) = (2n)! / ((n+1)! * n!), which is roughly 4^n / (n^(3/2) * sqrt(pi)).

Time: for each of the C(n) trees, you do O(n) work to build the n nodes. The total is O(n * C(n)).

Space: you store all C(n) trees, each with n nodes, so the output itself takes O(n * C(n)) space. The recursion stack adds O(n) on top of that, but it is dominated by the output size.

For small n, the numbers are manageable: C(3) = 5, C(4) = 14, C(5) = 42. But they grow fast: C(8) = 1430, so the constraint n is at most 8 on LeetCode keeps things feasible.

Edge cases

• n = 1: there is exactly one BST, a single node with value 1. The recursion calls build(1, 1), which tries root_val = 1, gets [None] for both left and right, and returns one tree.
• n = 0: the problem typically states 1 is less than or equal to n is less than or equal to 8, but the solution handles it by returning an empty list.
• Skewed trees: when the root is 1 (all nodes in the right subtree) or n (all nodes in the left subtree), the recursion naturally produces the maximally skewed chains.

The building blocks

This problem is built on two fundamental building blocks.

Recursive tree generation. The idea of choosing a root, recursively solving for the left and right subtrees, and combining the results. This pattern appears whenever you need to enumerate or count tree structures. The recursive call with a shrinking range (lo to hi) is the same skeleton used in problems like constructing BSTs from sorted arrays or building trees from preorder/inorder traversals.

Cartesian product of subtrees. Once you have a list of possible left subtrees and a list of possible right subtrees, you need every combination. The nested for-loop that pairs each left with each right is a direct application of the Cartesian product. This shows up in any problem where you combine independent choices from two or more sets.

# Recursive tree generation skeleton:
def build(lo, hi):
    if lo > hi:
        return [None]
    results = []
    for root_val in range(lo, hi + 1):
        for left in build(lo, root_val - 1):
            for right in build(root_val + 1, hi):
                results.append(TreeNode(root_val, left, right))
    return results

# Cartesian product pattern:
for left in left_options:
    for right in right_options:
        combine(left, right)

From understanding to recall

You now understand how choosing each root value from 1 to n splits the problem into two independent subproblems, and how the Cartesian product of left and right subtrees produces every valid combination. The base case returning [None] instead of [] makes the combinatorics work.

But understanding this once is not the same as being able to write it from scratch under pressure. In a week, will you remember that the base case returns a list containing None? Will you remember the nested loop structure that pairs every left subtree with every right subtree? Or will you stall on the base case and wonder why your solution produces an empty list?

Spaced repetition turns this understanding into reflex. You practice writing the build function from scratch at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the range parameters, the base case, the root loop, the recursive calls, and the Cartesian product. After a few reps, you reach for this pattern automatically whenever a problem asks you to enumerate tree structures.

Related posts

• Validate Binary Search Tree - Uses BST properties to validate structure, the verification side of what this problem generates