Construct Binary Search Tree from Preorder Traversal

Medium Trees & BST Tree Serialization / Deserialization Original on LeetCode

Construct Binary Search Tree from Preorder Traversal is a medium trees & bst problem solved with the tree serialization / deserialization pattern. The best approach, optimal (single pass with an upper bound), runs in O(n) time and O(h) space. Below are 2 approaches in Java, from insert one by one up.

Problem

Given the preorder traversal of a BST, rebuild the tree and return its root.

Examples

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 <= n <= 100; values are unique and form a valid BST preorder.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Insert one by one	`O(n²)`	`O(h)`
Optimal (single pass with an upper bound)	`O(n)`	`O(h)`

1Insert one by one

TimeO(n²)Each insert is O(h), and h can be n.

SpaceO(h)

Insert each value into a BST in preorder order. Inserting in preorder rebuilds exactly the original tree.

root = null; for each v: root = insert(root, v).

Java

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = null;
        for (int v : preorder) root = insert(root, v);
        return root;
    }

    private TreeNode insert(TreeNode n, int v) {
        if (n == null) return new TreeNode(v);
        if (v < n.val) n.left = insert(n.left, v);
        else n.right = insert(n.right, v);
        return n;
    }
}

2Optimal (single pass with an upper bound)

TimeO(n)

SpaceO(h)

Read preorder left to right with a shared index. build(bound) creates a node only if the next value is below bound. Its left subtree takes values below the node, and its right subtree takes values up to the parent's bound.

If i == n or preorder[i] > bound, return null.
root = new node(preorder[i++]).
root.left = build(root.val); root.right = build(bound).

Java

class Solution {
    private int i;

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

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

Edge cases to test

Strictly increasing or decreasing input (skewed tree)

Hints

Hint 1

Each value you read must fit below an upper bound. If the next value is larger than the bound, this subtree is finished.

FAQ

What is the best time complexity for Construct Binary Search Tree from Preorder Traversal?

Optimal (single pass with an upper bound) runs in O(n) time and O(h) extra space.

Which pattern does Construct Binary Search Tree from Preorder Traversal use?

It is a trees & bst problem that uses the tree serialization / deserialization pattern. Other problems with the same pattern: Construct Binary Tree from Preorder and Inorder Traversal, Construct Binary Tree from Inorder and Postorder Traversal, Serialize and Deserialize Binary Tree.

Is there a brute force solution for Construct Binary Search Tree from Preorder Traversal?

Yes. Insert one by one takes O(n²) time and O(h) space. Insert each value into a BST in preorder order.

Which edge cases should I test for Construct Binary Search Tree from Preorder Traversal?

Strictly increasing or decreasing input (skewed tree).