<p>Given an array of integers preorder, which represents the <strong>preorder traversal</strong> of a BST (i.e., <strong>binary search tree</strong>), construct the tree and return <em>its root</em>.</p>

<p>It is <strong>guaranteed</strong> that there is always possible to find a binary search tree with the given requirements for the given test cases.</p>

<p>A <strong>binary search tree</strong> is a binary tree where for every node, any descendant of <code>Node.left</code> has a value <strong>strictly less than</strong> <code>Node.val</code>, and any descendant of <code>Node.right</code> has a value <strong>strictly greater than</strong> <code>Node.val</code>.</p>

<p>A <strong>preorder traversal</strong> of a binary tree displays the value of the node first, then traverses <code>Node.left</code>, then traverses <code>Node.right</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/03/06/1266.png" style="height: 386px; width: 590px;" />
<pre>
<strong>Input:</strong> preorder = [8,5,1,7,10,12]
<strong>Output:</strong> [8,5,10,1,7,null,12]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> preorder = [1,3]
<strong>Output:</strong> [1,null,3]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= preorder.length &lt;= 100</code></li>
	<li><code>1 &lt;= preorder[i] &lt;= 1000</code></li>
	<li>All the values of <code>preorder</code> are <strong>unique</strong>.</li>
</ul>

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        TreeNode* root = new TreeNode();
        TreeNode* curr = root;

        if(preorder.empty()){
            return nullptr;
        }

        curr->val = preorder[0];

        int small_index = 1, large_index = 1;
        bool no_small = 1, no_large = 1;
        for(int j = 1; j < preorder.size(); j++){
            if(curr->val > preorder[j]){
                no_small = 0;
            }
            if(curr->val < preorder[j]){
                large_index = j;
                no_large = 0;
                break;
            }
        }
        if(no_large){
            large_index = preorder.size();
        }


        if(!no_small){
            vector<int> temp1;
            temp1.insert(temp1.end(), preorder.begin() + small_index, preorder.begin() + large_index);
            curr->left = bstFromPreorder(temp1);
        }
        else{
            curr->left = nullptr;
        }
        
        if(!no_large){
            vector<int> temp2;
            temp2.insert(temp2.end(), preorder.begin() + large_index, preorder.end());
            curr->right = bstFromPreorder(temp2);    
        }
        else{
            curr->right = nullptr;
        }



        return root;
    }
};  
18200