# 16. 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:**

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

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

## Solution: (Recursion)

**Approach:**\
**Building BST for each n(1 - n)**

```cpp
class Solution
{
public:
    vector<TreeNode *> generateBST(int start, int end)
    {

        vector<TreeNode *> v;
        if (start > end)
        {
            v.push_back(NULL);
            return v;
        }

        if (start == end)
        {
            TreeNode *t = new TreeNode(start);
            v.push_back(t);
            return v;
        }

        for (int i = start; i <= end; i++)
        {

            vector<TreeNode *> lt = generateBST(start, i - 1);
            vector<TreeNode *> rt = generateBST(i + 1, end);

            for (int k = 0; k < lt.size(); k++)
            {
                for (int j = 0; j < rt.size(); j++)
                {

                    TreeNode *t = new TreeNode(i);
                    t->left = lt[k];
                    t->right = rt[j];

                    v.push_back(t);
                }
            }
        }

        return v;
    }
    
    vector<TreeNode *> generateTrees(int n)
    {

        vector<TreeNode *> res = generateBST(1, n);
        return res;
    }
};
```

**Time Complexity: (2^n)**\
**Maps can be used to optimize**