Link: https://leetcode.com/problems/unique-binary-search-trees-ii/
Solution:
Topics: DFS, DP, recursion, catalan number, divide and conquer
Intuition
This is quite an interesting problem, and in some ways the core insight is not dissimilar to Balance a binary search tree. If we look at the constraints and nature of the problem, it’s pretty clear that this is a backtracking problem… so how is it similar to Balance a binary search tree?
In Balance a binary search tree, we sort the nodes (or perform an in-order traversal) and then find the parent recursively by choosing the mid in the current partition. For this problem, we must exhaust every possible option for the parent, not just the parent that guarantees a balanced tree! And of course we must do this recursively.
An easy way to think about this is realizing that somewhere in our list of trees there MUST be at least n-1 trees where the root (parent) is 1-n. And this is true recursively, so when we chose a parent, the left child can be any value between 1, parent-1 and the right child can be any value between parent+1, n. So we can set up the recursion to return a list of left and right children for the current node!
The last step is to duplicate the parent for each combination of left and right child, because this represents all possible trees. Caching (DP) is also a useful optimization because we will have large branches in our trees (relative to each other) that are duplicated so It makes sense to store the subtrees in a memo instead of backtracking for each tree.
Implementation
def generate_trees(n):
@cache
def dfs(l, r):
if l > r:
return [None]
trees = []
for parent_val in range(l, r+1):
left_children = dfs(1, parent_val-1)
right_children = dfs(parent_val+1, n)
for l_child in left_children:
for r_child in right_children:
parent = TreeNode(parent_val)
parent.left = l_child
parent.right = r_child
trees.append(parent)
return trees
return dfs(1, n)
#time: o(n*catalan(n))
#there are (4**n)/n**1.5 unique trees with n nodes... this is an aproximation of the nth catalan number.
#each unique tree takes o(n) time to build.
#memory: o(catalan(r-l+1) + catalan(r-l+1) ...)
#the space complexity is dominated by the cache, so what is in the cache?
#the cache contains every pair (l,r), and stores every possible tree in that range
#how many unique trees are in the range (l,r)?
#its simply the catalan number with respect to k, where k equals the number of nodes in the range (l,r)...which is simply r-l+1. Mnemonic
Same as Balance a binary search tree, but instead of picking up the string in the middle, we pick it up in every possible spot (recursively). For time/space complexity, remember a chess knight (catalan opening).
Visual
Review 1
Great problem! Quite tricky, but the main thing to remember is that we should be trying all possible values for the current node. In Balance a binary search tree we used the mid as the value for the current node, but here we must try all possible values. For the root of the tree that becomes all values between 1-n. Then we recursively get all possible left and right nodes, and create a new tree with each combination.
The time and space complexity is still bewildering to me. Just remember the nth catalan number.