Problem Description

You are given an array of unique integers called preorder. Your task is to determine if this array represents a valid preorder traversal sequence of a binary search tree (BST).

In a preorder traversal, we visit nodes in this order:

1. Visit the root node first
2. Recursively visit the left subtree
3. Recursively visit the right subtree

A binary search tree has the property that for any node:

• All values in its left subtree are less than the node's value
• All values in its right subtree are greater than the node's value

The solution uses a stack-based approach to validate the sequence. It maintains a stack and a variable last that represents the lower bound for subsequent elements. As we iterate through the array:

• If we encounter a value less than last, it means we're trying to add a node that violates the BST property (going to the right subtree but finding a smaller value), so we return False
• While the stack is not empty and the top element is less than the current value x, we pop from the stack and update last. This simulates moving from a left subtree to a right subtree
• We push the current element onto the stack

The algorithm effectively tracks the constraints imposed by the BST structure during a preorder traversal. The stack helps maintain the ancestors we haven't fully processed, and last ensures we don't violate the BST property when moving to right subtrees.

For example, with preorder = [5, 2, 1, 3, 6], this represents a valid BST where 5 is the root, 2 is its left child (with 1 and 3 as its children), and 6 is the right child of 5. The function would return True for this input.

Intuition

When we perform a preorder traversal on a BST, we get a specific pattern: we visit the root first, then all nodes in the left subtree (which are smaller than root), followed by all nodes in the right subtree (which are larger than root).

The key insight is that once we've moved to the right subtree of any node, we should never encounter a value smaller than that node again. This is because in preorder traversal, after visiting a node and its entire left subtree, when we move to the right subtree, all subsequent values must be greater than that node.

Think of it this way: as we traverse the preorder sequence, we're essentially "descending" down the tree. When we see smaller values, we're going left. When we see a larger value, we might be going right. The tricky part is figuring out which ancestor's right subtree we're entering.

This is where the stack comes in. The stack keeps track of the "path" from root to our current position - essentially all ancestors we haven't finished processing. When we encounter a value larger than some elements in our stack, it means we're done with those nodes' left subtrees and are moving to a right subtree.

The moment we pop a value from the stack (because current element is larger), that popped value becomes our new lower bound (last). Why? Because we're now in its right subtree, and everything that follows must be greater than it.

For example, consider [5, 2, 6, 1]. After processing 5, 2, and 6, our last would be 5 (since 6 > 5, we popped 5 and moved to its right subtree). Now when we see 1, which is less than 5, we know this can't be a valid BST preorder sequence - we can't have a value less than 5 appearing after we've already moved to 5's right subtree.

The algorithm elegantly captures this constraint: use a stack to track ancestors, and maintain the most recent "left-behind" ancestor as the minimum bound for all future values.

Solution Approach

The solution uses a stack-based simulation of the preorder traversal validation. Here's how the implementation works:

Data Structures Used:

• stk: A stack to keep track of ancestor nodes we haven't fully processed
• last: A variable initialized to negative infinity that maintains the lower bound for subsequent values

Algorithm Steps:

1. Initialize the stack and lower bound:

   stk = []
   last = -inf

   The stack starts empty, and last is set to negative infinity since initially there's no lower bound constraint.

2. Process each element in the preorder array:

   for x in preorder:

3. Check BST violation:

   if x < last:
       return False

   If the current value x is less than last, we've violated the BST property. This means we're trying to insert a value that's smaller than a node whose right subtree we've already entered.

4. Update the stack and lower bound:

   while stk and stk[-1] < x:
       last = stk.pop()

   While the stack is not empty and its top element is less than the current value x, we pop elements. This simulates moving from a left subtree to a right subtree. The last popped value becomes our new lower bound last because we're entering its right subtree.

5. Push current element to stack:

   stk.append(x)

   Add the current element to the stack as it becomes part of the current path.

6. Return the result:

   return True

   If we process all elements without finding a violation, the sequence is valid.

Example Walkthrough:

For preorder = [5, 2, 1, 3, 6]:

• Process 5: stk = [5], last = -inf
• Process 2: 2 > -inf ✓, 2 < 5 (no pop), stk = [5, 2]
• Process 1: 1 > -inf ✓, 1 < 2 (no pop), stk = [5, 2, 1]
• Process 3: 3 > -inf ✓, 3 > 1 (pop 1), 3 > 2 (pop 2), last = 2, stk = [5, 3]
• Process 6: 6 > 2 ✓, 6 > 3 (pop 3), 6 > 5 (pop 5), last = 5, stk = [6]
• All elements processed successfully → return True

Time Complexity: O(n) where n is the length of the preorder array. Each element is pushed and popped at most once.

Space Complexity: O(n) in the worst case when the tree is completely left-skewed, causing all elements to be in the stack.

Example Walkthrough

Let's walk through a small example with preorder = [8, 5, 1, 7, 10, 12] to see how the algorithm validates this sequence.

Initial State:

• stk = [] (empty stack)
• last = -infinity (no lower bound yet)

