Verify Preorder Sequence in Binary Search Tree - Solution & Explanation

Problem Overview: Given an integer array representing a preorder traversal, determine whether it could come from a valid Binary Search Tree (BST). In a BST preorder sequence, each value must respect the BST rule: values in the left subtree are smaller than the root, and values in the right subtree are greater.

Approach 1: Construct the BST and Validate Preorder (O(n log n) time, O(n) space)

Insert each value into a BST following normal insertion rules, then generate the preorder traversal of the constructed tree and compare it with the original array. If both match, the sequence is valid. This approach simulates how the tree would actually form. However, BST insertion may take O(log n) on average but O(n) in the worst case for skewed trees, leading to O(n^2) worst‑case behavior. Useful for understanding the relationship between traversal order and BST structure, but inefficient for interviews.

Approach 2: Recursion with Value Bounds (O(n) time, O(n) space)

Process the preorder array while maintaining valid value ranges for each subtree. Each node must lie within a (min, max) range inherited from its ancestors. The first value becomes the root. Recursively verify that upcoming values fall into the allowed range for the left subtree, then the right subtree. This approach mimics the way preorder traversal builds a BST and ensures each node respects ancestor constraints. It uses recursion stack space proportional to the tree height.

Approach 3: Monotonic Stack with Lower Bound (O(n) time, O(n) space)

The optimal method uses a stack to simulate traversal of the BST while tracking a lower bound. Iterate through the array. When the current value is smaller than the allowed lower bound, the sequence violates BST rules. While the stack top is smaller than the current value, pop elements and update the lower bound because you are moving from a left subtree into a right subtree. Push the current value onto the stack. This stack behaves like a monotonic stack that keeps ancestors whose right subtree hasn't been processed yet.

This technique works because preorder visits nodes in root → left → right order. Once you encounter a value larger than a previous node, you are transitioning into that node's right subtree, and all future values must be greater than it. The algorithm processes each element once, giving linear time complexity.

Recommended for interviews: The monotonic stack approach is the expected solution. It runs in O(n) time with a single pass and demonstrates understanding of preorder traversal properties in a Binary Search Tree. Mentioning the recursive bounds idea first shows conceptual understanding, while implementing the stack solution shows practical optimization skills.