The first method that came to mind was the brute force solution as below.

```
public List<TreeNode> generateTrees(int n) {
return generateTrees(1,n);
}
public List<TreeNode> generateTrees(int start,int end){
List<TreeNode> trees = new ArrayList<TreeNode>();
if(start>end){ trees.add(null); return trees;}
for(int rootValue=start;rootValue<=end;rootValue++){
List<TreeNode> leftSubTrees=generateTrees(start,rootValue-1);
List<TreeNode> rightSubTrees=generateTrees(rootValue+1,end);
for(TreeNode leftSubTree:leftSubTrees){
for(TreeNode rightSubTree:rightSubTrees){
TreeNode root=new TreeNode(rootValue);
root.left=leftSubTree;
root.right=rightSubTree;
trees.add(root);
}
}
}
return trees;
}
```

Then @6219221 reminded me it is unnecessary to create the BSTs with all brand new nodes.

Assume you have a list of all BSTs with values from 1 to n-1, every possible way to insert value n only involves changing the right tree (root inclusive) because n is always greater than root.val and the left subtree structure is fixed. So all we gotta do is to create a new copy of the right part of the tree and point the new root.left to the original left subtree. This way we reuse the left tree, which saves time and space.

How to insert Node n into the right subtree?

Given any BST on the n - 1 level, it will be only valid to put n on the root.right, root.right.right or root.right.....right locations and then move the right subtree of n.right...right to become the left child of n, in order to keep n on the right-most position as the greatest value in the tree.

Here is my implementation. Note that I do the dp from [n] back to [n to 1]. Therefore all the right subtree structures are fixed and new values are inserted into the left side, opposite to making BSTs from 1 to [1 to n].

```
public List<TreeNode> generateTrees(int n) {
List<TreeNode> res = new ArrayList<>();
res.add(null);
for(; n > 0; n--) {
List<TreeNode> next = new ArrayList<>();
for(TreeNode node: res) {
//the special case when Node(n) is root of new tree
TreeNode root = new TreeNode(n);
root.right = node;
next.add(root);
//while loop inserts new value to every possible position into the left tree side
while(node != null) {
TreeNode cRoot = new TreeNode(root.right.val);
//clone left subtree
cRoot.left = copyTree(root.right.left);
//reusing - point new root.right to the original right subtree
cRoot.right = root.right.right;
//curr is the cutoff node whose right child will be replaced by the new n
TreeNode curr = getValNode(cRoot, node.val);
//place n as curr's right child, make curr's original right child as the left child of n.
TreeNode tmp = curr.left;
curr.left = new TreeNode(n);
curr.left.right = tmp;
next.add(cRoot);
node = node.left;
}
}
res = next;
}
return res;
}
private TreeNode getValNode(TreeNode n, int val) { //find the cutoff node in the new tree
while(n != null) {
if(n.val == val) break;
n = n.left;
}
return n;
}
private TreeNode copyTree(TreeNode root) { //clone the right subtree
if(root == null) return null;
TreeNode cRoot = new TreeNode(root.val);
cRoot.left = copyTree(root.left);
cRoot.right = copyTree(root.right);
return cRoot;
}
```