Construct Binary Search Tree from Preorder Traversal

Description

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.

Recursive Upper Bound DFS ($O(N)$ Time, $O(H)$ Space)

Intuition

Since every node in a BST enforces an upper bound limit on its left subtree:

1. Maintain a global index pointer traversing preorder left-to-right.
2. Pass an upperBound parameter to recursive calls (initialized to Integer.MAX_VALUE for the root).
3. At each step, if index reaches the end of the array OR preorder[index] > upperBound, the current node cannot belong to this subtree, so return null.
4. Construct the root node: TreeNode root = new TreeNode(preorder[index++]).
5. Recursively construct:
   • Left Subtree: Values must be smaller than root.val $\to$ set upperBound = root.val.
   • Right Subtree: Values must be smaller than the current parent’s upperBound $\to$ keep upperBound.

class Solution {
    private int index = 0;
 
    public TreeNode bstFromPreorder(int[] preorder) {
        return build(preorder, Integer.MAX_VALUE);
    }
 
    private TreeNode build(int[] preorder, int bound) {
        if (index == preorder.length || preorder[index] > bound) {
            return null;
        }
 
        TreeNode root = new TreeNode(preorder[index++]);
 
        // Left subtree elements must be < root.val
        root.left = build(preorder, root.val);
 
        // Right subtree elements must be < parent's upper bound
        root.right = build(preorder, bound);
 
        return root;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Every element in preorder is processed exactly once in $O(1)$ time.
• Space Complexity: $O(H)$ — Recursion call stack depth bounded by tree height $H$ ($O(\log N)$ for balanced, $O(N)$ for skewed).

---

Key Interview Talking Point

• Why not use binary search to split left/right subtrees? Finding the split point with binary search takes $O(\log N)$ per node, leading to $O(N\log N)$ total time (or $O(N^2)$ in skewed trees).
• The Upper Bound approach achieves optimal $O(N)$ time by implicitly determining subtrees in a single linear pass.

---

Easy Memory Rule

“Track index globally $\to$ Pass root.val as upper bound for Left Subtree $\to$ Keep original upper bound for Right Subtree!”