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:

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

Example function shape:

def verifyPreorder(preorder: list[int]) -> bool:
    ...

Examples

Example 1:

preorder = [5, 2, 1, 3, 6]

This is valid.

It can represent this BST:

    5
   / \
  2   6
 / \
1   3

The preorder traversal is:

[5, 2, 1, 3, 6]

Answer:

True

Example 2:

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:

False

First Thought: Recursively Check Ranges

A BST preorder sequence can be checked with bounds.

When we visit a root value:

root

the left subtree must contain values in:

(lower, root)

and the right subtree must contain values in:

(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:

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:

preorder = [5, 2, 1, 3, 6]

Scan values:

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:

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:

preorder = [5, 2, 1, 3, 6]

Start:

stack = []
lower = -inf

Read 5.

stack = [5]
lower = -inf

Read 2.

2 is smaller than 5, so it is still in the left subtree.

stack = [5, 2]
lower = -inf

Read 1.

1 is smaller than 2, so it continues left.

stack = [5, 2, 1]
lower = -inf

Read 3.

3 > 1, so pop 1.

lower = 1
stack = [5, 2]

3 > 2, so pop 2.

lower = 2
stack = [5]

Now 3 < 5, so stop.

Push 3.

stack = [5, 3]
lower = 2

Read 6.

6 > 3, so pop 3.

lower = 3
stack = [5]

6 > 5, so pop 5.

lower = 5
stack = []

Push 6.

stack = [6]
lower = 5

No value violates the lower bound, so the sequence is valid.

Now use the invalid example:

preorder = [5, 2, 6, 1, 3]

After reading 6, we pop 2 and 5.

lower = 5
stack = [6]

Now read 1.

Since:

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

Implementation

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:

lower = float("-inf")

At first, there is no lower bound.

For each value:

for x in preorder:

we check whether it violates the current lower bound:

if x < lower:
    return False

If it does, then the sequence cannot be a valid BST preorder traversal.

Next, we pop smaller ancestors:

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:

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.

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

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: