<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>

/**
 * 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:
     // time : O(n * n) worst case, O(n log n) average case. For each node (n), 
    // we search for the split point (log n average, n worst case).
    // Memory: O(n) worst case, O(h) average case for the stack, where h is the height of the tree.
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        return util(preorder,0,0);
    }
    
    TreeNode* util(vector<int>&p, int first=0, int last=0){
        
        if(last==0) last=p.size();
        if(first==last) return nullptr;
        
        // find the first element greater than root to divide the array into lst and rst
        auto split = find_if(begin(p)+first,begin(p)+last,[&](int value){return value > p[first];});
        auto root = new TreeNode(p[first]);
        root->left = util(p,first+1,split-begin(p));
        root->right = util(p,split-begin(p),last);
        
        return root;
    }
    
    // O(n) solution 
    // pass the parent value for left sub tree
    //and keep building left sub tree until array value exceeds parent value.
   /* int idx = 0;
    TreeNode* bstFromPreorder(vector<int>& preorder){ 
        return util(preorder,INT_MAX);
    }
    
    TreeNode* util(vector<int>& p,int parent=INT_MAX){
        cout<<"idx="<<idx<<" "<<"parent="<<parent<<endl;
        if(idx >= p.size() || p[idx] > parent) //no ryt subtree or right subtree start
            return nullptr;                    // indicates no node of left sub tre 
        
        auto root = new TreeNode(p[idx++]);
        root->left = util(p,root->val);
        root->right = util(p,parent);  //for right sub tree, passing predessor parent
        
        return root;
    }*/
};
17000