# LeetCode: 95. Unique Binary Search Trees II

**The Problem**

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

N = 3

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

**Constraints:**

`1 <= n <= 8`

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
vector<TreeNode*> generateTrees(int n) {
return createTrees(1, n);
}
vector<TreeNode*> createTrees(int start, int end) {
if (start > end) return { NULL };
else if (start == end) return { new TreeNode(start) };
vector<TreeNode*> result;
for (int i = start; i <= end; ++i) {
vector<TreeNode*> leftSubtrees = createTrees(start, i - 1);
vector<TreeNode*> rightSubtrees = createTrees(i + 1, end);
for (TreeNode* &leftTree : leftSubtrees) {
for (TreeNode* &rightTree : rightSubtrees) {
TreeNode* root = new TreeNode(i);
root->left = leftTree;
root->right = rightTree;
result.push_back(root);
}
}
}
return result;
}
```

Let's break down the code step by step:

1. The primary function `generateTrees(int n)`

is a public function that takes the total number of nodes `n`

as input. It initializes the process by calling the private `createTrees`

function with the range `[1, n]`

and returns the result.

2. The private function `createTrees(int start, int end)`

is the heart of the algorithm. It generates all possible unique BSTs for nodes within the range `[start, end]`

.

- If
`start`

is greater than`end`

, it means there are no nodes in the current range, so it returns a vector with a single element containing`NULL`

to represent an empty tree. - If
`start`

is equal to`end`

, it means there is only one node in the range, and it creates a tree with that single node and returns it as a vector with a single element.

Otherwise, there is more than one node in the range. The code enters a loop from `start`

to `end`

, representing each node as the root of a potential BST.

- It recursively calls
`createTrees`

to generate all possible left subtrees for the current node (nodes less than`i`

) and all possible right subtrees (nodes greater than`i`

). - It then combines each left subtree with each right subtree, attaching the current node as the root, and adds the resulting tree to the
`result`

vector.

3. Finally, the function returns the `result`

vector, which contains all possible BSTs that can be formed using nodes in the range `[start, end]`

.