## Algorithm

Problem Name: 1008. Construct Binary Search Tree from Preorder Traversal

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

Example 1:

```Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
```

Example 2:

```Input: preorder = [1,3]
Output: [1,null,3]
```

Constraints:

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
struct TreeNode* bstFromPreorder(int* preorder, int preorderSize) {
struct TreeNode *node;
int mid;

if (preorderSize == 0) return NULL;

node = malloc(sizeof(struct TreeNode));
//assert(node);
node->val = preorder[0];

mid = 1;
while (mid < preorderSize && preorder[mid] < node->val) {
mid ++;
}
node->left = bstFromPreorder(&preorder[1], mid - 1);
node->right = bstFromPreorder(&preorder[mid], preorderSize - mid);

return node;
}
``````
Copy The Code &

Input

cmd
preorder = [8,5,1,7,10,12]

Output

cmd
[8,5,10,1,7,null,12]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public TreeNode bstFromPreorder(int[] preorder) {
if (preorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(preorder[0]);
Stack stack = new Stack<>();
stack.push(root);
for (int i = 1; i < preorder.length; i++) {
TreeNode node = stack.peek();
TreeNode child = new TreeNode(preorder[i]);
while (!stack.isEmpty() && stack.peek().val < child.val) {
node = stack.pop();
}
if (node.val < child.val) {
node.right = child;
} else {
node.left = child;
}
stack.push(child);
}
return root;
}
}
``````
Copy The Code &

Input

cmd
preorder = [8,5,1,7,10,12]

Output

cmd
[8,5,10,1,7,null,12]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
const bstFromPreorder = function(preorder) {
let i = 0;
return bstFromPreorder(preorder, Number.MAX_VALUE);
function bstFromPreorder(A, bound) {
if (i === A.length || A[i] > bound) return null;
let root = new TreeNode(A[i++]);
root.left = bstFromPreorder(A, root.val);
root.right = bstFromPreorder(A, bound);
return root;
}
};
``````
Copy The Code &

Input

cmd
preorder = [1,3]

Output

cmd
[1,null,3]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _1008_ConstructBinarySearchTreeFromPreorderTraversal
{
private int[] preorder;
private int index;

public TreeNode BstFromPreorder(int[] preorder)
{
this.preorder = preorder;
index = 0;

return Build(int.MinValue, int.MaxValue);
}

private TreeNode Build(int minValue, int maxValue)
{
if (index >= preorder.Length) return null;

var value = preorder[index];
if (value < minValue || value > maxValue)
return null;

var root = new TreeNode(value);
index++;

root.left = Build(minValue, value);
root.right = Build(value, maxValue);

return root;
}
}
}
``````
Copy The Code &

Input

cmd
preorder = [1,3]

Output

cmd
[1,null,3]