## Unique Binary Search Tree II

07/07/2016 Tree Dynamic Programming

## Question

Given an integer 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


## Solution

Result: Accepted Time: 28 ms

Here should be some explanations.

class Solution {
public:
vector<TreeNode*> dfs(int left,int right)
{
if(left >= right)
return vector<TreeNode*>{NULL};
vector<TreeNode*> ret;
for(int i = left; i < right; i++)
{
vector<TreeNode*> lvect = dfs(left,i);
vector<TreeNode*> rvect = dfs(i+1,right);
for(const auto &lft:lvect)
for(const auto & rht:rvect)
{
TreeNode * tmp = new TreeNode(i);
tmp->left = lft;
tmp->right = rht;
ret.push_back(tmp);
}
}
return ret;
}
vector<TreeNode*> generateTrees(int n) {
if(!n) return vector<TreeNode*>();
return dfs(1,n+1);
}
};


Complexity Analytics

• Time Complexity: $O(n!)$?
• Space Complexity: $O(n!)$?