Problem Description
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
The description was taken from https://leetcode.com/problems/unique-binary-search-trees-ii/.
Problem Solution
#O(?) Time, O(?) Space (Catalan Number)
class Solution:
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
def construct(left:int, right:int) -> TreeNode:
if left > right:
return [None]
bucket = []
for i in range(left, right+1):
left_bucket = construct(left, i-1)
right_bucket = construct(i+1, right)
for left_node in left_bucket:
for right_node in right_bucket:
root = TreeNode(i)
root.left = left_node
root.right = right_node
bucket.append(root)
return bucket
return construct(1, n)Problem Explanation
In the first variation of this problem, we just had to return the count of binary trees instead of the binary trees themselves.
In this version, we have to return the binary tree combinations.
That is typically the pattern, if the problem requires a count of each combination then it may usually be solved with dynamic programming, but if the combinations need to be returned in a matrix, list. or string then recursion or backtracking may be required. If only a count is required then that may come down to counting subproblems, otherwise, the subproblems need to actually be built which is why the plain recursive or backtracking solutions have a worse time and space complexity.
Here we are going to need to build each unique combination.
If the tree combinations were balanced, then we could just create permutations of the range and create trees from those permutations. However, we can see that some of these get funky, looking like linked lists so that isn't going to work.
The solution we'll implement won't be too distant from that though.
What we can do is handle this problem as we would converting an array to a binary tree.
We'll pick a root, not the middle node as we would for a balanced binary tree, but just the current index as we did in the first variation of this problem, and from there we will create our left and right subtrees. The left and right subtrees won't be the remaining left and right ranges though, it will be from a pool of left and right nodes that we will be creating within each recursive call.
Within each recursive call, we will traverse the given range and pick a root at each index. From there, we will need to create our left and right subtrees. To do that, we will throw each possible left subtree into a left bucket, and each possible right subtree into a right bucket.
We will then traverse each left subtree we have in our left bucket and each right subtree we have in our right bucket, attaching them to the current root node that we picked from the current index.
Each time we do this, we will append each new combination to a bucket that we'll be able to pass up to each recursive parent call that is requiring left and right buckets. This is how we will be building each subproblem, as mentioned previously.
Once we have exhausted each possible combination, the final bucket from the root recursive function call will contain each tree combination.
Let's create our tree construction function.
This function will take a left and right pointer that will define the boundaries of the nodes we will be picking a root from.
if left > right:
return [None]
Next, we'll create a bucket to throw each tree combination that we'll be building into.
This idea is similar to Divide and Conquer strategies, initially, these buckets will be empty, then they will contain one node that a parent recursive call will be able to pick and build a tree from, then two, etc.
bucket = []
For each index within the current range, we will pick a root node and build our trees.
for i in range(left, right+1):
We'll start by filling the left and right buckets from the left and right ranges of the current root index, excluding the root index.
left_bucket = construct(left, i-1)
right_bucket = construct(i+1, right)
Then, for each left subtree root node in the left bucket and each right subtree root node in the right bucket, we will create a root node, make the root's left child the left subtree root node, make the root's right child the right subtree root node, and then append the root node to the bucket.
for left_node in left_bucket:
for right_node in right_bucket:
root = TreeNode(i)
root.left = left_node
root.right = right_node
bucket.append(root)
This will allow us to continuously fill buckets at the lower end of the recursive tree with subtrees that the root recursive function call will be able to pick and choose from to create each tree combination.
return bucket
Now that our helper function is built, all we need to do is make the initial call to build each combination and return these combinations in the first bucket that was created within the recursive tree at the root function call.
return construct(1, n)