Log inSign up
mediumLeetCodeNot Started

Unique Binary Search Trees II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

Given an integer n, return *all the structurally unique BSTs (binary search trees), which has exactly n nodes of unique values from 1 to n*. Return the answer in any order.

---

### Examples

Example 1: ``text 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: ``text Input: n = 1 Output: [[1]]

---

### Constraints - 1 <= n <= 8

Constraints:

  • 1 <= n <= 8

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master interval-based divide-and-conquer recursion for tree generation.
  • Understand why returning [null] for empty intervals correctly anchors leaf nodes.
  • Analyze time complexity proportional to Catalan numbers C(n) * n.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Generating all actual tree structures (not just counting)
  • Subproblems depend on contiguous integer ranges [start, end]
  • Combinatorial tree assembly via Cartesian product of left and right forest

Algorithmic Decision Tree:

  • If tasked with enumerating all BSTs for range [1..n] -> Divide and conquer on interval [start, end].
  • For each root i in [start..end], link every combination of leftTree in generate(start, i-1) and rightTree in generate(i+1, end).

Connected Patterns:

Unique Binary Search TreesDifferent Ways to Add ParenthesesConstruct Binary Tree from Inorder and Postorder

1. Recursive Divide and Conquer

Intuition

Any value i in [start, end] can be root. All valid left subtrees are generated by [start, i - 1] and valid right subtrees by [i + 1, end]. For each pair (left, right), create a new TreeNode(i, left, right).

Algorithm

  1. If start > end, return list containing null (representing empty subtree).
  2. Initialize list allTrees.
  3. For i from start to end:
  4. Generate leftSubtrees = buildTrees(start, i - 1).
  5. Generate rightSubtrees = buildTrees(i + 1, end).
  6. For each left in leftSubtrees:
  7. For each right in rightSubtrees:
  8. Create root = new TreeNode(i, left, right).
  9. Append root to allTrees.
  10. Return allTrees.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
10};
11
12class Solution {
13public:
14 std::vector<TreeNode*> generateTrees(int n) {
15 if (n == 0) return {};
16 return build(1, n);
17 }
18
19private:
20 std::vector<TreeNode*> build(int start, int end) {
21 if (start > end) return {nullptr};
22 std::vector<TreeNode*> allTrees;
23 for (int i = start; i <= end; ++i) {
24 std::vector<TreeNode*> leftTrees = build(start, i - 1);
25 std::vector<TreeNode*> rightTrees = build(i + 1, end);
26 for (auto* l : leftTrees) {
27 for (auto* r : rightTrees) {
28 allTrees.push_back(new TreeNode(i, l, r));
29 }
30 }
31 }
32 return allTrees;
33 }
34};
35
36int main() {
37 Solution sol;
38 auto trees = sol.generateTrees(3);
39 std::cout << "Generated " << trees.size() << " unique BSTs for n=3 (Expected: 5)\n";
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(4^n / sqrt(n))
  • Space complexity: O(4^n / sqrt(n))

2. Memoized Divide and Conquer

Intuition

Subranges like [2, 3] are generated repeatedly when root is 1, and again as part of larger ranges. Caching list of trees for (start, end) avoids re-running Cartesian products.

Algorithm

  1. Create memoization map memo keyed by (start, end).
  2. If start > end, return [null].
  3. If key in memo, return memo[key].
  4. Iterate root i from start to end, combine memoized build(start, i-1) and build(i+1, end).
  5. Store and return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <map>
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x, TreeNode *l = nullptr, TreeNode *r = nullptr) : val(x), left(l), right(r) {}
10};
11
12class Solution {
13 std::map<std::pair<int, int>, std::vector<TreeNode*>> memo;
14public:
15 std::vector<TreeNode*> generateTrees(int n) {
16 if (n == 0) return {};
17 return build(1, n);
18 }
19
20private:
21 std::vector<TreeNode*> build(int start, int end) {
22 if (start > end) return {nullptr};
23 if (memo.count({start, end})) return memo[{start, end}];
24
25 std::vector<TreeNode*> res;
26 for (int i = start; i <= end; ++i) {
27 auto left = build(start, i - 1);
28 auto right = build(i + 1, end);
29 for (auto* l : left) {
30 for (auto* r : right) {
31 res.push_back(new TreeNode(i, l, r));
32 }
33 }
34 }
35 return memo[{start, end}] = res;
36 }
37};
38
39int main() {
40 Solution sol;
41 auto res = sol.generateTrees(3);
42 std::cout << "Memoized count: " << res.size() << " (Expected: 5)\n";
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(4^n / sqrt(n))
  • Space complexity: O(4^n / sqrt(n))

3. Dynamic Programming with Offset Tree Cloning

Intuition

A tree structure on keys [1..k] is isomorphic to any tree structure on [offset+1 .. offset+k]. We only generate canonical normalized trees for lengths 0..n, and clone them with value offsets to assemble larger trees without recursion.

Algorithm

  1. Maintain dp[len] as list of unique BSTs on values 1..len.
  2. dp[0] = [null].
  3. For len from 1 to n:
  4. dp[len] = []
  5. For root j from 1 to len:
  6. For each leftTree in dp[j - 1]:
  7. For each rightTree in dp[len - j]:
  8. Create root node with value j.
  9. root.left = leftTree;
  10. root.right = cloneTreeWithOffset(rightTree, j);
  11. dp[len].append(root);
  12. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x, TreeNode *l = nullptr, TreeNode *r = nullptr) : val(x), left(l), right(r) {}
