Verify Preorder is a Valid BST

Verify Preorder is a Valid BST hands you a flat list of numbers and asks a structural question: could this sequence have come from a preorder traversal of some binary search tree? The elegant answer uses a stack and a single rising lower bound — and runs in one pass.

The slow way first

You could try to rebuild the tree: the first element is the root, then split the rest into the prefix smaller than the root (left subtree) and the suffix larger than it (right subtree), and recurse. That works, but each split scans the remaining array, giving O(n²) in the worst case (a skewed tree).

The question to ask: as I read the values left to right, what constraint does each new value have to obey? In preorder, once you finish a left subtree and step to the right, you can never see a value smaller than the parent you turned right from again. So there is a lower bound that only ever goes up.

The idea: a stack and a rising lower bound

Keep a stack of the ancestors whose left subtrees we are still inside, and a lower bound. For each val:

• If val < lower, the sequence is impossible — return false.
• While the stack top is smaller than val, we are turning right out of that node: pop it and raise lower to its value.
• Push val and continue.

Each pop marks a right turn. The popped value becomes the new floor because nothing in a right subtree may dip below the node it hangs off of.

Walk through it

Step through the animation. The pointer scans [5, 2, 6, 1, 3]. We push 5, then 2 (a left child, smaller than the top). At 6 we pop both 2 and 5 — two right turns — so lower jumps to 5. Then 1 arrives: 1 is below lower = 5, which is impossible, so we return false.

Pseudocode

stack = empty
lower = -infinity
for each val in preorder:
    if val < lower:            # dipped below a right-turn floor
        return false
    while stack not empty and top of stack < val:
        lower = pop the stack   # turning right: raise the floor
    push val onto stack
return true

The Python solution

def verify_preorder(preorder):
    stack = []
    lower = float('-inf')
    for val in preorder:
        if val < lower:
            return False
        while stack and stack[-1] < val:
            lower = stack.pop()
        stack.append(val)
    return True

• stack holds the chain of ancestors we are still inside the left subtree of.
• lower is the floor every future value must clear; it starts at negative infinity.
• Line 5 is the rejection: if val has slipped under the floor, no BST could produce this order.
• Lines 7–8 are the right turns — popping ancestors smaller than val and lifting lower to the last one popped.
• We push val so it can later become a floor when we turn right out of it.

Complexity

Every value is pushed once and popped at most once, so the total work across all the inner while loops is linear — an amortized O(n) pass. The stack uses O(n) space in the worst case (a fully left-leaning input).

When this pattern shows up

Practice