Teaching Kids Programming: Videos on Data Structures and Algorithms
A stack-based solution for LeetCode 255, Verify Preorder Sequence in Binary Search Tree. The key idea is to track a lower bound: once preorder traversal enters the right subtree of a node, all later values must be greater than that node.
LeetCode 255: Verify Preorder Sequence in Binary Search Tree
LeetCode 255 asks whether a given array of unique integers can be the preorder traversal of a Binary Search Tree.
Given this input:
preorder = [5, 2, 1, 3, 6]
The answer is:
True
Because it can represent this BST:
5
/ \
2 6
/ \
1 3
But for this input:
preorder = [5, 2, 6, 1, 3]
The answer is:
False
Because after visiting
6
, we have already moved into the right subtree of
5
. Seeing
1
afterwards violates the BST rule.
BST Preorder Rule
For a Binary Search Tree:
- All values in the left subtree are smaller than the root.
- All values in the right subtree are greater than the root.
Preorder traversal follows this order:
root -> left subtree -> right subtree
So while scanning the preorder array from left to right, we are effectively simulating the traversal path.
The key observation is:
Once we move into the right subtree of a node, every future value must be greater than that node.
That node becomes a lower bound.
Stack-Based Solution
We use a stack to track the current ancestor path.
When the current value is smaller than the top of the stack, we are still going down the left subtree.
When the current value is greater than the top of the stack, we are moving back up and entering a right subtree.
At that point, we keep popping from the stack.
The last popped value becomes the new lower bound.
Any future value smaller than this lower bound is invalid.
Python Solution
class Solution:
def verifyPreorder(self, preorder: List[int]) -> bool:
stack = []
lower_bound = None
for value in preorder:
if lower_bound is not None and value < lower_bound:
return False
while stack and value > stack[-1]:
lower_bound = stack.pop()
stack.append(value)
return True
Small Improvement Over the Original Code
The original version used this condition:
if prev_root and item < prev_root:
It works for this LeetCode problem because all values are positive.
But in a more general BST problem, values could be
0
or negative.
So this version is safer:
if lower_bound is not None and value < lower_bound:
This avoids relying on Python truthiness.
Walkthrough: Valid Example
Input:
[5, 2, 1, 3, 6]
Start with:
stack = []
lower_bound = None
Read
5
:
stack = [5]
Read
2
:
2 < 5
, so we are going into the left subtree.
stack = [5, 2]
Read
1
:
1 < 2
, still going left.
stack = [5, 2, 1]
Read
3
:
3 > 1
, so pop
1
.
lower_bound = 1
stack = [5, 2]
3 > 2
, so pop
2
.
lower_bound = 2
stack = [5]
Now
3 < 5
, so stop popping and push
3
.
stack = [5, 3]
lower_bound = 2
This means we are now in the right subtree of
2
. Every future value must be greater than
2
.
Read
6
:
6 > 3
, pop
3
.
lower_bound = 3
stack = [5]
6 > 5
, pop
5
.
lower_bound = 5
stack = []
Push
6
.
stack = [6]
No violation is found, so return
True
.
Walkthrough: Invalid Example
Input:
[5, 2, 6, 1, 3]
Read
5
:
stack = [5]
Read
2
:
stack = [5, 2]
Read
6
:
6 > 2
, pop
2
.
lower_bound = 2
stack = [5]
6 > 5
, pop
5
.
lower_bound = 5
stack = []
Push
6
.
stack = [6]
Now we are in the right subtree of
5
.
That means every future value must be greater than
5
.
Read
1
:
1 < lower_bound
1 < 5
This is invalid, so return
False
.
Why This Works
The stack represents the current path of ancestors.
When we see a larger value, we are moving from a left subtree into a right subtree.
Every popped node means:
We have finished this node’s left subtree and are now entering its right subtree.
Therefore, the popped node becomes a lower bound.
If a future value is smaller than this lower bound, the sequence is trying to place a node into the wrong subtree.
That breaks the BST rule.
Time and Space Complexity
Time complexity:
O(n)
Each value is pushed once and popped at most once.
Space complexity:
O(n)
In the worst case, the stack may contain all nodes.
For example:
[5, 4, 3, 2, 1]
Follow-up: Constant Space Solution
The follow-up asks whether we can solve it using only constant extra space.
Yes, we can reuse the input array itself as the stack.
class Solution:
def verifyPreorder(self, preorder: List[int]) -> bool:
lower_bound = float("-inf")
i = -1
for value in preorder:
if value < lower_bound:
return False
while i >= 0 and value > preorder[i]:
lower_bound = preorder[i]
i -= 1
i += 1
preorder[i] = value
return True
Here,
i
is the stack pointer.
Instead of using:
stack.append(value)
We write:
i += 1
preorder[i] = value
Instead of using:
stack.pop()
We write:
lower_bound = preorder[i]
i -= 1
This gives:
- Time complexity:
O(n)
- Extra space complexity:
O(1)
However, this approach modifies the input array.
That is the trade-off.
Final Takeaway
The core idea is simple:
In preorder traversal of a BST, once we enter the right subtree of a node, all future values must be greater than that node.
The stack helps us detect when we enter a right subtree.
The lower bound records the smallest valid value allowed for future nodes.
If any future value is smaller than the lower bound, the preorder sequence cannot represent a valid BST.
–EOF (The Ultimate Computing & Technology Blog) —
1561 wordsLast Post: From Phone Booths to Large Language Models: The Twilight of Traditional Programming
Next Post: AI Coding Agents Are Reshaping the Barrier to Programming