9};
10
11class Solution {
12 TreeNode* cloneWithOffset(TreeNode* root, int offset) {
13 if (!root) return nullptr;
14 TreeNode* copy = new TreeNode(root->val + offset);
15 copy->left = cloneWithOffset(root->left, offset);
16 copy->right = cloneWithOffset(root->right, offset);
17 return copy;
18 }
19public:
20 std::vector<TreeNode*> generateTrees(int n) {
21 if (n == 0) return {};
22 std::vector<std::vector<TreeNode*>> dp(n + 1);
23 dp[0] = {nullptr};
24
25 for (int len = 1; len <= n; ++len) {
26 for (int rootVal = 1; rootVal <= len; ++rootVal) {
27 int leftLen = rootVal - 1;
28 int rightLen = len - rootVal;
29 for (auto* leftTree : dp[leftLen]) {
30 for (auto* rightTree : dp[rightLen]) {
31 TreeNode* root = new TreeNode(rootVal);
32 root->left = cloneWithOffset(leftTree, 0);
33 root->right = cloneWithOffset(rightTree, rootVal);
34 dp[len].push_back(root);
35 }
36 }
37 }
38 }
39 return dp[n];
40 }
41};
42
43int main() {
44 Solution sol;
45 auto res = sol.generateTrees(3);
46 std::cout << "DP with Offset count: " << res.size() << " (Expected: 5)\n";
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(4^n / sqrt(n))
  • Space complexity: O(4^n / sqrt(n))

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Divide and ConquerO(4^n / sqrt(n))O(4^n / sqrt(n))Recursively build trees for [start, end] with Cartesian product.Output construction size
2.Memoized Interval SearchO(4^n / sqrt(n))O(4^n / sqrt(n))Cache generated subtrees for each (start, end) range.Output construction size
3.Bottom-Up DP with Offset CloningOptimalO(4^n / sqrt(n))O(4^n / sqrt(n))Iteratively build canonical trees of size k and clone with root offsets.Cloning operations

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Returning an empty list [] instead of [null] for empty intervals, causing the tree creation loop to be skipped entirely.

Pitfall 2:

Reusing the exact same root TreeNode object across multiple iterations, overwriting child pointers.

Pitfall 3:

Trying to generate permutations and filter them instead of generating valid BSTs directly.

Crucial Edge Cases to Validate:

  • n = 1 — Returns a single tree with node value 1: [[1]].
  • n = 8 (maximum constraint) — Catalan(8) = 1430 unique trees. Handled efficiently within standard execution limits.
  • Left or right subtree empty — Properly linked to null without crashing or creating dummy nodes.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether subtrees may share node instances or must be deep-copied.
  2. Highlight the contrast with Unique BSTs I: problem I is counting (1D DP integer), whereas problem II is generating (forest Cartesian products).
  3. Explain how returning [null] anchors leaf nodes cleanly without cumbersome null checks.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the base case start > end return [null] rather than an empty list []?

2.How many total unique BSTs are generated when n = 4?

3.Why is offset cloning used in bottom-up DP for Unique BSTs II?

Back to DSA Sheet