# A simple bottom-up DP solution

• The optimal substructure is that for any BST with nodes 1 to n, pick i-th node as root, then the left subtree will contain nodes from 1 to (i-1), and the right subtree will contain nodes from (i+1) to n. I use a 3-d vector to store all possible trees for subtrees with nodes from i to j (0 <= i <= j <=n+1 ), if i==j, there is only one-node tree; if j = i-1, then there is no actual node(storing NULL pointer). Use a bottom up solution to generate all possible subtrees with nodes i to j. Finally the result will be the subtree set with nodes 1 to n,

``````	vector<TreeNode *> generateTrees(int n) {
if(n == 0)	return vector<TreeNode *>(1, NULL);
vector<vector<vector<TreeNode*>>> subtree(n+2, vector<vector<TreeNode*>>(n+2, vector<TreeNode*>()));
for(int i=1; i<=n+1; ++i){
subtree[i][i].push_back(new TreeNode(i));
subtree[i][i-1].push_back(NULL);
}
for(int l=2; l<=n; ++l){
for(int i=1; i<=n-l+1; ++i){
for(int j=i; j<=i+l-1; ++j){
for(int k=0; k<subtree[j+1][i+l-1].size(); ++k){
for(int m=0; m<subtree[i][j-1].size(); ++m){
TreeNode *T = new TreeNode(j);
T->left = subtree[i][j-1][m];
T->right = subtree[j+1][i+l-1][k];
subtree[i][i+l-1].push_back(T);
}
}
}
}
}
return subtree[1][n];
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.