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:

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)

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