LeetCode 255 - Verify Preorder Sequence in Binary Search Tree

Difficulty: 🟡 Medium
Topics: Array, Stack, Tree, Binary Search Tree, Recursion, Monotonic Stack, Binary Tree

Solution

Problem Understanding

The problem gives an array of unique integers called preorder. This array is supposed to represent the preorder traversal of a binary search tree, and we must determine whether such a BST could actually exist.

In a preorder traversal, nodes are visited in this order:

Visit the current node
Traverse the left subtree
Traverse the right subtree

A binary search tree has an additional property:

Every value in the left subtree is smaller than the current node
Every value in the right subtree is larger than the current node

The challenge is to verify whether the given preorder sequence could have been produced by some valid BST.

For example, the sequence [5,2,1,3,6] is valid because we can construct a BST where:

5 is the root
2,1,3 belong to the left subtree
6 belongs to the right subtree

The preorder traversal of that BST matches the input exactly.

However, [5,2,6,1,3] is invalid. Once we visit 6, we have entered the right subtree of 5. Any later value must therefore be greater than 5. The value 1 appears afterward, which violates BST ordering rules.

The constraints tell us several important things:

The array can contain up to 10^4 elements, so exponential or quadratic solutions are risky.
All values are unique, which simplifies BST validation because we never need to handle duplicates.
Values are relatively small integers, but the actual numeric range is not the important part. The ordering relationships matter.

Some important edge cases include:

A single-element array, which is always valid.
A strictly increasing sequence such as [1,2,3,4], which represents a BST where every node only has a right child.
A strictly decreasing sequence such as [4,3,2,1], which represents a BST where every node only has a left child.
Sequences that incorrectly return to a smaller value after entering a right subtree.

Approaches

Brute Force Approach

A brute-force solution tries to recursively rebuild the BST structure from the preorder traversal.

The first element is always the root. Every subsequent value smaller than the root belongs to the left subtree, and every value larger than the root belongs to the right subtree. We can recursively partition the array into left and right sections and verify whether each subtree satisfies BST rules.

This works because preorder traversal naturally divides into:

Root
Left subtree preorder
Right subtree preorder

At each recursive step, we search for the boundary between left and right subtree elements.

Although correct, this approach becomes inefficient because each recursive call may scan a large portion of the array to locate subtree boundaries. In the worst case, such as a strictly increasing or decreasing array, the recursion becomes highly unbalanced and leads to quadratic time complexity.

Optimal Approach

The key insight is that preorder traversal implicitly defines transitions between left and right subtrees.

While scanning the preorder array from left to right:

Values smaller than the current node belong to its left subtree.
Once we encounter a larger value, we move upward in the BST and begin traversing right subtrees.
After entering the right subtree of some ancestor, we can never see a value smaller than that ancestor again.

This observation allows us to maintain a lower bound.

We use a monotonic stack to simulate the traversal path through the BST:

The stack stores ancestors whose right subtree has not yet been fully processed.
Whenever the current value is greater than the stack top, we pop from the stack because we are moving upward and entering right subtrees.
The last popped value becomes the new lower bound.
If we ever encounter a value smaller than the lower bound, the preorder sequence is invalid.

This gives a linear-time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Recursively partitions preorder array
Optimal	O(n)	O(n)	Uses monotonic stack and lower bound tracking

Algorithm Walkthrough

Initialize an empty stack.

The stack represents the path of ancestors we are currently traversing in the BST. It helps us determine when we move from a left subtree into a right subtree. 2. Initialize a variable called lower_bound to negative infinity.

This variable tracks the smallest value that future nodes are allowed to have. Once we move into the right subtree of a node, all future values must be greater than that node. 3. Iterate through each value in the preorder array.

We process values exactly in preorder traversal order. 4. Check whether the current value violates the BST property.

If the current value is smaller than lower_bound, return False.

This means we already entered the right subtree of some ancestor, so seeing a smaller value is impossible in a valid BST. 5. While the stack is not empty and the current value is greater than the stack top, pop from the stack.

Popping means we are moving upward from a left subtree into a right subtree.

The popped value becomes the new lower_bound because all future values must be greater than it. 6. Push the current value onto the stack.

This value may later become an ancestor whose right subtree we enter. 7. If the entire array is processed without violations, return True.

Why it works

The algorithm maintains a critical invariant:

Every value processed must be greater than lower_bound.
The stack always contains a decreasing sequence of ancestors whose right subtree has not yet been fully traversed.

When we pop values from the stack, we are simulating moving upward in the BST and transitioning into right subtrees. Once that happens, all future nodes must remain larger than those popped ancestors. Any violation immediately proves the preorder sequence is impossible.

Python Solution

from typing import List

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        stack = []
        lower_bound = float("-inf")

        for value in preorder:
            if value < lower_bound:
                return False

            while stack and value > stack[-1]:
                lower_bound = stack.pop()

            stack.append(value)

        return True

The implementation closely follows the algorithm described earlier.

The stack simulates the traversal path through the BST. Each element represents an ancestor node that may still have unexplored right children.

The lower_bound variable tracks the minimum allowed value for future nodes. Initially, there is no restriction, so it starts at negative infinity.

For each value:

