Watch 10 video solutions for Unique Binary Search Trees II, a medium level problem involving Dynamic Programming, Backtracking, Tree. This walkthrough by NeetCodeIO has 31,940 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 follow BST ordering rules, and the result returns the root node of every valid tree configuration.
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]. Then combine every left subtree with every right subtree to form complete trees. The recursion explores all possible root choices, which naturally generates every valid structure. The total number of generated trees follows the Catalan sequence (Cn), which leads to exponential growth in the number of outputs.
This technique is essentially backtracking over root selections while constructing nodes that satisfy binary search tree ordering rules. It’s simple and mirrors the recursive definition of BSTs, making it the most common interview implementation.
Approach 2: Dynamic Programming with Memoization (Time: O(Cn * n), Space: O(Cn * n))
The recursive solution repeatedly recomputes subtrees for the same ranges. Memoization removes that duplication. Cache the result of generate(start, end) in a hash map or 2D table so the subtree list is built only once. When the recursion encounters the same range again, return the cached trees instead of rebuilding them.
This converts the brute recursive exploration into a classic dynamic programming problem over intervals. Each state represents all BSTs formed from a specific number range. Although the total number of produced trees is still Catalan-sized, memoization significantly reduces repeated recursion and improves practical performance.
Recommended for interviews: Start with the recursive tree construction because it clearly demonstrates understanding of BST structure and recursive decomposition. Then mention memoization as an optimization to eliminate repeated subtree generation. Interviewers typically expect the recursive formulation first, followed by the DP improvement.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Tree Construction (Backtracking) | O(Cn * n) | O(Cn * n) | Best for interviews and understanding BST structure. Straightforward recursion. |
| Dynamic Programming with Memoization | O(Cn * n) | O(Cn * n) | Use when avoiding repeated subtree computation. More efficient for larger n. |