Prerequisites
Before attempting this problem, you should be comfortable with:
- Binary Search Tree Properties - Understanding that left subtree values are less than root and right subtree values are greater
- Preorder Traversal - Knowing the order of visiting nodes (root, left subtree, right subtree)
- Monotonic Stack - Using a stack that maintains increasing or decreasing order to track ancestors
- Recursion with Bounds - Validating BST nodes by passing min/max constraints through recursive calls
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
- Initialize a stack and set
min_limitto negative infinity. - Iterate through each number in the
preordersequence. - While the stack is not empty and the stack top is less than the current number, pop from the stack and update
min_limitto the popped value. - If the current number is less than or equal to
min_limit, returnfalseas it violates BST property. - Push the current number onto the stack.
- If all numbers are processed without violations, return
true.
Time & Space Complexity
- Time complexity:
- Space complexity:
Where 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
- Initialize
min_limitto negative infinity and use indexias the stack pointer. - Iterate through each number in the
preordersequence. - While
i > 0andpreorder[i-1]is less than the current number, setmin_limittopreorder[i-1]and decrementi. - If the current number is less than or equal to
min_limit, returnfalse. - Write the current number to
preorder[i]and incrementito simulate pushing onto the stack. - Return
trueif 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 TrueTime & Space Complexity
- Time complexity:
- Space complexity: auxiliary
A common misconception is that modifying an input array for use in an algorithm leads to an space complexity. In reality, you are still using space, but 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 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
- Maintain a global index to track the current position in the
preorderarray. - Create a recursive helper function that takes
min_limitandmax_limitas boundaries. - If the index reaches the end, return
trueas all elements have been processed. - Check if the current element falls within the valid range. If not, return
false. - Increment the index and recursively verify the left subtree (with
max_limitas current value) and right subtree (withmin_limitas current value). - Return
trueif 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:
- Space complexity:
Where 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.