#include <bits/stdc++.h>
using namespace std;

// tree node is defined
class TreeNode
{
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        val = data;
        left = NULL;
        right = NULL;
    }
};

// inorder traversal for tree
void inorder(TreeNode *root)
{

    if (!root)
        return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

// to find next greater element of the root in the range in O(logn) time
// this will find the starting index of the right subtree if exists
int FindNextGreater(vector<int> &preorder, int l, int r, int key)
{
    int index = r + 1;
    while (l <= r)
    {
        int mid = l + (r - l) / 2;
        if (preorder[mid] > key)
        {
            index = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }

    return index;
}

// recursively Constructing the BST
TreeNode *bstFromPreorderRecur(vector<int> &preorder, int l, int r)
{
    // base case for returning NULL
    if (l > r)
        return NULL;
    // base case for leaf nodes
    if (l == r)
    {
        return new TreeNode(preorder[l]);
    }
    // building the tree
    TreeNode *root = new TreeNode(preorder[l]);
    // starting index of right subtree
    int m = FindNextGreater(preorder, l + 1, r, preorder[l]);
    // building the left subtree recursively
    root->left = bstFromPreorderRecur(preorder, l + 1, m - 1);
    // building the right subtree recursively
    root->right = bstFromPreorderRecur(preorder, m, r);

    return root;
}
// constructing the BST
TreeNode *bstFromPreorder(vector<int> &preorder)
{
    return bstFromPreorderRecur(preorder, 0, preorder.size() - 1);
}

// main function
int main()
{
    vector<int> preorder{8, 5, 1, 7, 10, 12};

    TreeNode *root = bstFromPreorder(preorder);
    cout << "Tree constructed\n";

    cout << "Inorder traversal of the constructed BST is:\n";
    inorder(root);
    cout << endl;

    return 0;
}

Output 


Tree constructed
Inorder traversal of the constructed BST is:
1 5 7 8 10 12