# LeetCode 255: Verify Preorder Sequence in Binary Search Tree ## Problem Restatement We are given an array of unique integers called `preorder`. We need to decide whether this array could be the preorder traversal of a binary search tree. In preorder traversal, nodes are visited in this order: 1. Visit root. 2. Visit left subtree. 3. Visit right subtree. For a binary search tree: | Position | Rule | |---|---| | Left subtree | Values are smaller than the root | | Right subtree | Values are larger than the root | The problem asks us to return `True` if the sequence is valid, otherwise return `False`. The input values are unique. The constraints are `1 <= preorder.length <= 10^4` and `1 <= preorder[i] <= 10^4`. The follow-up asks whether we can do it using constant extra space. ## Input and Output | Item | Meaning | |---|---| | Input | A list of unique integers `preorder` | | Output | `True` or `False` | | Traversal | Root, left subtree, right subtree | | Goal | Check whether some BST can produce this preorder sequence | Example function shape: ```python def verifyPreorder(preorder: list[int]) -> bool: ... ``` ## Examples Example 1: ```python preorder = [5, 2, 1, 3, 6] ``` This is valid. It can represent this BST: ```text 5 / \ 2 6 / \ 1 3 ``` The preorder traversal is: ```python [5, 2, 1, 3, 6] ``` Answer: ```python True ``` Example 2: ```python preorder = [5, 2, 6, 1, 3] ``` This is invalid. After visiting `6`, we have entered the right subtree of `5`. Any later value must be greater than `5`. But `1` appears after `6`, and `1 < 5`. Answer: ```python False ``` ## First Thought: Recursively Check Ranges A BST preorder sequence can be checked with bounds. When we visit a root value: ```python root ``` the left subtree must contain values in: ```python (lower, root) ``` and the right subtree must contain values in: ```python (root, upper) ``` So we can recursively consume values while they fit the current valid range. This works, but it uses recursion and needs careful index handling. ## Problem With Direct Recursion Recursive validation is correct, but the stack depth can become large for a skewed tree. For example: ```python preorder = [1, 2, 3, 4, 5] ``` This represents a BST where every node goes to the right. The recursion depth can become `O(n)`. We can solve the same problem iteratively using a stack. ## Key Insight While scanning preorder from left to right, we move through the BST in preorder order. The hard moment is knowing when we leave a left subtree and enter a right subtree. Consider: ```python preorder = [5, 2, 1, 3, 6] ``` Scan values: ```text 5 -> 2 -> 1 ``` These keep going left. When we see `3`, it is larger than `1`, so we move up from `1`. It is also larger than `2`, so we move up from `2`. Now `3` belongs to the right subtree of `2`. That means all later values in this subtree must be greater than `2`. We track this requirement with a variable called `lower`. `lower` means: > Every future value must be greater than this value. Whenever we pop from the stack, we have finished that node's left side and moved into its right side. The popped value becomes the new lower bound. ## Algorithm Use: ```python stack = [] lower = -inf ``` Then scan each value `x` in `preorder`. For each `x`: 1. If `x < lower`, return `False`. 2. While the stack is non-empty and `x > stack[-1]`: - Pop from the stack. - Set `lower` to the popped value. 3. Push `x` onto the stack. If the loop finishes, return `True`. ## Walkthrough Use: ```python preorder = [5, 2, 1, 3, 6] ``` Start: ```python stack = [] lower = -inf ``` Read `5`. ```python stack = [5] lower = -inf ``` Read `2`. `2` is smaller than `5`, so it is still in the left subtree. ```python stack = [5, 2] lower = -inf ``` Read `1`. `1` is smaller than `2`, so it continues left. ```python stack = [5, 2, 1] lower = -inf ``` Read `3`. `3 > 1`, so pop `1`. ```python lower = 1 stack = [5, 2] ``` `3 > 2`, so pop `2`. ```python lower = 2 stack = [5] ``` Now `3 < 5`, so stop. Push `3`. ```python stack = [5, 3] lower = 2 ``` Read `6`. `6 > 3`, so pop `3`. ```python lower = 3 stack = [5] ``` `6 > 5`, so pop `5`. ```python lower = 5 stack = [] ``` Push `6`. ```python stack = [6] lower = 5 ``` No value violates the lower bound, so the sequence is valid. Now use the invalid example: ```python preorder = [5, 2, 6, 1, 3] ``` After reading `6`, we pop `2` and `5`. ```python lower = 5 stack = [6] ``` Now read `1`. Since: ```python 1 < lower ``` the value `1` tries to appear inside the right subtree of `5`, but it is smaller than `5`. So the sequence is invalid. ## Correctness The stack stores a path of ancestors whose right subtree has not yet been fully entered. The values in the stack represent nodes we may still attach future values under. When the current value is greater than the top of the stack, we have finished the left subtree of that stack node and moved into its right subtree. We pop that node and set it as the lower bound. The lower bound records the most recent ancestor for which we have entered the right subtree. From that point forward, every value must be greater than this ancestor. If a later value is smaller than the lower bound, it would have to belong to the left side of an ancestor whose right side has already started, which violates preorder traversal of a BST. If no value violates the lower bound, every number can be placed consistently into the BST preorder structure. Therefore the sequence is valid. ## Complexity | Metric | Value | Why | |---|---|---| | Time | `O(n)` | Each value is pushed and popped at most once | | Space | `O(n)` | The stack may store all values in a decreasing sequence | ## Implementation ```python class Solution: def verifyPreorder(self, preorder: list[int]) -> bool: stack = [] lower = float("-inf") for x in preorder: if x < lower: return False while stack and x > stack[-1]: lower = stack.pop() stack.append(x) return True ``` ## Code Explanation The variable `lower` stores the minimum allowed value for future nodes: ```python lower = float("-inf") ``` At first, there is no lower bound. For each value: ```python for x in preorder: ``` we check whether it violates the current lower bound: ```python if x < lower: return False ``` If it does, then the sequence cannot be a valid BST preorder traversal. Next, we pop smaller ancestors: ```python while stack and x > stack[-1]: lower = stack.pop() ``` Each pop means we have moved from a node's left side into its right side. Finally, we push the current value: ```python stack.append(x) ``` If all values pass the check, the preorder sequence is valid. ## Constant Space Version The follow-up asks for constant extra space. We can use the input array itself as the stack. The variable `top` acts like the stack pointer. ```python class Solution: def verifyPreorder(self, preorder: list[int]) -> bool: lower = float("-inf") top = -1 for x in preorder: if x < lower: return False while top >= 0 and x > preorder[top]: lower = preorder[top] top -= 1 top += 1 preorder[top] = x return True ``` This modifies the input list, so use it only when mutation is allowed. ## Testing ```python def run_tests(): s = Solution() assert s.verifyPreorder([5, 2, 1, 3, 6]) is True assert s.verifyPreorder([5, 2, 6, 1, 3]) is False assert s.verifyPreorder([1]) is True assert s.verifyPreorder([1, 2, 3, 4, 5]) is True assert s.verifyPreorder([5, 4, 3, 2, 1]) is True assert s.verifyPreorder([8, 5, 1, 7, 10, 12]) is True assert s.verifyPreorder([8, 5, 1, 10, 7, 12]) is False print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | `[5, 2, 1, 3, 6]` | Valid balanced example | | `[5, 2, 6, 1, 3]` | Value violates lower bound | | Single value | Always valid | | Increasing sequence | All right children | | Decreasing sequence | All left children | | Mixed valid tree | Normal BST structure | | Mixed invalid tree | Detects value placed in wrong subtree |