Problem
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.
Testcases
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]]
Initial Result
Time spent: 20 min
Fail. Backtracked with no DP and did not successfully construct binary search trees (just the roots).
Initial Approach
I treated this as a backtracking problem and chose to add nodes by iterating through all available numbers and either attaching their respective nodes to the left or right depending on its value relative to the root node (for which I looped separately). This was combined with a visited set to avoid infinitely attaching repeating nodes.
What I Missed
When generating binary search trees, we should specify our left and right bounds for our recursive function such that we can attach all different nodes from the bottom-up recursively. This method works since we can narrow down to a leaf node (no left and right children) at the base case level.
Approach to the Solution
Memoize our function the super-simple and obvious way: a dp cache connecting the (l, r) inputs to the list of trees generated by that function call. We start at bounds of 1 and n as expected. In the function, we maintain the aforementioned trees list to store all of our output. We loop over all candidate values and then generate left and right trees via recursive calls. This goes down the recursive stack and builds up from the level of the leaves. After that, we have our available options for which nodes can be assigned left/right. We can then append a new node to the list. Once completed, we should memoize our state with our trees list and then return that same list.
Key Takeaways
Practice generating binary search trees recursively. Also, I should focus on the state of dynamic programming problems that are more unique like this one (though the state here was still obvious).