Construct a BST from a Preorder Traversal (3 Methods)

Constructing a Binary Search Tree (BST) from a given preorder traversal is a classic algorithmic problem. Because preorder traversal visits nodes in the exact order of Root -> Left Subtree -> Right Subtree, understanding how to leverage BST properties allows us to reconstruct the tree efficiently without needing a full sorting step or explicit lower/upper bound pairing on both sides.

1. Why Do We Need This? (Problem Statement & Status Quo)

Given an array representing the preorder traversal of a Binary Search Tree (e.g., [8, 5, 1, 7, 10, 12]), our goal is to reconstruct the original BST and return its root node.

• What is a BST? For any given node, every value in its left subtree is strictly smaller than the node's value, and every value in its right subtree is strictly greater.
• What is a Preorder Traversal? The first element is always the root of the tree (or subtree), followed by all elements belonging to its left subtree, followed by all elements belonging to its right subtree.

2. Core Mental Model: The Upper Bound Guard Rail

Real-Life Analogy: The Gatekeeper with a Ceiling Limit

Imagine walking through a warehouse where boxes are arranged by strict rules. You start at the main entrance with an infinite ceiling height (INT_MAX). As you move down into narrower aisles to the left, management imposes a strict new ceiling limit based on the parent box you just passed. You can never store a box that equals or exceeds your current aisle's ceiling limit. If a box violates the rule, you step back out of that aisle and try the right side, where the ceiling limit relaxes back to the parent's upper bound.

Instead of tracking both lower and upper bounds ([lower, upper]) for every recursive call, we only need to track the upper bound. The structural constraints of the preorder traversal and BST property naturally enforce the lower bound.

3. Method 1: The Naive / Brute-Force Approach

In the naive approach, we simulate the standard BST insertion process for every single element in the preorder array, starting from the root.

How It Works

1. Take the first element as the root.
2. For every subsequent element, start at the root and traverse down left or right based on BST comparison rules until you find an empty spot to insert it.

Complexity Analysis

• Time Complexity: $O(N^2)$ in the worst case (e.g., for a skewed tree where every node requires traversing the entire height of the tree).
• Space Complexity: $O(1)$ auxiliary space (ignoring the space required to store the output tree).

4. Method 2: The Sorting Approach (Preorder + Inorder)

A well-known property of Binary Search Trees is that the inorder traversal of a BST is always sorted in ascending order.

Step-by-Step Evolution

1. Take the given preorder traversal array.
2. Sort a copy of this array to obtain the inorder traversal.
3. Use the standard tree-building algorithm that constructs a unique binary tree given its preorder and inorder traversals.

Given Preorder:  [8, 5, 1, 7, 10, 12]
Sorted Inorder:  [1, 5, 7, 8, 10, 12]

Reconstruct unique BST using Preorder + Inorder algorithms.

Complexity Analysis

• Time Complexity: $O(N \log N)$ due to the sorting step, plus $O(N)$ to build the tree, totaling $O(N \log N)$.
• Space Complexity: $O(N)$ auxiliary space required to store the sorted inorder container/array.

5. Method 3: The Optimal $O(N)$ Recursive Approach with Upper Bounds

To achieve optimal linear time complexity $O(N)$, we eliminate sorting and avoid redundant traversals by passing a global index pointer along with an upper bound constraint during recursive DFS construction.

Complete Flow Walkthrough

Let's trace the optimal method with preorder [8, 5, 1, 7, 10, 12]:

1. build(vector& A, int &i, int bound) is called with i = 0 and bound = INT_MAX.
2. A[0] = 8. Since 8 < INT_MAX, create root node 8. Increment i (i = 1).
3. Go Left: build(A, i, 8)
   • A[1] = 5. Since 5 < 8, create node 5. Increment i (i = 2).
   • Go Left: build(A, i, 5)
     • A[2] = 1. Since 1 < 5, create node 1. Increment i (i = 3).
     • Go Left: build(A, i, 1)
       • A[3] = 7. Since 7 < 1 is false, return NULL.
     • Go Right: build(A, i, 5) (bound restored to parent 5)
       • A[3] = 7. Since 7 < 5 is false, return NULL.
   • Go Right: build(A, i, 8) (bound restored to parent 8)
     • A[3] = 7. Since 7 < 8, create node 7. Increment i (i = 4).
     • Go Left: build(A, i, 7) -> A[4] = 10 (10 < 7 false -> NULL)
     • Go Right: build(A, i, 8) -> A[4] = 10 (10 < 8 false -> NULL)
4. Go Right of Root (8): build(A, i, INT_MAX)
   • A[4] = 10 -> creates node 10. Increment i (i = 5).
   • Go Left: build(A, i, 10) -> A[5] = 12 (12 < 10 false -> NULL)
   • Go Right: build(A, i, INT_MAX) -> A[5] = 12 -> creates node 12. Increment i (i = 6).

6. Method Comparison Summary

7. Production-Ready Implementation (C++ & Java)

C++ Implementation

#include <vector>
#include <climits>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    TreeNode* build(const std::vector<int>& preorder, int& i, int bound) {
        // Base case: if we have processed all elements or current element exceeds upper bound
        if (i == preorder.size() || preorder[i] > bound) {
            return nullptr;
        }
        
        // Create root node from current preorder index
        TreeNode* root = new TreeNode(preorder[i++]);
        
        // Left child's upper bound becomes the current node's value
        root->left = build(preorder, i, root->val);
        
        // Right child retains the parent's upper bound
        root->right = build(preorder, i, bound);
        
        return root;
    }

public:
    TreeNode* bstFromPreorder(const std::vector<int>& preorder) {
        int i = 0;
        return build(preorder, i, INT_MAX);
    }
};

Java Implementation

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        // Java passes primitives by value, so we wrap index 'i' in a 1-element array
        int[] i = new int[]{0};
        return build(preorder, i, Integer.MAX_VALUE);
    }

    private TreeNode build(int[] preorder, int[] i, int bound) {
        // Base case: out of bounds or violates upper bound
        if (i[0] == preorder.length || preorder[i[0]] > bound) {
            return null;
        }

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

        // Left child bound is current node's value
        root.left = build(preorder, i, root.val);

        // Right child inherits parent's bound
        root.right = build(preorder, i, bound);

        return root;
    }
}

8. Summary and Key Takeaways

• Preorder Characteristics: Preorder traversal guarantees that the first element encountered is always the root of the current subtree (Root -> Left -> Right).
• Eliminating Lower Bounds: By passing a strict upper bound (bound) during recursive calls, we implicitly validate whether an element belongs to the left or right subtree without needing a separate lower bound parameter.
• Index Tracking by Reference: In languages like C++, pass the array pointer/index by reference (int &i). In Java, use a single-element wrapper array (int[] i = new int[1]) to emulate pass-by-reference state persistence across recursive stack frames.
• Optimal Efficiency: The optimal recursive approach visits each node a constant number of times, achieving an optimal $O(N)$ time complexity.
• Space Complexity: The auxiliary space is proportional to the height of the tree ($O(H)$) due to recursive call stack frames, which drops to $O(\log N)$ for balanced trees and $O(N)$ for skewed trees.