Verify Preorder Sequence in Binary Search Tree - Solution & Explanation

Problem Overview: You get an integer array that claims to be the preorder traversal of a Binary Search Tree (BST). The task is to verify whether such a BST could actually produce this preorder sequence without constructing the full tree.

Approach 1: Build the BST and Validate Preorder (O(n^2) time, O(n) space)

The most straightforward idea is to simulate insertion into a BST while iterating through the preorder array. Insert each element into a BST using standard BST insertion rules. After constructing the tree, generate its preorder traversal and compare it with the input array. This confirms whether the sequence is valid. The downside is that skewed trees cause insertion to degrade to O(n) per element, giving O(n^2) time overall and O(n) memory for the tree. Useful mainly for understanding BST behavior rather than writing optimal code.

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

A valid BST preorder traversal always respects value boundaries defined by ancestors. While processing nodes recursively, track a min and max range that the next value must satisfy. The first element becomes the root. Values smaller than the root belong to the left subtree, while larger values belong to the right subtree but must still respect ancestor bounds. If a value violates these constraints, the sequence cannot represent a BST preorder traversal. This approach closely mirrors actual BST construction and leverages recursion similar to problems involving Binary Search Tree validation.

Approach 3: Monotonic Stack Simulation (O(n) time, O(n) space)

The optimal solution avoids building the tree entirely. Iterate through the array while maintaining a stack representing the path from root to the current node. Also track a variable lowerBound representing the smallest allowed value for the current node. Whenever the current value is greater than the top of the stack, pop elements and update lowerBound, which simulates moving up the tree to a right subtree. If the current value ever becomes smaller than lowerBound, the preorder sequence is invalid. The stack remains monotonic decreasing and processes each element once. This technique combines ideas from stack processing and monotonic stack patterns.

Recommended for interviews: The monotonic stack solution is the expected answer. It runs in O(n) time with a single pass and demonstrates strong understanding of preorder traversal constraints. Mentioning the brute-force tree construction shows baseline reasoning, but implementing the stack-based simulation signals mastery of preorder properties and stack-based traversal techniques.