Medium

Construct Binary Search Tree from Preorder Traversal

A medium BST interview guide. Task statement, worked examples, intuition, and step-by-step solutions.

Topic: BST
Sheets: 1
Core for: 2 roles

The problem

Given an integer array representing the preorder traversal of a binary search tree, construct and return the BST. Each element in preorder appears in the order they would be visited in a preorder traversal.

Example 1

Input: preorder=[6,3,2,5,8,7,9]
Output: [6,3,8,2,5,7,9]
Why: 6 is root, 3,2,5 go left (3 left of 6, 2 left of 3, 5 right of 3), 8,7,9 go right (8 right of 6, 7 left of 8, 9 right of 8).

Example 2

Input: preorder=[1,2,3]
Output: [1,null,2,null,3]
Why: Elements are in ascending order, forming a right-skewed tree.

Example 3

Input: preorder=[3,2,1]
Output: [3,2,null,1]
Why: Elements are in descending order, forming a left-skewed tree.

Constraints

1 <= preorder.length <= 100
1 <= preorder[i] <= 104
All values in preorder are unique.

How to think about it

Updated 2026-09-29

In preorder, the first element is always the current root. All subsequent elements smaller than the root belong to its left subtree, and all elements larger belong to its right subtree. Instead of scanning for that partition point at each level, pass an upper bound constraint: a node consumes the next preorder token if and only if it is smaller than its inherited upper bound.

Approaches, worst first

Sort preorder to obtain inorder
time O(n log n) · space O(n)
Sort the preorder array to get the tree's inorder sequence, then construct the binary tree using the standard preorder-and-inorder reconstruction algorithm. Works correctly but incurs sorting overhead and hash map lookups.
Recursive partitioning
time O(n^2) · space O(n)
Take the first element as root, scan linearly for the first element greater than root to split into left and right subtrees, and recurse. On skewed trees, repeated linear scans degrade runtime to quadratic.
Upper bound validation passWrite this one
time O(n) · space O(h)
Maintain a global preorder index and recursively build nodes while passing an upper limit. If the next preorder value exceeds the bound, return null. The left branch inherits the current node's value as its bound; the right branch keeps the parent's bound.

Where people lose marks · 2

Unbounded right branches: passing an incorrect upper limit to the right child lets elements belonging to higher ancestors be greedily absorbed into the wrong subtree.
Index increment desynchronization: incrementing the array index before confirming the value falls within the valid bound skips valid elements for ancestor branches.

Full solution

C++

#include <bits/stdc++.h>
using namespace std;

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

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

TreeNode* bstFromPreorder(vector<int>& preorder) {
    int idx = 0;
    return buildBST(preorder, idx, INT_MAX);
}

Java

import java.util.*;

public class Main {
    static class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } }

    private static TreeNode build(int[] preorder, int[] idx, int bound) {
        if (idx[0] >= preorder.length || preorder[idx[0]] > bound) return null;
        int val = preorder[idx[0]++];
        TreeNode root = new TreeNode(val);
        root.left = build(preorder, idx, val);
        root.right = build(preorder, idx, bound);
        return root;
    }

    static TreeNode bstFromPreorder(int[] preorder) {
        int[] idx = new int[]{0};
        return build(preorder, idx, Integer.MAX_VALUE);
    }
}

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def bst_from_preorder(preorder):
    idx = 0
    def build(bound):
        nonlocal idx
        if idx >= len(preorder) or preorder[idx] > bound:
            return None
        val = preorder[idx]
        idx += 1
        root = TreeNode(val)
        root.left = build(val)
        root.right = build(bound)
        return root
    return build(float('inf'))

JavaScript

function TreeNode(val, left, right) {
    this.val = val;
    this.left = left || null;
    this.right = right || null;
}

function bstFromPreorder(preorder) {
    if (!preorder || !preorder.length) return null;
    const root = new TreeNode(preorder[0]);
    const stack = [root];
    for (let i = 1; i < preorder.length; i++) {
        const val = preorder[i];
        const node = new TreeNode(val);
        if (val < stack[stack.length - 1].val) {
            stack[stack.length - 1].left = node;
        } else {
            let parent = stack[stack.length - 1];
            while (stack.length && stack[stack.length - 1].val < val) {
                parent = stack.pop();
            }
            parent.right = node;
        }
        stack.push(node);
    }
    return root;
}

Try it in the editor

The theory behind it

BST — the ground this problem stands on. All BST problems

What BST is

A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.

When to reach for it

Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.

How the pattern works

Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.

Construct Binary Search Tree from Preorder Traversal

The problem

Constraints

How to think about it

Approaches, worst first

Sort preorder to obtain inorder

Recursive partitioning

Upper bound validation passWrite this one

Full solution

The theory behind it

What BST is

When to reach for it

How the pattern works

More BST problems

Interactive Practice

Target Roles

Track in your role's order

The problem

Constraints

How to think about it

Approaches, worst first

chevron_rightSort preorder to obtain inorder

chevron_rightRecursive partitioning

chevron_rightUpper bound validation passWrite this one

Full solution

The theory behind it

What BST is

When to reach for it

How the pattern works

More BST problems

Interactive Practice

Target Roles

Track in your role's order

Sort preorder to obtain inorder

Recursive partitioning

Upper bound validation passWrite this one