Verify Preorder Sequence in Binary Search Tree

How it works

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.

Steps

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.

Complexity

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

Where n is the length of preorder

Things to watch for

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.

from typing import List

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

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        int i = 0;
        return helper(preorder, i, INT_MIN, INT_MAX);
    }

    bool helper(vector<int>& preorder, int& i, int minLimit, int maxLimit) {
        if (i == preorder.size()) {
            return true;
        }

        int root = preorder[i];
        if (root <= minLimit || root >= maxLimit) {
            return false;
        }

        i++;
        bool left = helper(preorder, i, minLimit, root);
        bool right = helper(preorder, i, root, maxLimit);
        return left || right;
    }
};