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 <= 8The goal of Unique Binary Search Trees II is to generate all structurally unique BSTs that store values from 1 to n. The key observation is that for every value i in the range, it can act as the root of the tree. All values smaller than i must appear in the left subtree, while all larger values must appear in the right subtree.
A common strategy is to use recursive backtracking. For each candidate root, recursively generate all possible left subtrees from the range [start, i-1] and all right subtrees from [i+1, end]. Then combine every left subtree with every right subtree to form complete trees. This naturally builds every valid BST configuration.
To improve efficiency, memoization (dynamic programming) can cache results for previously computed ranges so they are not recomputed multiple times. Since the number of unique BSTs follows the Catalan sequence, the algorithm ultimately generates all valid trees. The time complexity is proportional to the number of generated trees, and additional space is used for recursion and storing the constructed structures.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursive Backtracking | O(Cn * n) where Cn is the nth Catalan number | O(Cn * n) |
| Backtracking with Memoization (DP) | O(Cn * n) | O(Cn * n) |
NeetCode
This approach involves dividing the set of integers from 1 to n into left and right subtrees recursively for each possible root value. For each possible root node, the values less than the root form the left subtree and the values greater than the root form the right subtree. We repeat this process recursively to construct all unique BSTs by selecting each number in the range as the root.
Time Complexity: O(4^n / √n) where n is the number of nodes because it involves generating all unique trees which is a Catalan number problem.
Space Complexity: O(4^n / √n) for storing the results.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
This JavaScript code utilizes a recursive mechanism to generate all unique BSTs. The 'generateTreesRange' function recursively creates trees by making selections for the root node, identifying left and right subtrees.
This approach involves leveraging dynamic programming to store results of previously evaluated subproblems to optimize the recursive solution. We maintain a memoization table to store precalculated trees for specific ranges, aiding efficient calculation by reducing the re-computation of the same subproblems.
Time Complexity: O(4^n / √n) due to solving subproblems exactly once.
Space Complexity: O(4^n / √n) for storing the memoized results.
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
unordered_map<int, vector<TreeNode*>> memo;
vector<TreeNode*> generateTrees(int start, int end) {
if (start > end) return {NULL};
int key = start * 100 + end;
if (memo.count(key)) return memo[key];
vector<TreeNode*> allTrees;
for (int i = start; i <= end; ++i) {
vector<TreeNode*> leftTrees = generateTrees(start, i - 1);
vector<TreeNode*> rightTrees = generateTrees(i + 1, end);
for (auto left : leftTrees) {
for (auto right : rightTrees) {
TreeNode* root = new TreeNode(i);
root->left = left;
root->right = right;
allTrees.push_back(root);
}
}
}
return memo[key] = allTrees;
}
vector<TreeNode*> generateTrees(int n) {
if (n == 0) return {};
return generateTrees(1, n);
}
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of BST generation and Catalan-number-based problems appear in FAANG-style interviews. They test understanding of recursion, tree structures, and dynamic programming optimization techniques.
Binary trees are the primary data structure used in this problem. The solution constructs TreeNode structures recursively, combining left and right subtrees to build all valid binary search trees.
The optimal approach uses recursive backtracking combined with memoization. Each value in the range is treated as a root, and all possible left and right subtrees are generated recursively. Memoization avoids recomputing subtree ranges, improving efficiency.
The number of structurally unique BSTs that can be formed with n nodes follows the Catalan number sequence. Each possible root splits the problem into left and right subtrees, which leads to the same recurrence relation as Catalan numbers.
This C++ solution uses a map to cache results of subproblem solutions. The 'memo' map stores results for each range, saving time by avoiding duplicate computations in the recursive process.