Дата публикации: 15-05-2026 21:00:07

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) --
Related posts:
Algorithms to Detect Pattern of Length M Repeated K or More Times in a String Given an array of positive integers arr, find a pattern of length m that is...
How to Compute the Number of Pawns-Captures for Rook in Chess? On an 8 x 8 chessboard, there is one white rook. There also may be...
Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
How to Reverse a Linked List in C/C++? A Singly Linked List is a one-direction List that uses a pointer to connect between...
The 24 Game Algorithm using Depth First Search You have 4 cards each containing a number from 1 to 9. You need to...
Compute the Number Spiral Diagonals Starting with the number 1 and moving to the right in a clockwise direction a...
How to Optimize WordPress Website for Speed? One of the main problems that website owners face is slow loading times and poor...

Основное содержимое страницы с новостью.

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

True

      5
     / \
    2   6
   / \
  1   3

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

False

6

5

1

root -> left subtree -> right subtree

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

if prev_root and item < prev_root:

0

if lower_bound is not None and value < lower_bound:

[5, 2, 1, 3, 6]

stack = []
lower_bound = None

5

stack = [5]

2

2 < 5

stack = [5, 2]

1

1 < 2

stack = [5, 2, 1]

3

3 > 1

1

lower_bound = 1
stack = [5, 2]

3 > 2

2

lower_bound = 2
stack = [5]

3 < 5

3

stack = [5, 3]
lower_bound = 2

2

2

6

6 > 3

3

lower_bound = 3
stack = [5]

6 > 5

5

lower_bound = 5
stack = []

6

stack = [6]

True

[5, 2, 6, 1, 3]

5

stack = [5]

2

stack = [5, 2]

6

6 > 2

2

lower_bound = 2
stack = [5]

6 > 5

5

lower_bound = 5
stack = []

6

stack = [6]

5

5

1

1 < lower_bound
1 < 5

False

O(n)

O(n)

[5, 4, 3, 2, 1]

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

i

stack.append(value)

i += 1
preorder[i] = value

stack.pop()

lower_bound = preorder[i]
i -= 1

Схожие новости