Step 1: Process 8

• Check: 8 > -infinity ✓ (no violation)
• Stack top check: stack is empty, no popping needed
• Push 8: stk = [8]
• State: We're at the root

Step 2: Process 5

• Check: 5 > -infinity ✓ (no violation)
• Stack top check: 5 < 8, no popping needed
• Push 5: stk = [8, 5]
• State: We went left from 8

Step 3: Process 1

• Check: 1 > -infinity ✓ (no violation)
• Stack top check: 1 < 5, no popping needed
• Push 1: stk = [8, 5, 1]
• State: We went left from 5

Step 4: Process 7

• Check: 7 > -infinity ✓ (no violation)
• Stack top check: 7 > 1, so pop 1 → last = 1
• Continue: 7 > 5, so pop 5 → last = 5
• Continue: 7 < 8, stop popping
• Push 7: stk = [8, 7]
• State: We're now in the right subtree of 5 (all future values must be > 5)

Step 5: Process 10

• Check: 10 > 5 ✓ (no violation)
• Stack top check: 10 > 7, so pop 7 → last = 7
• Continue: 10 > 8, so pop 8 → last = 8
• Push 10: stk = [10]
• State: We're now in the right subtree of 8 (all future values must be > 8)

Step 6: Process 12

• Check: 12 > 8 ✓ (no violation)
• Stack top check: 12 > 10, so pop 10 → last = 10
• Push 12: stk = [12]
• State: We're in the right subtree of 10

Result: All elements processed successfully → return True

The corresponding BST would look like:

       8
      / \
     5   10
    / \    \
   1   7    12

Why this works: The algorithm tracks when we transition from a left subtree to a right subtree. When we pop elements from the stack (because we found a larger value), we're essentially saying "we're done with this node's left subtree and moving to its right." The last popped value becomes our minimum bound because everything in a right subtree must be greater than its parent node.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the preorder array.

The algorithm iterates through each element in the preorder array exactly once. For each element, we perform:

• A comparison with last: O(1)
• A while loop that pops elements from the stack
• An append operation to the stack: O(1)

Although there's a nested while loop, each element can be pushed to and popped from the stack at most once throughout the entire execution. Therefore, the total number of operations across all iterations is bounded by 2n (each element is pushed once and popped at most once), resulting in O(n) time complexity.

Space Complexity: O(n) in the worst case.

The space is used by the stack stk. In the worst case, when the preorder traversal represents a skewed tree (all nodes only have left children or form a strictly decreasing sequence), all elements would be pushed onto the stack before any popping occurs, requiring O(n) space. In the best case of a skewed tree with only right children, the stack would maintain at most one element at a time, giving O(1) space, but we consider worst-case complexity.

Common Pitfalls

1. Forgetting to Update the Lower Bound Correctly

A common mistake is not properly tracking the lower bound (last or min_value) when transitioning from a left subtree to a right subtree. Some implementations might forget to update this value or update it incorrectly.

Incorrect Implementation:

# WRONG: Not updating the lower bound
while stack and stack[-1] < current_value:
    stack.pop()  # Just popping without updating min_value

Correct Implementation:

# CORRECT: Update min_value with the last popped element
while stack and stack[-1] < current_value:
    min_value = stack.pop()

The last popped value represents the parent node whose right subtree we're entering, so it becomes the new lower bound.

2. Using Wrong Initial Value for Lower Bound

Another pitfall is initializing the lower bound with 0 or some arbitrary value instead of negative infinity.

Incorrect Implementation:

# WRONG: May fail for negative values in the tree
min_value = 0  # What if the BST contains negative values?

Correct Implementation:

# CORRECT: Use negative infinity to handle all possible values
min_value = -inf

3. Incorrect Comparison in the While Loop

Using <= instead of < in the while loop condition can lead to incorrect results when dealing with the BST property.

Incorrect Implementation:

# WRONG: Equal values shouldn't be popped
while stack and stack[-1] <= current_value:
    min_value = stack.pop()

Correct Implementation:

# CORRECT: Only pop strictly smaller values
while stack and stack[-1] < current_value:
    min_value = stack.pop()

4. Not Handling Edge Cases

Forgetting to handle edge cases like empty arrays or single-element arrays.

Better Implementation with Edge Case Handling:

def verifyPreorder(self, preorder: List[int]) -> bool:
    # Handle edge cases
    if not preorder or len(preorder) <= 1:
        return True
  
    stack = []
    min_value = -inf
  
    for current_value in preorder:
        if current_value < min_value:
            return False
      
        while stack and stack[-1] < current_value:
            min_value = stack.pop()
      
        stack.append(current_value)
  
    return True

5. Misunderstanding the Algorithm's Purpose

Some might think the stack needs to be empty at the end for validation, but this is incorrect. The stack can contain elements at the end (representing the rightmost path in the tree).

Wrong Assumption:

# WRONG: Stack doesn't need to be empty
return len(stack) == 0

Correct Understanding:

# CORRECT: Just return True if all elements processed without violation
return True