AlgoMaster Logo

Unique Binary Search Trees II

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We need to generate every possible BST that contains exactly the values 1 through n. "Structurally unique" means two trees are different if they have different shapes or different node placements, even if they contain the same values.

The BST property constrains where each value can go: for any node with value v, all values in its left subtree must be less than v, and all values in its right subtree must be greater than v. So if we pick value k as the root, values 1 through k-1 must form the left subtree, and values k+1 through n must form the right subtree.

This gives a recursive decomposition. For each possible root value k, generate all possible left subtrees from the smaller values and all possible right subtrees from the larger values, then combine every left subtree with every right subtree to form complete trees rooted at k.

Key Constraints:

  • 1 <= n <= 8. The number of unique BSTs is the Catalan number C(n), which reaches C(8) = 1430. We must construct every one of them, so the output alone dominates the cost and any correct enumeration runs in time.
  • The output is a list of tree roots, so we construct the trees, not just count them.

Approach 1: Recursive Generation (Divide and Conquer)

Intuition

Apply the BST property directly. If we choose value k as the root of a BST containing values from start to end, then values start through k-1 form the left subtree and values k+1 through end form the right subtree.

So we try every value in the range as the root. For each choice, recursively generate all possible left subtrees and all possible right subtrees, then for each combination of a left subtree and a right subtree, create a new tree with k as the root.

The base case decides whether the combination loop produces anything. When the range is empty (start > end), return a list containing a single null element rather than an empty list. A null subtree is a valid subtree. With an empty list, the parent's loop over left-right pairs would iterate zero times and produce no trees, even when only one side is empty. Returning [null] lets the parent pair that single null with each subtree from the non-empty side.

Algorithm

  1. Define a helper function generateTrees(start, end) that returns all BSTs using values in [start, end].
  2. If start > end, return a list containing just null (empty subtree).
  3. For each value k from start to end:
    • Recursively generate all left subtrees: generateTrees(start, k - 1).
    • Recursively generate all right subtrees: generateTrees(k + 1, end).
    • For each (leftTree, rightTree) pair, create a new node with value k, set its left to leftTree and right to rightTree, and add it to the result list.
  4. Return the result list.

Example Walkthrough

1Start: generate all BSTs for values [1,2,3]. Try root=1 first.
0
root=1
1
1
2
2
3
1/7

Code

The recursive approach recomputes the same (start, end) range multiple times. The next approach caches each range's result so it is computed once.

Approach 2: Recursive with Memoization

Intuition

In the pure recursive approach, many subproblems overlap. For instance, the range (2, 4) might appear as a right subtree when root = 1 in the range (1, 5), and also as a left subtree when root = 5 in the range (2, 5). Each time, we regenerate all BSTs for that range from scratch.

We can fix this by caching results in a hash map keyed by the (start, end) pair. Before doing any work, check if we have already computed all trees for this range. If so, return the cached result. If not, compute it, cache it, and return it.

One subtle point: when we reuse cached subtrees, multiple parent trees will share the same child subtree objects. This is fine for this problem because we never modify the trees after construction.

Algorithm

  1. Create a hash map memo keyed by (start, end) pairs.
  2. Define generate(start, end) as before, but check memo first.
  3. If (start, end) is already in memo, return the cached list.
  4. Otherwise, compute the list of trees as in Approach 1, store it in memo, and return it.

Example Walkthrough

1Start generate(1,3). Try root=1. Need generate(1,0) and generate(2,3).
0
root=1
1
1
2
2
3
right
1/5

Code

Memoization computes each range once but still drives the order through recursion. The next approach makes the build order explicit, computing every short range before the longer ranges that depend on it.

Approach 3: Bottom-Up Dynamic Programming

Intuition

The same recurrence runs bottom-up instead of top-down. Compute all BSTs for ranges of length 0 (the base case: just null), then length 1 (single nodes), then length 2, and so on up to length n.

For a range of length len starting at position start, try each value in the range as the root. Both the left subtree and the right subtree come from shorter ranges that are already in the table, so they are looked up rather than recomputed. Combining left-right pairs works as before.

This tabulation removes the recursion stack and fixes the order in which ranges are built. The trade-off against memoization is that it allocates the full 2D table up front rather than filling entries lazily.

Algorithm

  1. Create a 2D table dp[start][end] where each cell holds the list of all BSTs for that range.
  2. Initialize all ranges where start > end with [null].
  3. Iterate by range length from 1 to n.
  4. For each starting position, compute the ending position.
  5. For each possible root in the range, look up left and right subtree lists from the dp table.
  6. Combine all left-right pairs into trees rooted at the chosen value.

Example Walkthrough

1Bottom-up: first compute all length-1 ranges: dp[1][1], dp[2][2], dp[3][3].
0
1
dp[1][1]
1
2
dp[2][2]
2
3
dp[3][3]
1/4

Code