Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

• Time: O(n)
• Space: O(1)

public List<TreeNode> generateTrees(int n) {
    if (n == 0) return new ArrayList<>();
    return generateTreesHelper(1, n);
}

private List<TreeNode> generateTreesHelper(int start, int end) {
    List<TreeNode> ret = new ArrayList<>();
    if (start >= end) {
        ret.add(null);
        return ret;
    }
    for (int i = start; i <= end; i++) {
        List<TreeNode> left = generateTreesHelper(start, i - 1);
        List<TreeNode> right = generateTreesHelper(i + 1, end);
        for (TreeNode l : left) {
            for (TreeNode r : right) {
                TreeNode node = new TreeNode(i);
                node.left = l;
                node.right = r;
                ret.add(node);
            }
        }
    }
    return ret;
}