Preorder Validation for BST

MediumPython

Problem

NCR Voyix checkout and retail software may serialize tree-based configuration data as traversal arrays. Given an integer array, determine whether it could be the preorder traversal of a binary search tree, without constructing the tree.

A preorder traversal visits each node in this order: root, left subtree, right subtree. The BST must be strict, so duplicate values are not allowed. Return True if at least one valid BST can produce the array, otherwise return False.

Formal Specification

Input: preorder, a list of integers.
Output: A boolean indicating whether preorder is a valid preorder traversal of a strict BST.
An empty array is considered valid because it represents an empty BST.

Constraints

0 <= len(preorder) <= 10^5
-10^9 <= preorder[i] <= 10^9
Duplicate values are invalid

Function Signature

def is_valid_preorder(preorder):

Formal Specification

Input: preorder, a list of integers.
Output: A boolean indicating whether preorder is a valid preorder traversal of a strict BST.
An empty array is considered valid because it represents an empty BST.