# Construct Binary Search Tree from Preorder Traversal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal)
Canonical: https://scaleengineer.com/dsa/problems/construct-binary-search-tree-from-preorder-traversal
**Data structures:** Array, Stack, Monotonic Stack, Tree, Binary Tree, Binary Search Tree
**Companies:** [Akamai](https://scaleengineer.com/companies/akamai)
---
## Problem
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:**

![](https://assets.glich.co/dsa/construct-binary-search-tree-from-preorder-traversal/image0.png) 

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

# Approaches
## Brute-Force Recursion
This approach directly translates the properties of a preorder traversal of a BST into a recursive algorithm. The first element of the preorder array is the root. The subsequent elements are then partitioned into two groups: those smaller than the root (for the left subtree) and those larger than the root (for the right subtree). The algorithm finds this partition point and recursively constructs the left and right subtrees.
**Time:** O(N^2) in the worst case. For a skewed tree (e.g., `[5, 4, 3, 2, 1]`), each call to `build` might scan almost the entire remaining array to find the split point. · **Space:** O(N) in the worst case for the recursion stack. If the tree is skewed, the recursion depth can go up to N.
**Pros:** The logic is straightforward and easy to understand as it directly models the definition of preorder traversal in a BST.
**Cons:** The time complexity is quadratic, which is inefficient for large inputs.; For each node, it re-scans a portion of the array, leading to redundant work.
### Explanation
The implementation uses a recursive helper function that operates on a specific range of the `preorder` array, defined by `start` and `end` indices. For each recursive call, the first element `preorder[start]` is taken as the root. Then, a linear scan is performed on the rest of the range `[start + 1, end]` to find the boundary between the left and right subtrees. This boundary is the first element that is larger than the root's value. Once found, two more recursive calls are made for the left and right sub-ranges.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        return build(preorder, 0, preorder.length - 1);
    }

    private TreeNode build(int[] preorder, int start, int end) {
        if (start > end) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[start]);
        
        int splitIndex = start + 1;
        while (splitIndex <= end && preorder[splitIndex] < root.val) {
            splitIndex++;
        }
        
        root.left = build(preorder, start + 1, splitIndex - 1);
        root.right = build(preorder, splitIndex, end);
        
        return root;
    }
}
```
### Algorithm
- The core idea is to use recursion. The first element in any preorder traversal sequence is the root of the tree/subtree.
- Create a recursive function, say `build(preorder, start, end)`, which constructs a BST from the subarray `preorder[start...end]`.
- The base case for the recursion is when `start > end`, which means the subarray is empty, so we return `null`.
- In the recursive step, create a new `TreeNode` with the value `preorder[start]`. This is the root of the current subtree.
- Iterate from `start + 1` to `end` to find the index of the first element that is greater than `root.val`. Let's call this `splitIndex`.
- All elements from `start + 1` to `splitIndex - 1` belong to the left subtree.
- All elements from `splitIndex` to `end` belong to the right subtree.
- Make a recursive call to build the left subtree: `root.left = build(preorder, start + 1, splitIndex - 1)`.
- Make another recursive call to build the right subtree: `root.right = build(preorder, splitIndex, end)`.
- Return the `root`.

## Iterative Construction with a Stack
An iterative approach can be used to construct the BST, which avoids recursion and has linear time complexity. This method uses a stack to maintain the chain of parent nodes. As we iterate through the preorder traversal, we determine whether the current element is a left or right child of a node already in the tree by comparing its value with the nodes in the stack.
**Time:** O(N). Each element of the `preorder` array is processed once, and each node is pushed and popped from the stack at most once. · **Space:** O(N) for the stack. In the worst case of a skewed tree, the stack might hold all N nodes.
**Pros:** Achieves optimal O(N) time complexity.; Iterative solution avoids potential stack overflow issues with very deep trees (though not a concern with the given constraints).
**Cons:** The logic can be less intuitive to follow compared to the recursive approaches.
### Explanation
We start by creating the root from `preorder[0]` and pushing it to a stack. Then, we iterate through the rest of the `preorder` array. For each new value, we create a node. We check the node at the top of the stack. If the new node's value is smaller, it's a left child. If it's larger, we pop from the stack until we find a node that is a suitable parent (i.e., the new node's value is smaller than the node at the top of the stack, or the stack becomes empty). The last popped node becomes the parent, and the new node is its right child. Finally, the new node is pushed onto the stack to extend the current path.

```java
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        for (int i = 1; i < preorder.length; i++) {
            TreeNode node = new TreeNode(preorder[i]);
            TreeNode parent = stack.peek();
            
            if (node.val < parent.val) {
                parent.left = node;
            } else {
                while (!stack.isEmpty() && node.val > stack.peek().val) {
                    parent = stack.pop();
                }
                parent.right = node;
            }
            stack.push(node);
        }
        return root;
    }
}
```
### Algorithm
- Initialize the `root` of the tree with the first element of `preorder`.
- Use a `Stack` to keep track of the path of ancestors. Push the `root` onto the stack.
- Iterate through the `preorder` array from the second element (`i = 1`).
- For each element `preorder[i]`, create a new `child` node.
- Let `parent` be the node at the top of the stack.
- If `child.val < parent.val`, the `child` is the left child of `parent`. So, set `parent.left = child`.
- If `child.val > parent.val`, the `child` is the right child of some ancestor. We need to find the correct parent by popping from the stack. Pop nodes as long as the stack is not empty and `child.val` is greater than the value of the node at the top of the stack. The last node that was at the top of the stack before the condition failed (or the last node popped) is the parent. Set `parent.right = child`.
- After placing the `child`, push it onto the stack.
- After the loop finishes, return the `root`.

## Optimal Recursive Construction with Bounds
This is a highly efficient recursive approach that constructs the tree in a single pass. It cleverly uses lower and upper bounds to determine where each node should be placed in the tree. By passing these bounds down the recursion, it avoids the need to re-scan the array to find subtree boundaries, leading to a linear time complexity.
**Time:** O(N). The `preorder` array is traversed only once. Each element results in a single node creation and two recursive calls. · **Space:** O(N) for the recursion stack. The depth of the recursion can be up to N for a skewed tree.
**Pros:** Optimal O(N) time complexity as it processes each element once.; The code is concise and elegant.; Conceptually clean way to enforce the BST property during construction.
**Cons:** Relies on a shared index (e.g., a member variable), which can be considered less clean than a purely functional approach.; Being recursive, it could theoretically lead to stack overflow on extremely deep trees, although this is not an issue with the problem's constraints.
### Explanation
The core of this method is a recursive function that builds the tree while respecting the BST property. We maintain a global index for the `preorder` array. The recursive function is given a `lower` and `upper` bound for the values of nodes it can create. When we process an element from `preorder`, we check if it falls within the current bounds. If it does, we create a node, advance the index, and then make two recursive calls for the left and right children, updating the bounds accordingly. For the left child, the new upper bound is the parent's value. For the right child, the new lower bound is the parent's value. If an element doesn't fit the bounds, we know that branch of the tree is empty, and we return `null`.

```java
class Solution {
    private int preorderIndex = 0;
    private int[] preorder;

