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.
1class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
This Python code defines a TreeNode class and a recursive function 'generate_trees' that builds all unique BSTs for integers between 'start' and 'end'. It selects each number as the root and recursively builds 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.
1class TreeNode:
2 def
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 Python code employs memoization via the 'lru_cache' decorator to efficiently store and reuse the results of previously computed subproblems within the recursive 'generate_trees' function.