Check preorder is valid or not

The problem, simply

You get a list of different numbers. Say true if some binary search tree (BST) would give exactly this list when you visit it in "me, then my left side, then my right side" order (preorder). Say false otherwise.

The first number must be the top. After it come all the numbers of the left side (all smaller), and then all the numbers of the right side (all bigger). Each side must follow the same rule inside.

A story to remember it

Picture it

Examples

Way 1: the simple way

Check the rule directly, part by part.

1. The first number of a part is its top.
2. Walk forward while numbers are smaller. That is the left side.
3. Everything after that must be bigger than the top. If one is smaller, say false.
4. Check the left side and the right side the same way.

class Solution {
    public boolean canRepresentBST(int[] pre) {
        return ok(pre, 0, pre.length - 1);
    }

    private boolean ok(int[] pre, int lo, int hi) {
        if (lo >= hi) return true;                 // zero or one number
        int top = pre[lo];
        int j = lo + 1;
        while (j <= hi && pre[j] < top) j++;       // the left side
        for (int k = j; k <= hi; k++) {
            if (pre[k] < top) return false;        // a small number on the right side
        }
        return ok(pre, lo + 1, j - 1) && ok(pre, j, hi);
    }
}

How long it takes: each part scans all of its numbers, and on a stick the parts shrink by one each time, so O(n^2). Extra room: the recursion can be n deep, O(n).

Way 2: the clever way

Read the list once with a pile (a stack) of spots that are still "open on the right", and a sticky note floor.

1. If the number is below floor, say false.
2. While the top of the pile is smaller than the number, pop it and set floor to it. The last spot popped is where the number hangs, on its right side, and nothing smaller may come after.
3. Push the number. (If nothing was popped, the number hangs on the left of the pile's top.)
4. If the list ends with no trouble, say true.

The pile always goes from bigger at the bottom to smaller at the top. The drawing grows the tree as the pile builds it.

import java.util.*;

class Solution {
    public boolean canRepresentBST(int[] pre) {
        Deque<Integer> pile = new ArrayDeque<>();
        long floor = Long.MIN_VALUE;               // nothing may go below this
        for (int x : pre) {
            if (x < floor) return false;
            while (!pile.isEmpty() && pile.peek() < x) {
                floor = pile.pop();                // we moved to the right of this spot
            }
            pile.push(x);
        }
        return true;
    }
}

How long it takes: each number is pushed once and popped at most once, O(n). Extra room: the pile, up to n for a left stick, O(n). If you may change the input, you can use the front of the array itself as the pile and get O(1) extra room.

Watch out for

• Setting floor to the number being pushed instead of the one being popped.
• Using int with Integer.MIN_VALUE as the start is fine for distinct values, but long avoids any doubt.
• Duplicates. Ask how equal values are placed. With "equal goes right", pop while peek() <= x.

What interviewers ask next

• Check a postorder list instead. Read it backwards: it is "me, right side, left side". Use a ceiling that falls instead of a floor that rises.
• Can you check it with no pile at all? Run the ceiling builder from "Construct BST from preorder traversal" without making nodes. If it uses every number, the list is valid. That uses O(h) room for the recursion.
• Once you know it is valid, print the leaf numbers without building the tree. A number is a leaf when the next number either pops it or is placed below another spot.
• Why does the stack go bigger to smaller from bottom to top? It holds the current road from the top, only the spots where we last went left. Those get smaller as we go down.

Remember this

Grown-up words: the "me, left, right" order is a preorder traversal, the pile of spots still open on the right is a monotonic decreasing stack, the sticky note is a lower bound, and the "last popped is the parent" step is how the stack rebuilds the tree.