Unique Binary Search Trees II
Last Updated: April 4, 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 naturally leads to a recursive decomposition. For each possible root value k, we recursively generate all possible left subtrees from the smaller values and all possible right subtrees from the larger values. Then we combine every left subtree with every right subtree to form complete trees rooted at k.
Key Constraints:
1 <= n <= 8--> With n at most 8, the total number of unique BSTs is the Catalan number C(8) = 1430. This is small enough for any approach, including brute force enumeration of all trees.- The output is a list of tree roots, so we need to actually construct the trees, not just count them.
Approach 1: Recursive Generation (Divide and Conquer)
Intuition
The most natural way to think about this problem is to use 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 must form the left subtree, and values k+1 through end must form the right subtree.
We can try every value in the range as the root. For each choice, we recursively generate all possible left subtrees and all possible right subtrees. Then, for each combination of a left subtree and a right subtree, we create a new tree with k as the root.
The key insight is the base case: when the range is empty (start > end), we should return a list containing a single null element. A null subtree is a valid subtree. If we returned an empty list instead, the parent's loop over left-right combinations would produce zero trees, even when only one side is empty.
Algorithm
- Define a helper function
generateTrees(start, end)that returns all BSTs using values in [start, end]. - If start > end, return a list containing just null (empty subtree).
- 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.
- Return the result list.
Example Walkthrough
Code
- Time Complexity: O(n * C(n)), where C(n) is the nth Catalan number. We generate C(n) trees, each with n nodes. The recursive decomposition visits overlapping subproblems, so the same (start, end) range gets computed multiple times.
- Space Complexity: O(n * C(n)). We store all C(n) trees, each with n nodes. The recursion stack adds O(n) depth, but the dominant cost is the output itself.
The recursive approach recomputes the same subproblems multiple times. What if we remembered the results for each (start, end) range so we only compute them 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
- Create a hash map
memokeyed by (start, end) pairs. - Define
generate(start, end)as before, but checkmemofirst. - If
(start, end)is already in memo, return the cached list. - Otherwise, compute the list of trees as in Approach 1, store it in memo, and return it.
Example Walkthrough
Code
- Time Complexity: O(n * C(n)), where C(n) is the nth Catalan number. Each unique (start, end) pair is computed once. Memoization avoids redundant subproblem computation, but we still need to construct all output trees.
- Space Complexity: O(n * C(n)). The memo stores all subtrees for all (start, end) pairs. The dominant cost remains the output: C(n) trees, each with n nodes.
The memoized approach avoids redundant computation. We can also build subtrees bottom-up, starting from small ranges and combining them for larger ones.
Approach 3: Bottom-Up Dynamic Programming
Intuition
Instead of thinking top-down with recursion, we can flip the approach. Start by computing all BSTs for ranges of length 0 (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, we try each value in the range as the root. The left subtree comes from a shorter range we have already computed, and same for the right subtree. We combine them exactly as before.
This is a tabulation approach to the same recurrence. It eliminates recursion stack overhead and makes the build order explicit.
Algorithm
- Create a 2D table
dp[start][end]where each cell holds the list of all BSTs for that range. - Initialize all ranges where start > end with
[null]. - Iterate by range length from 1 to n.
- For each starting position, compute the ending position.
- For each possible root in the range, look up left and right subtree lists from the dp table.
- Combine all left-right pairs into trees rooted at the chosen value.
Example Walkthrough
Code
- Time Complexity: O(n * C(n)), where C(n) is the nth Catalan number. Same as the memoized approach. We compute each (start, end) pair exactly once, and for each pair we generate all possible trees.
- Space Complexity: O(n C(n)). The dp table stores the same trees as the memoized approach. The 2D array has O(n^2) cells, but the total number of TreeNode pointers across all cells sums to n C(n).