Verify Preorder Sequence in Binary Search Tree

medium tree stack bst

Problem

Given an array of unique integers preorder, return true if it could be the preorder traversal of a binary search tree.

Inputpreorder = [5,2,1,3,6]

Outputtrue

Valid BST: root 5, left subtree {2,1,3}, right subtree {6}.

preorder (comma-separated)

def verify_preorder(pre):
    stack = []
    lo = float("-inf")
    for v in pre:
        if v < lo:
            return False
        while stack and stack[-1] < v:
            lo = stack.pop()
        stack.append(v)
    return True

function verifyPreorder(pre) {
  const stack = [];
  let lo = -Infinity;
  for (const v of pre) {
    if (v < lo) return false;
    while (stack.length && stack[stack.length-1] < v) lo = stack.pop();
    stack.push(v);
  }
  return true;
}

class Solution {
    public boolean verifyPreorder(int[] pre) {
        Deque stack = new ArrayDeque<>();
        int lo = Integer.MIN_VALUE;
        for (int v : pre) {
            if (v < lo) return false;
            while (!stack.isEmpty() && stack.peek() < v) lo = stack.pop();
            stack.push(v);
        }
        return true;
    }
}

bool verifyPreorder(vector& pre) {
    stack st;
    int lo = INT_MIN;
    for (int v : pre) {
        if (v < lo) return false;
        while (!st.empty() && st.top() < v) { lo = st.top(); st.pop(); }
        st.push(v);
    }
    return true;
}

Explanation

In a binary search tree, a preorder walk visits the root, then everything in the left subtree (all smaller), then everything in the right subtree (all larger). The clever trick here is to replay that walk using a stack plus a single lower bound lo, without ever building the tree.

As we read values, we keep pushing them while they stay smaller — that is us going deeper down left children. The moment a value is bigger than the top of the stack, we have turned into a right subtree, so we pop all the smaller ancestors and raise lo to the last popped value. From now on, nothing is allowed to be below that floor.

Why does it work? Once you step into someone's right subtree, every remaining number must be larger than that node, forever. So if any later value dips below lo, it would have to sit in a left subtree we already left behind — impossible for a real BST preorder, and we return False.

Example: [5, 2, 1, 3, 6]. Push 5, 2, 1. Then 3 > 1 and > 2, so pop 1 and 2, set lo = 2, push 3. Then 6 > 3 and 5, pop them, set lo = 5, push 6. No value ever fell below the floor, so it is valid.

Each value is pushed and popped at most once, so the whole check runs in a single linear pass.

Time: O(n) Space: O(n)