Rebuild a Search Tree From Its Node-First Listing

Medium25–30 min

Topics

Binary Search TreeBSTPreorderConstruction

Companies

AmazonMicrosoftGoogleFacebookBloomberg

You are given the pre-order listing of a binary search tree with distinct values: each node appears before its left subtree, which appears before its right subtree. Rebuild the tree and return its root. A binary search tree is fully determined by its pre-order listing.

You can insert the values one at a time into an empty tree, which works because of the order they are listed in. A single left-to-right pass that carries an upper bound for each subtree does the same in linear time.

Test Case 1:

Input:preorder = [45, 20, 10, 30, 70, 60, 90]

Output:[45, 20, 70, 10, 30, 60, 90]

Explanation:45 is the root. The values 20, 10, 30 (smaller than 45) form its left subtree and 70, 60, 90 its right subtree; the same rule rebuilds each side.

Test Case 2:

Input:preorder = [12, 7, 3, 9, 15, 20]

Output:[12, 7, 15, 3, 9, null, 20]

Explanation:After the root 12, the values 7, 3, 9 are smaller (left subtree) and 15, 20 are larger (right subtree; 20 is the right child of 15).

Test Case 3:

Input:preorder = []

Output:[]

Explanation:No values: the empty tree.

Constraints

◆0 ≤ preorder.length ≤ 100; all values are distinct, 0 ≤ preorder[i] ≤ 1000
◆preorder is the pre-order listing (node, left subtree, right subtree) of some binary search tree (left subtree smaller, right subtree larger); such a tree is guaranteed to exist
◆Return the root of that tree (checked as a level-order list); an empty listing gives the empty tree
◆A tree is uniquely determined by its pre-order listing together with the search-tree property

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Insert the Values One by One Into an Empty Tree

Brute

The pre-order listing is exactly a valid order in which to insert the values into an initially empty search tree: every node is listed before its descendants, so inserting in that order puts each value back below its old parent. Start with an empty tree and insert each value with the ordinary search-tree insertion (walk down comparing, attach as a new leaf). Every insertion costs the current height: O(n · h) time — O(n²) for a chain — and O(h) recursion space.

TimeO(n · h)

SpaceO(h)

Java

Try it out

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

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

Optimal — One Pass With an Upper Bound

Optimal

Read the pre-order list once, from left to right, with a single running index. To build a subtree that may only contain values below some upper bound: if the next unread value is missing or is larger than the bound, this subtree is empty. Otherwise the next value is the subtree's root (consume it), its left subtree is built next with the root's value as the new bound (left values must be smaller), and after that its right subtree with the ORIGINAL bound (right values are larger than the root but must still respect the bound inherited from above). Every value is consumed exactly once: O(n) time, O(h) recursion space.

TimeO(n)