Skip to content

BST from Preorder

Why BSTs Need Only One Traversal

In Lesson 1, you needed two traversals to reconstruct a general binary tree. BSTs are different. You only need one.

Why? Because the BST property — left subtree values \(<\) root \(<\) right subtree values — acts as the second traversal. Given a preorder sequence of a BST, the BST property tells you exactly which elements belong to the left subtree (all values less than the root) and which belong to the right (all values greater). That's the same information inorder would have given you.

A BST's structure is fully determined by the insertion order of its values. Preorder IS the insertion order.

Problem (LC 1008)

Given: A preorder traversal of a BST. All values are unique. Reconstruct the BST.

Input: [8, 5, 1, 7, 10, 12]

Expected tree:

        8
       / \
      5   10
     / \    \
    1   7    12

Verify: preorder of this tree = [8, 5, 1, 7, 10, 12]. Correct.

The Naive \(O(n^2)\) Approach

For each element in preorder, insert it into the BST one at a time using standard BST insertion (walk down from root, go left if smaller, right if larger).

This works but takes \(O(n^2)\) in the worst case (when the preorder is sorted — the BST becomes a chain, and each insertion walks the entire chain).

The \(O(n)\) Recursive Approach: Upper Bound

Here's the idea. Read preorder left to right using an index. Each recursive call is responsible for building a subtree where all values must be less than some upperBound.

  • The root of the whole tree has upperBound = infinity.
  • When building the left subtree of a node with value \(v\), the upper bound is \(v\) (everything in the left subtree must be \(< v\)).
  • When building the right subtree, the upper bound is the parent's upper bound (everything in the right subtree must be \(<\) the grandparent's value).

If the next value in preorder exceeds the upper bound, this subtree is done — return nullptr.

Upper bound narrows as recursion descends, constraining valid BST values

Full Trace

Preorder: [8, 5, 1, 7, 10, 12]. Starting with upperBound = 2e9.

Step Index Value Upper Bound Action Tree State
1 0 8 2e9 Create node 8, build left with bound 8 8
2 1 5 8 \(5 < 8\) → create node 5, build left with bound 5 8→L:5
3 2 1 5 \(1 < 5\) → create node 1, build left with bound 1 8→L:5→L:1
4 3 7 1 \(7 > 1\) → return nullptr (left of 1 done) —
4b 3 7 1 \(7 > 1\) → return nullptr (right of 1 done) —
5 3 7 5 Back to right of 5. \(7 > 5\) → return nullptr? No — bound is 8 —

Wait, let me re-trace more carefully. After building node 1, we try to build 1's left and right subtrees. Both fail because \(7 > 1\). We return to node 5 and build its right subtree with upper bound 8.

Step Index Value Upper Bound Action
1 0 8 2e9 Create 8. Left subtree: bound = 8.
2 1 5 8 \(5 < 8\) → create 5. Left: bound = 5.
3 2 1 5 \(1 < 5\) → create 1. Left: bound = 1.
4 3 7 1 \(7 > 1\) → nullptr. Right of 1: bound = 5.
5 3 7 5 \(7 > 5\) → nullptr. Back to right of 5: bound = 8.
6 3 7 8 \(7 < 8\) → create 7. Left: bound = 7.
7 4 10 7 \(10 > 7\) → nullptr. Right of 7: bound = 8.
8 4 10 8 \(10 > 8\) → nullptr. Back to right of 8: bound = 2e9.
9 4 10 2e9 \(10 < 2e9\) → create 10. Left: bound = 10.
10 5 12 10 \(12 > 10\) → nullptr. Right of 10: bound = 2e9.
11 5 12 2e9 \(12 < 2e9\) → create 12. Left/right: nullptr.

Final tree:

        8
       / \
      5   10
     / \    \
    1   7    12

Each value is consumed exactly once. Total: \(O(n)\).

The Code

TreeNode* buildBST(vector<int>& preorder, int& index, int upperBound) {
    if (index >= (int)preorder.size() || preorder[index] > upperBound) {
        return nullptr;
    }
    TreeNode* node = new TreeNode(preorder[index++]);
    node->left = buildBST(preorder, index, node->val);
    node->right = buildBST(preorder, index, upperBound);
    return node;
}

TreeNode* bstFromPreorder(vector<int>& preorder) {
    int index = 0;
    return buildBST(preorder, index, 2e9);
}

Complexity: \(O(n)\) time, \(O(h)\) space.

The Monotonic Stack Approach

There's an iterative \(O(n)\) approach using a stack, and it connects to a pattern you may have seen before.