If it is smaller than lower_bound, the preorder sequence violates BST rules and we immediately return False.
While the current value is larger than the stack top, we pop ancestors from the stack. This simulates moving upward in the tree and entering right subtrees.
Each popped ancestor becomes the new lower bound because future values must remain larger than it.
Finally, we push the current value onto the stack.

If we finish processing every value without detecting a violation, the sequence is valid.

Go Solution

func verifyPreorder(preorder []int) bool {
	stack := []int{}
	lowerBound := -1 << 31

	for _, value := range preorder {
		if value < lowerBound {
			return false
		}

		for len(stack) > 0 && value > stack[len(stack)-1] {
			lowerBound = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
		}

		stack = append(stack, value)
	}

	return true
}

The Go implementation follows the same logic as the Python version.

Slices are used to implement the stack. The last element of the slice represents the top of the stack.

Go does not have built-in negative infinity for integers, so the implementation initializes lowerBound using a very small integer value with -1 << 31.

The stack popping operation is implemented by reslicing:

stack = stack[:len(stack)-1]

This removes the last element efficiently without allocating new memory.

Worked Examples

Example 1

Input:

[5,2,1,3,6]

Current Value	Stack Before	Lower Bound	Action	Stack After
5	[]	-inf	Push 5	[5]
2	[5]	-inf	Push 2	[5,2]
1	[5,2]	-inf	Push 1	[5,2,1]
3	[5,2,1]	-inf	Pop 1, pop 2, update lower bound to 2, push 3	[5,3]
6	[5,3]	2	Pop 3, pop 5, update lower bound to 5, push 6	[6]

No value violated the lower bound, so the answer is True.

Example 2

Input:

[5,2,6,1,3]

Current Value	Stack Before	Lower Bound	Action	Stack After
5	[]	-inf	Push 5	[5]
2	[5]	-inf	Push 2	[5,2]
6	[5,2]	-inf	Pop 2, pop 5, lower bound becomes 5, push 6	[6]
1	[6]	5	1 < 5, invalid	-

Once we entered the right subtree of 5, all future values had to be greater than 5. The value 1 violates that rule, so the answer is False.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is pushed and popped at most once
Space	O(n)	Stack may store all elements in worst case

The time complexity is linear because every value enters the stack exactly once and leaves the stack at most once. No element is revisited unnecessarily.

The space complexity is linear in the worst case. For a strictly decreasing preorder sequence, the stack grows to size n.

Test Cases

from typing import List

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        stack = []
        lower_bound = float("-inf")

        for value in preorder:
            if value < lower_bound:
                return False

            while stack and value > stack[-1]:
                lower_bound = stack.pop()

            stack.append(value)

        return True

solution = Solution()

assert solution.verifyPreorder([5, 2, 1, 3, 6]) is True  # Provided valid example
assert solution.verifyPreorder([5, 2, 6, 1, 3]) is False  # Provided invalid example

assert solution.verifyPreorder([1]) is True  # Single node tree
assert solution.verifyPreorder([1, 2, 3, 4]) is True  # Right-skewed BST
assert solution.verifyPreorder([4, 3, 2, 1]) is True  # Left-skewed BST

assert solution.verifyPreorder([8, 5, 1, 7, 10, 12]) is True  # Balanced valid BST
assert solution.verifyPreorder([8, 5, 1, 10, 7]) is False  # Invalid right subtree value

assert solution.verifyPreorder([10, 5, 2, 6, 12]) is True  # Mixed subtree structure
assert solution.verifyPreorder([10, 5, 12, 4]) is False  # Value violates lower bound

assert solution.verifyPreorder([3, 2, 1]) is True  # Strict descending sequence
assert solution.verifyPreorder([1, 3, 2]) is True  # Small valid mixed case

Test	Why
`[5,2,1,3,6]`	Standard valid preorder traversal
`[5,2,6,1,3]`	Invalid because of lower bound violation
`[1]`	Smallest possible input
`[1,2,3,4]`	Completely right-skewed BST
`[4,3,2,1]`	Completely left-skewed BST
`[8,5,1,7,10,12]`	Typical balanced BST structure
`[8,5,1,10,7]`	Invalid node appears after entering right subtree
`[10,5,2,6,12]`	Valid mixed subtree transitions
`[10,5,12,4]`	Detects invalid return to smaller value
`[3,2,1]`	Deep left recursion pattern
`[1,3,2]`	Small valid preorder with right subtree

Edge Cases

A single-element array is an important edge case because it represents the smallest valid BST possible. Naive implementations that assume both left and right subtrees exist may accidentally fail on this input. The current implementation handles it naturally because the loop runs once and no constraint is violated.

Strictly increasing sequences such as [1,2,3,4,5] are another important case. These correspond to BSTs where every node only has a right child. During processing, the algorithm repeatedly pops from the stack and updates the lower bound. Incorrect stack management often causes bugs here, but the implementation correctly simulates moving through successive right subtrees.

Strictly decreasing sequences such as [5,4,3,2,1] are also significant. These produce BSTs where every node only has a left child. In this scenario, the stack grows continuously and no popping occurs. Some implementations incorrectly assume stack pops are always necessary, but this algorithm correctly handles purely left-skewed trees.

A particularly tricky case occurs when a sequence improperly returns to a smaller value after entering a right subtree, such as [5,2,6,1]. Once 6 is processed, we know we are in the right subtree of 5. The value 1 violates the lower bound requirement. The implementation detects this immediately using the lower_bound check.