Question:

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

Thinking:

It’s a simple dynamic programming question. For n numbers, we should consider the situation that every one become the root, and delete it from the sets and do the same thing for their children.

Solution:

public class Solution {
    public List<TreeNode> generateTrees(int n) {
        return dp(1, n);
    }

    public List<TreeNode> dp(int low, int high){
        List<TreeNode> res = new ArrayList<TreeNode>();
        if (low == high){
            TreeNode n = new TreeNode(low);
            res.add(n);
            return res;
        }
        for (int i = low; i <= high; i++){
            TreeNode n = new TreeNode(i);
            if (i == low){
                for (TreeNode p: dp(low+1, high)){
                    n.right = p;
                    res.add(n);
                    n = new TreeNode(i);
                }
            }
            else if (i == high){
                for (TreeNode p: dp(low, high-1)){
                    n.left = p;
                    res.add(n);
                    n = new TreeNode(i);
                }
            }
            else{
                for (TreeNode p: dp(low, i-1)){
                    for (TreeNode q: dp(i+1, high)){
                        n.left = p;
                        n.right = q;
                        res.add(n);
                        n = new TreeNode(i);
                    }
                }
            }
        }

        return res;
    }
}