Watch 10 video solutions for Unique Binary Search Trees II, a medium level problem involving Dynamic Programming, Backtracking, Tree. This walkthrough by NeetCode has 77,933 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.
Example 1:
Input: n = 3 Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
Example 2:
Input: n = 1 Output: [[1]]
Constraints:
1 <= n <= 8Problem Overview: Given an integer n, generate every structurally unique binary search tree that stores values from 1 to n. Each tree must satisfy BST ordering and the result should return the root node of every valid structure.
Approach 1: Recursive Tree Construction (Backtracking) (Time: ~O(Cn * n), Space: ~O(Cn * n))
This approach builds trees by choosing every number in the range [start, end] as the root. For a chosen root i, recursively generate all left subtrees from [start, i-1] and all right subtrees from [i+1, end]. Combine each left subtree with each right subtree to form complete BSTs. The key insight is that BST structure depends entirely on which value is selected as the root and how the remaining values split into left and right ranges.
This technique naturally maps to backtracking over value ranges. The number of possible trees equals the Catalan number Cn, so the algorithm must construct roughly Cn trees, each taking up to O(n) work to link nodes.
Approach 2: Dynamic Programming with Memoization (Time: ~O(Cn * n), Space: ~O(Cn * n))
Recursive generation recomputes the same subtree ranges many times. Memoization avoids that by caching results for each interval (start, end). When the algorithm requests trees for the same range again, it returns the stored list instead of recomputing it.
This transforms the recursion into a classic dynamic programming problem over intervals. Each state represents all BSTs possible from a value range. By reusing computed subtrees, the algorithm significantly reduces repeated recursion while still enumerating all valid BST structures.
Recommended for interviews: Interviewers usually expect the recursive construction first because it clearly shows understanding of BST properties and recursive tree generation. Adding memoization demonstrates optimization skills and knowledge of interval-based dynamic programming. Both approaches share the same theoretical complexity because the algorithm must output every valid BST.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Tree Construction | ~O(Cn * n) | ~O(Cn * n) | Best for understanding BST structure generation and interview explanations |
| Dynamic Programming with Memoization | ~O(Cn * n) | ~O(Cn * n) | Use when avoiding repeated recursion over the same value ranges |