Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3 

Naive Way: Since it is associated with its previous question. I'll bring the code in unique-binary-search-trees for reference.

 public class Solution {  
   public int numTrees(int n) {  
     // base case  
     if(n <= 1){return 1;}  
     // recursion  
     int sum = 0;  
     for(int i = 1;i <= n;i++)  
       sum += numTrees(i-1-0) * numTrees(n-i);  
     return sum;  
   }  
 }  

The code cannot be inherited since it demand us to return the structure itself instead of the number of the structure. But the idea can be inherited.

Use each number i as root node, then the left branch will be what's less than i, the right branch will be what's larger than i. For left branch and right branch, we can do the same trick. But this time we need to provide both boundary for the range.

This solution needs O(2^n) run time and space because of the scale of the output.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; left = null; right = null; }  
  * }  
  */  
 public class Solution {  
   public List<TreeNode> generateTrees(int n) {  
     return generateTree(1,n+1);  
   }  
   private List<TreeNode> generateTree(int min, int max){  
     List<TreeNode> list = new ArrayList<TreeNode>();  
     // base case  
     if(min >= max){  
       TreeNode node = null;  
       list.add(node);  
     }  
     // general case  
     for(int i = min;i < max;i++){  
       List<TreeNode> left = generateTree(min,i);  
       List<TreeNode> right = generateTree(i+1,max);  
       for(int p = 0;p < left.size();p++){  
         for(int q = 0;q < right.size();q++){  
           TreeNode root = new TreeNode(i);  
           root.left = left.get(p);  
           root.right = right.get(q);  
           list.add(root);  
         }  
       }  
     }  
     return list;  
   }  
 }