Problem Statement

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

Problem Link

Unique Binary Search Trees II - LeetCode

Reference Link

Construct all possible BSTs for keys 1 to N - GeeksforGeeks

Approach

The idea is to maintain a list of roots of all BSTs. Recursively construct all possible left and right subtrees. Create a tree for every pair of left and right subtree and add the tree to list. Below is detailed algorithm.

1) Initialize list of BSTs as empty.
2) For every number i where i varies from 1 to N, do following
......a)  Create a new node with key as 'i', let this node be 'node'
......b)  Recursively construct list of all left subtrees.
......c)  Recursively construct list of all right subtrees.
3) Iterate for all left subtrees
   a) For current leftsubtree, iterate for all right subtrees
        Add current left and right subtrees to 'node' and add
        'node' to list.

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        
        return solve(1,n);
    }
    
    vector<TreeNode*> solve(int start,int end) {
        
        vector<TreeNode*> res;
        
        if(start>end)
        {
            res.push_back(NULL);
            
            return res;
        }
        
        for(int i=start;i<=end;i++)
        {
            vector<TreeNode*> lst = solve(start,i-1);
            vector<TreeNode*> rst = solve(i+1,end);
            
            for(int j=0;j<lst.size();j++)
            {
                TreeNode *left = lst[j];
                
                for(int k=0;k<rst.size();k++)
                {
                    TreeNode *right = rst[k];
                    
                    TreeNode *node = new TreeNode(i);
                    node->left = left;
                    node->right = right;
                    res.push_back(node);
                }
            }
        }
        
        return res;
    }
    
    
};