    public TreeNode bstFromPreorder(int[] preorder) {
        this.preorder = preorder;
        return build(Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private TreeNode build(int lower, int upper) {
        if (preorderIndex == preorder.length) {
            return null;
        }

        int val = preorder[preorderIndex];
        if (val < lower || val > upper) {
            return null;
        }

        preorderIndex++;
        TreeNode root = new TreeNode(val);
        root.left = build(lower, val);
        root.right = build(val, upper);
        return root;
    }
}
```
### Algorithm
- Use a global index `preorderIndex` to track the current element in the `preorder` array.
- Define a recursive helper function `build(lower, upper)` that constructs a subtree whose nodes must have values within the range `(lower, upper)`.
- The initial call is `build(Integer.MIN_VALUE, Integer.MAX_VALUE)`.
- Inside `build(lower, upper)`:
  - If `preorderIndex` is at the end of the array, return `null`.
  - Get the current value `val = preorder[preorderIndex]`.
  - If `val` is not within the `(lower, upper)` bounds, it doesn't belong in this subtree, so return `null`.
  - If the value is valid, increment `preorderIndex`.
  - Create a new `TreeNode` with `val`. This is the `root` of the current subtree.
  - Recursively build the left subtree by calling `build(lower, val)`. The upper bound for the left child is the parent's value.
  - Recursively build the right subtree by calling `build(val, upper)`. The lower bound for the right child is the parent's value.
  - Return the `root`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode bstFromPreorder ( int [] preorder ) { return dfs ( preorder , 0 , preorder . length - 1 ); } private TreeNode dfs ( int [] preorder , int i , int j ) { if ( i > j || i >= preorder . length ) { return null ; } TreeNode root = new TreeNode ( preorder [ i ]); int left = i + 1 , right = j + 1 ; while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( preorder [ mid ] > preorder [ i ]) { right = mid ; } else { left = mid + 1 ; } } root . left = dfs ( preorder , i + 1 , left - 1 ); root . right = dfs ( preorder , left , j ); return root ; } }
```

### CPP

```cpp
/** * 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: TreeNode * bstFromPreorder ( vector < int >& preorder ) { return dfs ( preorder , 0 , preorder . size () - 1 ); } TreeNode * dfs ( vector < int >& preorder , int i , int j ) { if ( i > j || i >= preorder . size ()) return nullptr ; TreeNode * root = new TreeNode ( preorder [ i ]); int left = i + 1 , right = j + 1 ; while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( preorder [ mid ] > preorder [ i ]) right = mid ; else left = mid + 1 ; } root -> left = dfs ( preorder , i + 1 , left - 1 ); root -> right = dfs ( preorder , left , j ); return root ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def bstFromPreorder ( self , preorder : List [ int ]) -> Optional [ TreeNode ]: def dfs ( preorder ): if not preorder : return None root = TreeNode ( preorder [ 0 ]) left , right = 1 , len ( preorder ) while left < right : mid = ( left + right ) >> 1 if preorder [ mid ] > preorder [ 0 ]: right = mid else : left = mid + 1 root . left = dfs ( preorder [ 1 : left ]) root . right = dfs ( preorder [ left :]) return root return dfs ( preorder )
```