```
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
using namespace std;
// node structure
struct node
{
int key;
struct node *left, *right;
};
map<int, int> mp;
// A utility function to create a new BST node
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to do preorder traversal of BST
void preorder(struct node *root)
{
if (root != NULL)
{
printf("%d ", mp[root->key]); // remapping while printing
preorder(root->left);
preorder(root->right);
}
}
// A utility function to do preorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", mp[root->key]); // remapping while printing
inorder(root->right);
}
}
// function for constructing trees
vector<struct node *> constructTrees(int start, int end)
{
vector<struct node *> list;
/* if start > end then subtree will be empty so returning NULL in the list */
if (start > end)
{
list.push_back(NULL);
return list;
}
/* iterating through all values from start to end for constructing left and right subtree recursively */
for (int i = start; i <= end; i++)
{
/* constructing left subtree */
vector<struct node *> leftSubtree = constructTrees(start, i - 1);
/* constructing right subtree */
vector<struct node *> rightSubtree = constructTrees(i + 1, end);
/* now looping through all left and right subtrees and connecting them to ith root below */
for (int j = 0; j < leftSubtree.size(); j++)
{
struct node* left = leftSubtree[j];
for (int k = 0; k < rightSubtree.size(); k++)
{
struct node * right = rightSubtree[k];
struct node * node = newNode(i); // making value i as root
node->left = left; // connecting left subtree
node->right = right; // connecting right subtree
list.push_back(node); // adding this tree to list
}
}
}
return list;
}
// Driver Program to test above functions
int main()
{
int in[] = {4, 5, 7, 8, 10};
int N = sizeof(in) / sizeof(int);
for(int i = 1; i <= N; i++)
mp[i] = in[i - 1]; // mapping all numbers from 1 to N for simplicity
vector<struct node *> totalTreesFrom1toN = constructTrees(1, N);
/* printing preorder of all BSTs */
for (int i = 0; i < totalTreesFrom1toN.size(); i++)
{
preorder(totalTreesFrom1toN[i]);
printf("\n");
}
return 0;
}
```