Verify Preorder Sequence in Binary Search Tree

Verify Preorder Sequence in Binary Search Tree

What is this problem about?

The "Verify Preorder Sequence in Binary Search Tree" interview question asks you to check if a given array of integers represents a valid preorder traversal of some Binary Search Tree (BST). In preorder traversal, the nodes are visited in the order: Root, Left Subtree, Right Subtree.

Why is this asked in interviews?

Companies like Nvidia and Salesforce use this coding problem to test a candidate's understanding of BST properties without actually having a tree structure. It challenges you to use a "Monotonic Stack interview pattern" to solve a tree problem in linear time, which is a common optimization requested in senior-level interviews.

Algorithmic pattern used

The optimal approach uses a "Monotonic Stack." As you traverse the array, you simulate the traversal. When you see a value smaller than the top of the stack, it's a left child. When you see a value larger, you've moved to a right subtree. The values you pop from the stack represent "completed" subtrees, and their values set a "lower bound" (low) for all future elements. In a BST, any element in a right subtree must be greater than its parent.

Example explanation

Sequence: [5, 2, 1, 3, 6]

1. low = -infinity, Stack: [].
2. element 5: 5 > -inf. Push 5. Stack: [5].
3. element 2: 2 > -inf. 2 < 5, so it's a left child. Push 2. Stack: [5, 2].
4. element 1: 1 > -inf. 1 < 2, so it's a left child. Push 1. Stack: [5, 2, 1].
5. element 3: 3 > -inf. 3 > 1 and 3 > 2. Pop 1, then pop 2. low becomes 2. Push 3. Stack: [5, 3].
6. element 6: 6 > 2. 6 > 3 and 6 > 5. Pop 3, then pop 5. low becomes 5. Push 6. Stack: [6].
7. Result: True (all elements followed the BST lower bound rule).

Common mistakes candidates make

A common mistake is using a recursive O(n²) approach that finds the first element larger than the root and splits the array. While correct, it's too slow. Another error is not updating the "lower bound" correctly when moving to a right child, which is the key to identifying invalid BST structures (where a right-subtree node is smaller than an ancestor it should be larger than).

Interview preparation tip

For the "Verify Preorder Sequence in Binary Search Tree" coding problem, practice the "In-place Stack" optimization. You can use the input array itself as a stack to achieve O(1) extra space complexity. This level of optimization is often what differentiates "passing" from "excelling" in a technical interview.