# C++ recursive solution, easy to understand

• for root at i, the unique BST has left child as all unique BST between 1 to i-1, has right child as all unique BST between i+1 to n. And the overall results have root traverse from 1 to n. So this intuitively lead to a recursive solution.

The help function is used to generate all combination of unique BST in a given range

``````class Solution {
public:
vector<TreeNode*> generateTrees(int n)
{
vector<TreeNode*> ans;
if(n<1) return ans;
for(int i = 1; i <= n; i++)
{
vector<TreeNode*> left = help(1,i-1);
vector<TreeNode*> right = help(i+1,n);
for(auto l : left)
{
for(auto r : right)
{
TreeNode * root = new TreeNode(i);
root -> left = l;
root -> right = r;
ans.push_back(root);
}
}

}
return ans;
}

vector<TreeNode*> help(int start, int end)
{
vector<TreeNode*> ans;
if(start>end)
{
ans.push_back(NULL);
return ans;
}
for(int i = start; i<= end; i++)
{
vector<TreeNode*> left = help(start,i-1);
vector<TreeNode*> right = help(i+1,end);
for(auto l : left)
{
for(auto r : right)
{
TreeNode * root = new TreeNode(i);
root -> left = l;
root -> right = r;
ans.push_back(root);
}
}
}
return ans;
}

};``````

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