## Algorithm

Problem Nmae: 95. Unique Binary Search Trees II

Given an integer `n`, return all the structurally unique BST's (binary search trees), which has exactly `n` nodes of unique values from `1` to `n`. Return the answer in any order.

Example 1:

```Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
```

Example 2:

```Input: n = 1
Output: [[1]]
```

Constraints:

• `1 <= n <= 8`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector generateTrees(int n) {
if(n == 0) return {};
return DFS(1, n);
}

vector DFS(int l, int r){
vectorres;
if(l > r) return {NULL};
for(int i = l; i <= r; i++){
auto left = DFS(l, i - 1);
auto right = DFS(i + 1, r);
for(auto x: left)
for(auto y: right){
TreeNode* root = new TreeNode(i);
root->left = x;
root->right = y;
res.push_back(root);
}
}
return res;
}
};
``````
Copy The Code &

Input

cmd
n = 3

Output

cmd
[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const generateTrees = function(n) {
if (n === 0) return []
return genTreeList(1, n)
}

function genTreeList(start, end) {
const list = []
if (start > end) list.push(null)
for (let idx = start; idx <= end; idx++) {
const leftList = genTreeList(start, idx - 1)
const rightList = genTreeList(idx + 1, end)
for (let left of leftList) {
for (let right of rightList) {
const root = new TreeNode(idx)
root.left = left
root.right = right
list.push(root)
}
}
}
return list
}
``````
Copy The Code &

Input

cmd
n = 3

Output

cmd
[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
def dfs(l, r):
if r < l: return [None]
arr = []
for m in range(l, r + 1):
left = dfs(l, m - 1)
right = dfs(m + 1, r)
for lNode in left:
for rNode in right:
new = TreeNode(m)
new.left = lNode
new.right = rNode
arr.append(new)
return arr
res = dfs(1, n)
return [] if res == [None] else res
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
[[1]]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _095_UniqueBinarySearchTree2
{
public IList GenerateTrees(int n)
{
if (n == 0) return new List();

return GenerateTrees(1, n);
}

public IList GenerateTrees(int start, int end)
{
List trees = new List();

if (start > end)
{
trees.Add(null);
return trees;
}

for (int i = start; i <= end; i++)
{
var leftTrees = GenerateTrees(start, i - 1);
var rightTrees = GenerateTrees(i + 1, end);

foreach (var leftTree in leftTrees)
foreach (var rightTree in rightTrees)
{
var current = new TreeNode(i);
current.left = leftTree;
current.right = rightTree;
trees.Add(current);
}
}

return trees;
}
}
}
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
[[1]]