Code Implementation

class Solution:
    def verifyPreorder(self, preorder):
        lower_bound = float('-inf')
        stack = []
        for value in preorder:
            if value < lower_bound:
                return False
            while stack and value > stack[-1]:
                lower_bound = stack.pop()
            stack.append(value)
        return True
      

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        int lower_bound = INT_MIN;
        vector<int> stack;
        for (int value : preorder) {
            if (value < lower_bound)
                return false;
            while (!stack.empty() && value > stack.back()) {
                lower_bound = stack.back();
                stack.pop_back();
            }
            stack.push_back(value);
        }
        return true;
    }
};
      

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int lowerBound = Integer.MIN_VALUE;
        int i = -1;
        for (int value : preorder) {
            if (value < lowerBound) return false;
            while (i >= 0 && value > preorder[i]) {
                lowerBound = preorder[i--];
            }
            preorder[++i] = value;
        }
        return true;
    }
}
      

var verifyPreorder = function(preorder) {
    let lowerBound = -Infinity;
    let stack = [];
    for (let value of preorder) {
        if (value < lowerBound) return false;
        while (stack.length && value > stack[stack.length - 1]) {
            lowerBound = stack.pop();
        }
        stack.push(value);
    }
    return true;
};
      

Problem Description

Given an array preorder of integers, determine if it can represent the preorder traversal of a binary search tree (BST).

• Each element in preorder is unique.
• You must verify if there exists at least one BST whose preorder traversal yields exactly preorder.
• You must not use or modify elements more than once.

Return True if the sequence is a valid preorder traversal of a BST, otherwise return False.

Thought Process

The problem asks us to check if a given sequence could be the preorder traversal of a BST. The naive approach would be to reconstruct all possible BSTs and compare their preorder traversals to the input, but this is computationally infeasible for large inputs.

Instead, we can leverage the properties of BSTs and preorder traversal:

• In preorder traversal, we visit the root, then the left subtree, then the right subtree.
• In a BST, all nodes in the left subtree are less than the root, and all nodes in the right subtree are greater than the root.

The challenge is to efficiently check these constraints as we process the sequence, ideally in linear time and space.

Solution Approach

We use a stack-based approach to simulate the preorder traversal and enforce BST constraints:

1. Initialize a lower bound to negative infinity. This represents the minimum value that the next node can have (since once we move to the right subtree, all subsequent nodes must be greater than all ancestors in the left).
2. Iterate through each value in the preorder array:
   • If the current value is less than the lower bound, return False (BST property violated).
   • While the stack is not empty and the current value is greater than the top of the stack, pop from the stack and update the lower bound to the popped value. This simulates moving from a left subtree to a right subtree.
   • Push the current value onto the stack.
3. If we finish processing all values without finding any violations, return True.

This approach works because the stack maintains the path from the root down to the current node, and the lower bound ensures that we don't revisit a left subtree after moving to a right subtree.

Example Walkthrough

Let's use the input [5, 2, 1, 3, 6]:

• Start with lower_bound = -∞, stack = []
• Process 5: 5 > -∞, push 5. stack = [5]
• Process 2: 2 > -∞, push 2. stack = [5, 2]
• Process 1: 1 > -∞, push 1. stack = [5, 2, 1]
• Process 3: 3 > -∞, 3 > 1 (pop 1, set lower_bound=1), 3 > 2 (pop 2, set lower_bound=2), 3 < 5, push 3. stack = [5, 3]
• Process 6: 6 > 2, 6 > 3 (pop 3, set lower_bound=3), 6 > 5 (pop 5, set lower_bound=5), push 6. stack = [6]

All values processed without violating the lower bound. So, the sequence is a valid preorder traversal of a BST.

Time and Space Complexity

• Brute-force approach: Reconstructing all BSTs and checking their preorder traversals would be exponential in time and space (O(2^N) or worse), which is infeasible.
• Optimized stack-based approach:
  • Time Complexity: O(N), where N is the length of preorder. Each element is pushed and popped at most once.
  • Space Complexity: O(N) in the worst case (for the stack), but can be optimized to O(1) if using the input array itself as a stack (as in the Java code).

Summary

By leveraging the properties of BSTs and preorder traversal, we efficiently verify a preorder sequence using a stack and a dynamic lower bound. This avoids brute-force tree reconstruction and achieves linear time and space. The key insight is to simulate the traversal path and enforce the BST property at each step, making the solution both elegant and optimal.