The stack maintains the rightmost path of the tree built so far — the path from the root down through right children. If you've studied Chapter 1 Lesson 2, you'll recall that the call stack during tree traversal IS the rightmost path being explored.

Algorithm:

For each new value in preorder:

  • If it's less than the stack's top, it's the left child of the top.
  • If it's greater than the stack's top, pop nodes until you find one with a greater value (or the stack is empty). The new node is the right child of the last popped node.

Push the new node onto the stack.

Monotonic stack maintains the rightmost path during BST construction

Full Stack Trace

Preorder: [8, 5, 1, 7, 10, 12]

Step Value Stack Before Comparison Action Stack After
1 8 [] — Create root 8, push [8]
2 5 [8] \(5 < 8\) Left child of 8 [8, 5]
3 1 [8, 5] \(1 < 5\) Left child of 5 [8, 5, 1]
4 7 [8, 5, 1] \(7 > 1\): pop 1; \(7 > 5\): pop 5; \(7 < 8\): stop Right child of 5 (last popped) [8, 7]
5 10 [8, 7] \(10 > 7\): pop 7; \(10 > 8\): pop 8; stack empty: stop Right child of 8 (last popped) [10]
6 12 [10] \(12 > 10\): pop 10; stack empty: stop Right child of 10 (last popped) [12]

The stack always holds the rightmost path. When a new value is larger than the top, it "closes off" nodes on the rightmost path — those nodes will never get a right child from future values. The new node becomes the right child of the deepest node it surpassed.

This is a monotonic stack — the same structure used in "next greater element" problems. If you've taken the monotonic stack course, this connection should feel familiar.

The Code

TreeNode* bstFromPreorderStack(vector<int>& preorder) {
    TreeNode* root = new TreeNode(preorder[0]);
    stack<TreeNode*> rightmostPath;
    rightmostPath.push(root);

    for (int i = 1; i < (int)preorder.size(); i++) {
        TreeNode* newNode = new TreeNode(preorder[i]);
        if (preorder[i] < rightmostPath.top()->val) {
            rightmostPath.top()->left = newNode;
        } else {
            TreeNode* parent = nullptr;
            while (!rightmostPath.empty() && preorder[i] > rightmostPath.top()->val) {
                parent = rightmostPath.top();
                rightmostPath.pop();
            }
            parent->right = newNode;
        }
        rightmostPath.push(newNode);
    }
    return root;
}

Complexity: \(O(n)\) time (each node is pushed and popped at most once), \(O(n)\) space.

Three Approaches Compared

Approach Time Space Key Idea
Naive insertion \(O(n^2)\) worst \(O(h)\) Insert one-by-one into BST
Upper-bound recursion \(O(n)\) \(O(h)\) BST property constrains valid range
Monotonic stack \(O(n)\) \(O(n)\) Stack = rightmost path being built

The upper-bound approach is the cleanest for interviews — three lines of logic. The stack approach is worth knowing because it reveals the connection between BST construction and monotonic stacks.

Try It

The starter code has a bstFromPreorder function with a TODO. Implement the upper-bound recursive approach.

Input: [8, 5, 1, 7, 10, 12]
Output (inorder): 1 5 7 8 10 12

Predict before running: What does the inorder traversal of the reconstructed BST look like? It should be the preorder values sorted — because inorder of any BST gives sorted output. Here: [1, 5, 7, 8, 10, 12].

Challenge: What if preorder = [5, 4, 3, 2, 1]? That's a left-skewed BST. The upper-bound approach creates node 5, then builds a left subtree with bound 5. Each subsequent value is smaller, so each becomes the left child of the previous. The recursion depth is \(n\). Works correctly, just uses \(O(n)\) stack space.

Edge Cases to Watch For

  • Upper bound set too low: Using INT_MAX as the initial upper bound fails if the preorder contains INT_MAX itself (since the check is preorder[index] > upperBound with strict inequality). Use a larger sentinel like 2e9 or LLONG_MAX.
  • Invalid preorder (not from a BST): The algorithm assumes the input is a valid BST preorder. If it isn't (e.g., [2, 3, 1] which can't come from any BST), the result is undefined — not all elements may be consumed, and the tree structure will be wrong.

Problems

Problem Link Difficulty
LC 1008 — Construct Binary Search Tree from Preorder Traversal leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal Medium
LC 108 — Convert Sorted Array to Binary Search Tree leetcode.com/problems/convert-sorted-array-to-binary-search-tree Easy
LC 1382 — Balance a Binary Search Tree leetcode.com/problems/balance-a-binary-search-tree Medium