Verify Preorder Sequence in Binary Search Tree

Given an array of integers representing a sequence, determine if it's a valid preorder traversal of a Binary Search Tree (BST). This problem tests your understanding of BST properties and recursion/stack-based traversal techniques. Validating preorder sequences is useful in scenarios where you receive data from a potentially corrupted or incomplete BST traversal.

Problem Description

You are given an array preorder representing a sequence of nodes. Your task is to determine if this sequence could be the result of a valid preorder traversal of a Binary Search Tree (BST). A valid preorder traversal of a BST follows these rules:

1. The first element in the sequence is the root of the subtree.
2. All elements to the left of the root in the sequence are smaller than the root.
3. All elements to the right of the root in the sequence are greater than the root.
4. The subsequences to the left and right of the root must also be valid preorder traversals of BSTs.

You must return true if the given preorder array represents a valid preorder traversal of a BST, and false otherwise.

Key Requirements:

• The input array preorder contains only integers.
• The array may be empty.
• The array may contain duplicate values.
• The array is not necessarily sorted.

Expected Behavior:

The function should return true if the input array is a valid preorder traversal of a BST. Otherwise, it should return false.

Edge Cases to Consider:

• Empty input array: Should return true (an empty tree is a valid BST).
• Single-element input array: Should return true (a single node is a valid BST).
• Input array with duplicate values: The algorithm must correctly handle duplicates, ensuring that elements to the right of a node are strictly greater.
• Input array that violates BST properties: The algorithm must correctly identify sequences that cannot be a valid preorder traversal.

Examples

Example 1:

Input: [5, 2, 1, 3, 6]
Output: true
Explanation: This sequence can represent a BST where the root is 5, the left subtree has root 2 (with 1 and 3 as children), and the right subtree has root 6.

Example 2:

Input: [5, 2, 6, 1, 3]
Output: false
Explanation: This sequence is invalid because 1 and 3 are smaller than 6, but they appear after 6 in the sequence, violating the BST preorder property.

Example 3:

Input: [4,2,1,3]
Output: true
Explanation: This is a valid preorder traversal.

Example 4:

Input: [4,2,3,1]
Output: false
Explanation: This is not a valid preorder traversal. 1 should appear before 3.

Constraints

• 1 <= preorder.length <= 10000
• -10000 <= preorder[i] <= 10000 for all i
• The solution should have a time complexity of O(n), where n is the length of the preorder array. A stack-based approach is generally preferred for achieving this.

Notes

Consider using a stack to keep track of the potential parent nodes during the traversal. The stack will help you determine the lower bound for the values that can appear to the right of a node. Think about how the stack changes as you iterate through the preorder array and how to detect violations of the BST property. The lower bound is the last element pushed onto the stack.