# 95. Unique Binary Search Trees II (Medium)

https://leetcode.com/problems/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
```

## Solutions

``````class Solution {

// The straight forward solution is firstly sort out all the possible tree patterns. Then for each tree,
// populate the values by inorder traversal.

int val = 1;

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

// First get all the patterns of trees
List<TreeNode> ans = recurse(n);

for (TreeNode node : ans) {
// every time reset the val count
val = 1;

// Inorder traversal and set the values
setValue(node);
}

return ans;
}

private void setValue(TreeNode root) {
if (root == null) {
return;
}

setValue(root.left);

root.val = val++;

setValue(root.right);
}

private List<TreeNode> recurse(int n) {
if (n == 0) {
return null;
}

List<TreeNode> ans = new ArrayList<>();

if (n == 1) {

return ans;
}

for (int i = 0; i < n; i++) {
// left i nodes
List<TreeNode> left = recurse(i);

// right n - i - 2 nodes
List<TreeNode> right = recurse(n - i - 1);

// combine the left and right branch
combine(left, right, ans);
}

return ans;
}

private void combine(List<TreeNode> left, List<TreeNode> right, List<TreeNode> ans) {
// Technically, below situation will never happen
if (left == null && right == null) {
return;
}

// if left == null
if (left == null) {
for (TreeNode node : right) {
TreeNode root = new TreeNode(0);

root.left = null;
root.right = node;

}

return;
}

// if right == null
if (right == null) {
for (TreeNode node : left) {
TreeNode root = new TreeNode(0);

root.left = node;
root.right = null;

}

return;
}

// if left != null && right != null
for (TreeNode l : left) {
for (TreeNode r : right) {
TreeNode root = new TreeNode(0);

root.left = l;
root.right = r;

}
}
}
}
``````