1. Monotonic Stack

Intuition

In a BST preorder traversal, we visit root, then left subtree, then right subtree. When we move to a right subtree, all subsequent values must be greater than the ancestors we are leaving behind. The key insight is to use a decreasing stack to track ancestors. When we encounter a larger value, we pop smaller ancestors and update the minimum limit, as we are now in a right subtree.

Algorithm

1. Initialize a stack and set min_limit to negative infinity.
2. Iterate through each number in the preorder sequence.
3. While the stack is not empty and the stack top is less than the current number, pop from the stack and update min_limit to the popped value.
4. If the current number is less than or equal to min_limit, return false as it violates BST property.
5. Push the current number onto the stack.
6. If all numbers are processed without violations, return true.

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

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the length of preorder

---

2. Constant Auxiliary Space

Intuition

We can optimize the stack approach by reusing the input array itself as our stack. Since we process elements left to right and the stack never grows larger than the elements we have processed, we can use the prefix of the preorder array to simulate the stack.

Algorithm

1. Initialize min_limit to negative infinity and use index i as the stack pointer.
2. Iterate through each number in the preorder sequence.
3. While i > 0 and preorder[i-1] is less than the current number, set min_limit to preorder[i-1] and decrement i.
4. If the current number is less than or equal to min_limit, return false.
5. Write the current number to preorder[i] and increment i to simulate pushing onto the stack.
6. Return true if all numbers are processed without violations.

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        min_limit = float('-inf') 
        i = 0
        
        for num in preorder:
            while i > 0 and preorder[i - 1] < num:
                min_limit = preorder[i - 1]
                i -= 1
                
            if num <= min_limit:
                return False
            
            preorder[i] = num
            i += 1
        
        return True

Time & Space Complexity

• Time complexity: $O(n)$

• Space complexity: $O(1)$ auxiliary

  • A common misconception is that modifying an input array for use in an algorithm leads to an $O(1)$ space complexity. In reality, you are still using $O(n)$ space, but $O(1)$ auxiliary space.

  • Because we are modifying the input to directly use in the algorithm, we must count it as part of the space complexity. However, we are not using any auxiliary space other than a few integers.
    The exception to this is in-place algorithms where the input is also returned as the output. For example: sorting algorithms.

Where $n$ is the length of preorder

---

3. Recursion

Intuition

We can verify the preorder sequence by simulating the construction of the BST. Each recursive call attempts to build a subtree within given bounds. The key insight is that for a valid preorder sequence, we can greedily consume elements that fall within the current subtree's valid range, recursively processing left and right subtrees.

Algorithm

1. Maintain a global index to track the current position in the preorder array.
2. Create a recursive helper function that takes min_limit and max_limit as boundaries.
3. If the index reaches the end, return true as all elements have been processed.
4. Check if the current element falls within the valid range. If not, return false.
5. Increment the index and recursively verify the left subtree (with max_limit as current value) and right subtree (with min_limit as current value).
6. Return true if either the left or right subtree verification succeeds, allowing the sequence to be valid.

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        def helper(i, min_limit, max_limit):
            if i[0] == len(preorder):
                return True
            
            root = preorder[i[0]]
            if not min_limit < root < max_limit:
                return False

            i[0] += 1
            left = helper(i, min_limit, root)
            right = helper(i, root, max_limit)
            return left or right
            
        return helper([0], float('-inf'), float('inf'))

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the length of preorder

---

Common Pitfalls

Using Wrong Comparison Operator

When checking if a value violates BST constraints, you must use less than or equal (<=) for the minimum limit check, not just less than. BSTs typically do not allow duplicate values, so a value equal to an ancestor it should be greater than is invalid.

Misunderstanding When to Update the Minimum Limit

The minimum limit should only be updated when you pop elements from the stack (transitioning to a right subtree). A common mistake is updating the limit at the wrong time, such as when pushing elements. The limit represents the most recently left ancestor whose right subtree you are now in.

Not Maintaining a Decreasing Stack

The stack should maintain a decreasing order from bottom to top. When you encounter a larger value, you pop smaller values to find the correct parent. Forgetting to maintain this invariant or popping incorrectly will cause the algorithm to fail on valid preorder sequences.