Unique Binary Search Trees II
A medium BST interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- BST
- Sheets
- 1
- Core for
- 2 roles
The problem
Given an integer n, generate all structurally unique BSTs that store values 1 through n. Each tree must be a valid binary search tree. Return a list of the root nodes of all such trees.
Example 1
- Input
- n=3
- Output
- 5 trees
- Why
- There are 5 structurally unique BSTs: roots 1, 2, 3 with different left/right child arrangements.
Example 2
- Input
- n=1
- Output
- 1 tree
- Why
- Only one tree: a single node with value 1.
Example 3
- Input
- n=2
- Output
- 2 trees
- Why
- Two trees: root 1 with right child 2, and root 2 with left child 1.
Constraints
- 1 <= n <= 8
How to think about it
Updated 2026-09-29This is the generative counterpart of counting unique BSTs. For any range [start, end], pick each value i as root, recursively generate all valid BSTs on [start, i - 1] for left subtrees, recursively generate all valid BSTs on [i + 1, end] for right subtrees, and construct all cartesian pairs with i as their root.
Approaches, worst first
Recursive divide and conquer
time O(4^n / n^(1/2)) · space O(4^n / n^(1/2))
Define helper `generate(start, end)`. If `start > end`, return a list containing `null`. For each `i` from start to end, generate all left subtrees and right subtrees, then combine each pair under a new root with value `i` and append to the result list.
Memoized interval generationWrite this one
time O(4^n / n^(1/2)) · space O(4^n / n^(1/2))
Cache results of `generate(start, end)` in a map or 2D table keyed by interval bounds. Sub-ranges with identical lengths produce isomorphic structures, avoiding redundant tree construction calls.
Where people lose marks · 2
- Returning empty list instead of list containing null for the base case `start > end`. An empty list makes nested loops over left and right children execute zero times, producing zero trees.
- Reusing node instances across multiple trees: mutating child pointers on shared nodes corrupts previously constructed trees; allocate a fresh root node for each Cartesian product pair.
The theory behind it
BST — the ground this problem stands on. All BST problems
What BST is
A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.
When to reach for it
Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.
How the pattern works
Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.
More BST problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .