> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/dynamic-programming/tree-dp/95.-unique-binary-search-trees-ii.md).

# 95. Unique Binary Search Trees II

## Problem Statement

<br>

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

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg)

<pre><code><strong>Input: n = 3
</strong><strong>Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: n = 1
</strong><strong>Output: [[1]]
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= n <= 8`<br>

## Intuition

```

Building all the left subtrees in that range and attaching
Let say 1 3 , It will have all trees possilble  from 1 to 3

This will be attach all the trees between 1 & 3 to left

and so on

We can use DP to memoize but no need as constraints are low
            
```

### Links

<https://leetcode.com/problems/unique-binary-search-trees-ii/description/>

### Video Links

<https://leetcode.com/problems/unique-binary-search-trees-ii/solutions/1849266/c-detailed-explanation-recursive-tree-with-comments/>

### Approach 1:

```
Recursion 
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    vector<TreeNode*> buildTree(int start, int end) {
        vector<TreeNode*> ans;
  
        if(start > end) {
            ans.push_back(NULL);
            return ans;
        }

        for(int i = start; i <= end; ++i) {
            vector<TreeNode*> leftSubTree = buildTree(start, i - 1);
            vector<TreeNode*> rightSubTree = buildTree(i + 1, end);    
            /* 
            Building all the left subtrees in that range and attaching
            Let say 1 3 , It will have all trees possilble  from 1 to 3

            This will be attach all the trees between 1 & 3 to left

            and so on
            */
            for(int j = 0; j < leftSubTree.size(); j++) {
                for(int k = 0; k < rightSubTree.size(); k++) {
                    TreeNode* root = new TreeNode(i);   
                    root->left = leftSubTree[j];   
                    root->right = rightSubTree[k];  
                    ans.push_back(root);    
                }
            }
        }
            
        return ans;
    }
    
    vector<TreeNode*> generateTrees(int n) {
        return buildTree(1, n);
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###