Construct BST from preorder traversal

The problem, simply

Someone walked a binary search tree (BST) in "me, then my left side, then my right side" order and wrote down the numbers. That order is called preorder. You get that list. Build the tree back and return its top.

The first number is always the top. The tricky part is knowing where the left side's numbers end and the right side's numbers begin.

A story to remember it

Picture it

Examples

Way 1: the simple way

Build an empty tree and put the numbers in one by one, in the given order, with the normal BST insert (walk down, smaller left, bigger right, hang it where you fall off). Because the top always comes first in preorder, inserting in that order rebuilds exactly the same tree.

1. The first number becomes the top.
2. For each next number, walk down from the top and hang it in the empty spot where it belongs.

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

    private TreeNode insert(TreeNode node, int x) {
        if (node == null) return new TreeNode(x);      // the empty spot it belongs in
        if (x < node.val) node.left = insert(node.left, x);
        else node.right = insert(node.right, x);
        return node;
    }
}

How long it takes: each insert walks the height. For a stick shaped tree that is 1 + 2 + ... + n, so O(n^2). For a bushy tree it is about O(n log n). Extra room: the recursion, O(h).

Way 2: the clever way

Read the list once, left to right, with one finger i. Build the tree top down with a function build(ceiling) that means "make the next part of the tree, using only numbers below this ceiling".

1. If the list is used up, or the next number is above the ceiling, this spot stays empty. Return null and do not move i.
2. Otherwise the next number belongs here. Make a spot for it and move i forward.
3. Its left side is build(its own value): only numbers smaller than it may go there.
4. Its right side is build(the same ceiling): bigger numbers, but still under the old ceiling.

Each number is looked at a few times but placed once, and i only moves forward. The pile on the right is the list of waiting helpers with their ceilings.

class Solution {
    private int i;                                   // the next number to place

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

    private TreeNode build(int[] pre, int ceiling) {
        if (i == pre.length || pre[i] > ceiling) return null;  // does not fit here
        TreeNode node = new TreeNode(pre[i++]);
        node.left = build(pre, node.val);            // smaller than me
        node.right = build(pre, ceiling);            // bigger than me, under the old ceiling
        return node;
    }
}

How long it takes: i moves forward n times, and each call either places a number or returns right away. There are about 2n + 1 calls, so O(n). Extra room: the recursion depth, O(h).

Another way: a stack of open seats

Keep a pile of spots whose right seat might still be open. For each new number: if it is smaller than the top of the pile, it is that spot's left child. Otherwise pop every spot smaller than it. The last one popped is its parent, and it becomes that spot's right child. Push the new spot.

import java.util.*;

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        if (preorder.length == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> pile = new ArrayDeque<>();
        pile.push(root);
        for (int k = 1; k < preorder.length; k++) {
            TreeNode node = new TreeNode(preorder[k]);
            if (node.val < pile.peek().val) {
                pile.peek().left = node;              // fits on the left of the newest spot
            } else {
                TreeNode parent = null;
                while (!pile.isEmpty() && pile.peek().val < node.val) parent = pile.pop();
                parent.right = node;                  // the last smaller spot takes it on the right
            }
            pile.push(node);
        }
        return root;
    }
}

Same O(n) time, since each spot is pushed and popped once, and O(h) room for the pile.

Watch out for

• Passing node.val as the ceiling for the right side. The right side keeps the parent's ceiling, not a new one.
• Splitting the list by finding "the first bigger number" in each call. That is correct but O(n^2) on a stick, the same as Way 1.
• If the list might not be a real preorder of a BST, Way 2 stops early with i < n. Check i == n at the end to detect that.

What interviewers ask next

• Build from postorder. Read the list from the back with a floor instead of a ceiling, and build the right side before the left side.
• Is this list a valid preorder of some BST? Run Way 2 and check that every number was used, or use the stack trick with a growing lower limit. See "Check preorder is valid or not".
• Build from inorder alone. Not possible, since many trees share one sorted order. Inorder plus preorder works for any binary tree.
• Send a BST over the network and rebuild it (serialize and deserialize). Send the preorder list. This page is the rebuild half, and no null markers are needed because the BST rule tells you where each number goes.

Remember this

Grown-up words: the "me, left, right" order is a preorder traversal, the height limit on a seat is an upper bound, the finger is a shared index, the waiting helpers are the call stack, and the pile of open seats is a monotonic stack.