# LC95 Unique Binary Search Tree

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]

``````/**
* 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 n) {
if(n < 1)
return vector<TreeNode*>(0);
return genRoots(1, n);
}
vector<TreeNode*> genRoots(int start, int end){
vector<TreeNode*> res;
if(start > end){
return vector<TreeNode*>(1,NULL);
}

for(int i = start; i <= end; i ++){
vector<TreeNode*>left = genRoots(start, i - 1);
vector<TreeNode*>right = genRoots(i + 1, end);
//then put the connect the root with all possible left and right child
for(int j = 0; j < left.size(); j ++){
for(int k = 0; k < right.size(); k ++){
TreeNode *curRoot = new TreeNode(i);
curRoot -> left = left[j];
curRoot -> right = right[k];
res.push_back(curRoot);
}
}
}
return res;
}
};
``````