# When n is 0, why the OJ requires returning the list with a NULL pointer, not an empty list?

• I don't think it makes any sense to do so. When n is 0, we just cannot generate any trees, so the list should be empty.

• I found there are many other problems with edge cases that do not make sense.
A simple if(n==0){} would get around such problems as this issue does actually not bring much technical significance.

• It does seem odd when you think about it, but I actually found that including this edge case in my code with this result helped me simplify my solution. I ended up creating a helper function that generated trees from X-Y rather than 1-N, and I returned null when X > Y.

• If you think about how we define size 1 trees,
then it's most natural and consistent to say that a tree with root==null has size 0.

n=0 means we want the set of size 0 trees. It doesn't mean the set has size 0.
The set is not empty, as it still contains an empty tree with root==null

• it's a bit odd, better to have more clarification.
but i do find, at least in my code, returning an array with null makes my code simpler.

``````/**
* recursion(list<int> candidates)
* pick any as root;
* build left subtrees with candidates less than root, recursively;
* build right subtrees wtih candidates greater than root, recursively.
* use memo to improve performance.
*/
private final Map<List<Integer>, List<TreeNode>> cache =
new HashMap<List<Integer>, List<TreeNode>>();
public List<TreeNode> generateTrees(int n) {
List<Integer> candidates = new ArrayList<Integer>();
for (int i = 1; i <= n; i++)
return generateTreesHelper(candidates);
}

private List<TreeNode> generateTreesHelper(List<Integer> candidates) {
List<TreeNode> results = cache.get(candidates);
if (results != null)
return results;
results = new ArrayList<TreeNode>();
if (candidates.isEmpty()) {
results.add(null); // just to make life easier :)
} else {
for (int i = 0; i < candidates.size(); i++) {
int rootVal = candidates.get(i);
List<TreeNode> lefts  = generateTreesHelper(candidates.subList(0, i));
List<TreeNode> rights = generateTreesHelper(candidates.subList(i+1, candidates.size()));
for (TreeNode left : lefts) {
for (TreeNode right : rights) {
TreeNode root = new TreeNode(rootVal);
root.left  = left;
root.right = right;
}
}
}
}
cache.put(candidates, results);
return results;
}``````

• Adding a null to the result List make the code simple. Look at the following code which is the core of generating all the combinations of trees:

``````  for(TreeNode leftSubTree:leftSubTrees){
for(TreeNode rightSubTree:rightSubTrees){
TreeNode root=new TreeNode(rootValue);
root.left=leftSubTree;
root.right=rightSubTree;