Preorder Validation for BST | Dataford Interview Questions

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):

Your question is Preorder Validation for BST. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

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):

Your question is Preorder Validation for BST. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.