# 1008. Construct Binary Search Tree from Preorder Traversal

## Problem Statement

<br>

Given an array of integers preorder, which represents the **preorder traversal** of a BST (i.e., **binary search tree**), construct the tree and return *its root*.

It is **guaranteed** that there is always possible to find a binary search tree with the given requirements for the given test cases.

A **binary search tree** is a binary tree where for every node, any descendant of `Node.left` has a value **strictly less than** `Node.val`, and any descendant of `Node.right` has a value **strictly greater than** `Node.val`.

A **preorder traversal** of a binary tree displays the value of the node first, then traverses `Node.left`, then traverses `Node.right`.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2019/03/06/1266.png)

<pre><code><strong>Input: preorder = [8,5,1,7,10,12]
</strong><strong>Output: [8,5,10,1,7,null,12]
</strong></code></pre>

**Example 2:**

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

&#x20;

**Constraints:**

* `1 <= preorder.length <= 100`
* `1 <= preorder[i] <= 1000`
* All the values of `preorder` are **unique**.

## Intuition

```
Make an inorder, as BST so sorted of preorder

And apply the same concept of construction. By recursively building the tree

```

### Links

<https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/>

### Video Links

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    unordered_map<int, int> mp;
    TreeNode* Tree(vector<int>& preorder, int p_start, int p_end, vector<int>& inorder, int in_start, int in_end){
        if(in_start > in_end)
            return nullptr;

        TreeNode* root = new TreeNode(preorder[p_start]);
        int index = mp[preorder[p_start]];
        int diff = index - in_start;

        root->left = Tree(preorder, p_start+1, p_start+diff, inorder, in_start, index-1);
        root->right = Tree(preorder, p_start+diff+1, p_end, inorder, index+1, in_end);

        return root;
    }

    TreeNode* bstFromPreorder(vector<int>& preorder) {
        vector<int> inorder(preorder);
        sort(inorder.begin(), inorder.end());

        for(int i=0;i<inorder.size(); i++)
            mp[inorder[i]] = i;
    
        return Tree(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###