# Leetcode 95 Solution

https://leetcode.com/problems/unique-binary-search-trees-ii

## Solution

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int l, int r)
{
vector<TreeNode*> res;

if (l == r)
{
TreeNode* node = new TreeNode(l);
res.push_back(node);
return res;
}

for (int i = l; i <= r; i++)
{
vector<TreeNode*> left_trees;
vector<TreeNode*> right_trees;

if (i == l)
left_trees.push_back(NULL);
else
left_trees = generateTrees(l, i - 1);

if (i == r)
right_trees.push_back(NULL);
else
right_trees = generateTrees(i + 1, r);

for (auto it1 = left_trees.begin(); it1 != left_trees.end(); it1++)
{
for (auto it2 = right_trees.begin(); it2 != right_trees.end(); it2++)
{
TreeNode* root = new TreeNode(i);
root->left = *it1;
root->right = *it2;

res.push_back(root);
}
}
}

return res;
}

vector<TreeNode*> generateTrees(int n) {
return generateTrees(1, n);
}
};
``````