Unique Binary Search Trees II
MedPrompt
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 <= 8
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a straightforward recursive method to construct all possible Binary Search Trees. The core idea is based on the definition of a BST: for any chosen root i from the range [1, n], all values smaller than i must go into the left subtree, and all values larger than i must go into the right subtree. We can recursively generate all possible left and right subtrees and then combine them for each choice of root i.
Algorithm
- Define a recursive function, say
generate(start, end), that returns a list of all unique BSTs for values in the range[start, end]. - The main function calls
generate(1, n). - In
generate(start, end):- If
start > end, it signifies an empty subtree. Return a list containing a singlenullelement to represent this. - Initialize an empty list,
all_trees, to store the generated BSTs for the current range. - Iterate with a loop variable
ifromstarttoend. Thisiwill serve as the root of a BST. - Make a recursive call to
generate(start, i-1)to get all possible left subtrees. - Make another recursive call to
generate(i+1, end)to get all possible right subtrees. - Nest two loops to iterate through each
left_treefrom the list of left subtrees and eachright_treefrom the list of right subtrees. - Inside the loops, for each pair of
(left_tree, right_tree), create a newTreeNodewith valuei. Set itsleftchild toleft_treeand itsrightchild toright_tree. - Add this newly constructed tree to the
all_treeslist.
- If
- After the loops complete, return the
all_treeslist.
Walkthrough
The algorithm defines a helper function, generateSubtrees(start, end), which is responsible for generating all BSTs using numbers from start to end. For each number i in this range, we consider it as the root. Then, we recursively call the function to generate all possible left subtrees from the range [start, i-1] and all possible right subtrees from [i+1, end]. Finally, we combine each left subtree with each right subtree to form a new tree rooted at i.
The base case for the recursion is when start > end, which represents an empty range. In this case, we return a list containing null to signify an empty subtree. This null is crucial for the loops that combine subtrees, ensuring they execute correctly even when one side is empty.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<TreeNode> generateTrees(int n) { if (n == 0) { return new ArrayList<>(); } return generateSubtrees(1, n); } private List<TreeNode> generateSubtrees(int start, int end) { List<TreeNode> allTrees = new ArrayList<>(); if (start > end) { allTrees.add(null); return allTrees; } // Pick each number in the range as a root for (int i = start; i <= end; i++) { // Generate all possible left subtrees List<TreeNode> leftSubtrees = generateSubtrees(start, i - 1); // Generate all possible right subtrees List<TreeNode> rightSubtrees = generateSubtrees(i + 1, end); // Combine each left subtree with each right subtree for (TreeNode left : leftSubtrees) { for (TreeNode right : rightSubtrees) { TreeNode root = new TreeNode(i); root.left = left; root.right = right; allTrees.add(root); } } } return allTrees; }}Complexity
Time
Exponential, O(3^N)
Space
O(N * G_N)
Trade-offs
Pros
The logic is simple and directly follows the mathematical definition of constructing BSTs.
It's relatively easy to implement.
Cons
Highly inefficient due to massive re-computation of the same subproblems. For example, generating trees for a range of a certain length is done multiple times with different value offsets.
This approach optimizes the brute-force recursive solution by using dynamic programming with memoization. The plain recursive solution suffers from re-calculating the results for the same subproblems (i.e., same ranges of numbers) multiple times. By storing the list of generated trees for each range [start, end] in a cache, we can avoid these redundant computations. When the function is called for a range that has been solved before, we can simply retrieve the result from the cache in constant time.
Algorithm
- Create a cache, for instance, a 2D array
memo[n+1][n+1], to store the lists ofTreeNodes for previously computed ranges. - Define a recursive helper function
generate(start, end, memo). - In
generate(start, end, memo):- If
start > end, return a list containingnull. - Check if
memo[start][end]contains a result. If it does, return the cached list immediately. - If the result is not in the cache, proceed with the same logic as the brute-force approach:
- Initialize an empty list
all_trees. - Loop
ifromstarttoendto select a root. - Recursively call
generate(start, i-1, memo)for left subtrees. - Recursively call
generate(i+1, end, memo)for right subtrees. - Combine each left and right subtree pair to form new trees with root
iand add them toall_trees.
- Initialize an empty list
- Before returning, store the computed
all_treeslist inmemo[start][end]to cache the result.
- If
- The main function initializes the cache and calls
generate(1, n, memo).
Walkthrough
The core of this approach is a memoization table, memo, which is typically a 2D array. memo[start][end] will store the list of all unique BSTs that can be formed from the numbers in the range [start, end].
The recursive helper function is modified to accept this memoization table. Before any computation, it checks if the result for the current (start, end) pair is already in the table. If so, it returns the cached value. Otherwise, it computes the result just like the brute-force method. Once the list of trees for the current range is generated, it's stored in memo[start][end] before being returned. This ensures that each subproblem is solved only once.
This technique transforms the exponential time complexity of the naive recursion into a more manageable one, making it efficient enough for the given constraints.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<TreeNode> generateTrees(int n) { if (n == 0) { return new ArrayList<>(); } List<TreeNode>[][] memo = new List[n + 1][n + 1]; return generateSubtrees(1, n, memo); } private List<TreeNode> generateSubtrees(int start, int end, List<TreeNode>[][] memo) { List<TreeNode> allTrees = new ArrayList<>(); if (start > end) { allTrees.add(null); return allTrees; } if (memo[start][end] != null) { return memo[start][end]; } for (int i = start; i <= end; i++) { List<TreeNode> leftSubtrees = generateSubtrees(start, i - 1, memo); List<TreeNode> rightSubtrees = generateSubtrees(i + 1, end, memo); for (TreeNode left : leftSubtrees) { for (TreeNode right : rightSubtrees) { TreeNode root = new TreeNode(i); root.left = left; root.right = right; allTrees.add(root); } } } memo[start][end] = allTrees; return allTrees; }}Complexity
Time
O(N * G_N)
Space
O(N * G_N)
Trade-offs
Pros
Significantly more efficient than the brute-force approach by eliminating redundant computations.
Guarantees that each subproblem is solved only once.
Cons
Requires additional space for the memoization table, which can be significant.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < TreeNode > generateTrees ( int n ) { return dfs ( 1 , n ); } private List < TreeNode > dfs ( int i , int j ) { List < TreeNode > ans = new ArrayList <>(); if ( i > j ) { ans . add ( null ); return ans ; } for ( int v = i ; v <= j ; ++ v ) { var left = dfs ( i , v - 1 ); var right = dfs ( v + 1 , j ); for ( var l : left ) { for ( var r : right ) { ans . add ( new TreeNode ( v , l , r )); } } } return ans ; } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < TreeNode *> generateTrees ( int n ) { function < vector < TreeNode *> ( int , int ) > dfs = [ & ]( int i , int j ) { if ( i > j ) { return vector < TreeNode *> { nullptr }; } vector < TreeNode *> ans ; for ( int v = i ; v <= j ; ++ v ) { auto left = dfs ( i , v - 1 ); auto right = dfs ( v + 1 , j ); for ( auto l : left ) { for ( auto r : right ) { ans . push_back ( new TreeNode ( v , l , r )); } } } return ans ; }; return dfs ( 1 , n ); } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def generateTrees ( self , n : int ) -> List [ TreeNode ]: def gen ( left , right ): ans = [] # this if check instead of if left==right then return Node(left), less hassle if left > right : ans . append ( None ) else : # right+1, to cover case when left==right for i in range ( left , right + 1 ): left_trees = gen ( left , i - 1 ) right_trees = gen ( i + 1 , right ) for l in left_trees : for r in right_trees : node = TreeNode ( i , l , r ) ans . append ( node ) return ans return gen ( 1 , n ) # n or right is inclusive ############ # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def generateTrees ( self , n : int ) -> List [ Optional [ TreeNode ]]: def dfs ( i : int , j : int ) -> List [ Optional [ TreeNode ]]: if i > j : return [ None ] ans = [] for v in range ( i , j + 1 ): left = dfs ( i , v - 1 ) right = dfs ( v + 1 , j ) for l in left : for r in right : ans . append ( TreeNode ( v , l , r )) return ans return dfs ( 1 , n )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.