<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:
//method 2
/*
    TreeNode *buildBST(vector<int> &preorder,int preStart,int preEnd,vector<int> &inorder,int inStart,int inEnd,unordered_map<int,int> &mp)
    { if(inStart>inEnd || preStart>preEnd)
      return NULL;

      TreeNode * root=new TreeNode(preorder[preStart]);
      int inRoot=mp[root->val];

      int numsLeft=inRoot-inStart;

      root->left=buildBST(preorder,preStart+1,preStart+numsLeft,inorder,inStart,inRoot-1,mp);

      root->right=buildBST(preorder,preStart+numsLeft+1,preEnd,inorder,inRoot+1,inEnd,mp);

      return root;


    }
    */

    //method 3 function
    TreeNode *build(vector<int> &preorder,int &i,int bound)
    {
        if(i>=preorder.size() || preorder[i]>bound)
        return NULL;

        TreeNode * root=new TreeNode(preorder[i++]);

        root->left=build(preorder,i,root->val);
        root->right=build(preorder,i,bound);

        return root;
    }
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        //method 1: BST ki property hai left < node < right...aur preorder ka pehla element root toh bss simply inn dono property ko follow krte jao..aur pehle element ko root bnane ke baad bbar baar poore tree aur preorder vector ko traverse krke shi position pta krke insert kr do..TC=O(n^2) 

        //method 2: hame pta hiaki bst ka inorder sorted order me hota hai
        //toh bss preorder ko sort kr do hamne inorder mil jayega ..phir same BT waale logic ke hisab se tree bna denge


        //method 3:abb hum kya krenge hrr element ke liye ek upper bound le lenge ki woh element max to max kitna ho skta hai...aur lower bound toh hame hmara upar waala uska parent elemnt hi bta dega....dry run for better understanding


//method 2:
/*
     vector<int> inorder=preorder;

     sort(inorder.begin(),inorder.end());

     unordered_map<int,int> mp;

     for(int i=0;i<inorder.size();i++)
     mp[inorder[i]]=i;
     
     TreeNode * root=buildBST(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1,mp);
    

    return root;

    */


    //method 3: upper bound maintain krke 
    int i=0;
    return build(preorder,i,INT_MAX);
    }
};
16400