# Unique Binary Search Trees II

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]
]

Explanation:

The above output corresponds to the 5 unique BST's shown below:

1         3     3      2      1
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3
``````

## Analysis

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

Similar thinking to Unique Binary Search Trees, the core of building a BST from sorted array 1, ..., n is to select a root, then build left subtrees and right subtrees recursively. The tricky part in this problem however, is to combine different subtrees and root node to unique BSTs.

Three loops

1. loop over `start, ..., end` and select `i` for the root node; (recursively) build left subtrees with left subsequence `start, ..., i - 1`; build right subtrees with right subsequence `i + 1, ..., end`
2. loop over left subtrees, with root node for left subtrees; TreeNode leftNode
3. loop over right subtrees, with root node for right subtrees; TreeNode rightNode

Note: create a new root has to be inside the 3rd loop, and then set root.left = leftNode, root.right = rightNode, and finally add to result list.

The number of possible BST is actually a Catalan number.

Time complexity:
Catalan number G_n. This is done `n` times, that results in time complexity `n*G_n`

Catalan numbers grow as `{4^n}/{n^{3/2}`
Thus, ​final time complexity `O({4^n}/{n^{1/2})`

Space complexity:
keeps `n*G_n` Catalan trees, thus space complexity: `O({4^n}/{n^{1/2})`

## Solution

``````class Solution {
public List<TreeNode> generateTrees(int n) {
if (n == 0) return new ArrayList<TreeNode>();

return generateTrees(1, n);
}
private List<TreeNode> generateTrees(int start, int end) {
List<TreeNode> trees = new ArrayList<TreeNode>();

if (start > end) {
return trees;
}

// select root, and generate sub trees recursively

for (int i = start; i <= end; i++) {
List<TreeNode> leftSubtrees = generateTrees(start, i - 1);
List<TreeNode> rightSubtrees = generateTrees(i + 1, end);

for (TreeNode leftTree : leftSubtrees) {

for (TreeNode rightTree : rightSubtrees) {
TreeNode root = new TreeNode(i);
root.left = leftTree;
root.right = rightTree;
}
}
}
return trees;

}
}
``````
``````class Solution {
public List<TreeNode> generateTrees(int n) {

List<TreeNode> res1 = new ArrayList<TreeNode>();
if(n <= 0)
{
return res1;
}

return genTree(1, n);
}

private List<TreeNode> genTree(int start, int end)
{
List<TreeNode> res = new ArrayList<TreeNode>();

if(start > end)
{
return res;
}

if(start == end)
{
return res;
}

List<TreeNode> left;
List<TreeNode> right;

for(int i = start; i <= end; i++)
{
left = genTree(start, i - 1);
right = genTree(i + 1, end);

for(TreeNode lnode : left)
{
for(TreeNode rnode : right)
{
TreeNode root = new TreeNode(i);
root.left = lnode;
root.right = rnode;