Verify Preorder Sequence in Binary Search Tree solution and explanation
8 more videos on this problem
Valid BST from Preorder | Verify Preorder Sequence in Binary Search TreeFit Coder · 11:36 · 21K views
LeetCode #255 Verify Preorder Sequence in Binary Search Tree (Explanation + Code)NerdsInABarrel · 21:32 · 4K views
LeetCode 255.Verify Preorder Sequence in Binary Search TreeGot Up Late · 5:54 · 1K views
255. Verify Preorder Sequence In Binary Search Tree in C# | LeetCode MediumInterviewPro · 16:20 · 925 views
255. Verify Preorder Sequence in Binary Search Tree - Week 2/5 Leetcode April ChallengeProgramming Live with Larry · 21:10 · 574 views
255. Verify Preorder Sequence in Binary Search Tree - Week 2/5 Leetcode June ChallengeProgramming Live with Larry · 21:10 · 292 views
Leetcode 255. Verify Preorder Sequence in Binary Search Tree(monotonic stack)LetsCode · 10:08 · 77 views
Leetcode 255. Verify Preorder Sequence in Binary Search Tree in Python | Python Leetcode | TutorialCode is Art · 1:38 · 23 views
LeetCode 255: Verify Preorder Sequence in Binary Search TreeAlitaCode · 31:51
The problem
Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree.
Example 1:
Input: preorder = [5,2,1,3,6] Output: true
Example 2:
Input: preorder = [5,2,6,1,3] Output: false
Constraints:
1 <= preorder.length <= 1041 <= preorder[i] <= 104- All the elements of
preorderare unique.
Follow up: Could you do it using only constant space complexity?
Approach overview
Problem Overview: Given an integer array representing a preorder traversal, determine whether it could come from a valid Binary Search Tree (BST). In a BST preorder sequence, each value must respect the BST rule: values in the left subtree are smaller than the root, and values in the right subtree are greater.
Approach 1: Construct the BST and Validate Preorder (O(n log n) time, O(n) space)
Insert each value into a BST following normal insertion rules, then generate the preorder traversal of the constructed tree and compare it with the original array. If both match, the sequence is valid. This approach simulates how the tree would actually form. However, BST insertion may take O(log n) on average but O(n) in the worst case for skewed trees, leading to O(n^2) worst‑case behavior. Useful for understanding the relationship between traversal order and BST structure, but inefficient for interviews.
Approach 2: Recursion with Value Bounds (O(n) time, O(n) space)
Process the preorder array while maintaining valid value ranges for each subtree. Each node must lie within a (min, max) range inherited from its ancestors. The first value becomes the root. Recursively verify that upcoming values fall into the allowed range for the left subtree, then the right subtree. This approach mimics the way preorder traversal builds a BST and ensures each node respects ancestor constraints. It uses recursion stack space proportional to the tree height.
Approach 3: Monotonic Stack with Lower Bound (O(n) time, O(n) space)
The optimal method uses a stack to simulate traversal of the BST while tracking a lower bound. Iterate through the array. When the current value is smaller than the allowed lower bound, the sequence violates BST rules. While the stack top is smaller than the current value, pop elements and update the lower bound because you are moving from a left subtree into a right subtree. Push the current value onto the stack. This stack behaves like a monotonic stack that keeps ancestors whose right subtree hasn't been processed yet.
This technique works because preorder visits nodes in root → left → right order. Once you encounter a value larger than a previous node, you are transitioning into that node's right subtree, and all future values must be greater than it. The algorithm processes each element once, giving linear time complexity.
Recommended for interviews: The monotonic stack approach is the expected solution. It runs in O(n) time with a single pass and demonstrates understanding of preorder traversal properties in a Binary Search Tree. Mentioning the recursive bounds idea first shows conceptual understanding, while implementing the stack solution shows practical optimization skills.
Solution
class Solution:
def verifyPreorder(self, preorder: List[int]) -> bool:
stk = []
last = -inf
for x in preorder:
if x < last:
return False
while stk and stk[-1] < x:
last = stk.pop()
stk.append(x)
return Trueclass Solution {
public boolean verifyPreorder(int[] preorder) {
Deque<Integer> stk = new ArrayDeque<>();
int last = Integer.MIN_VALUE;
for (int x : preorder) {
if (x < last) {
return false;
}
while (!stk.isEmpty() && stk.peek() < x) {
last = stk.poll();
}
stk.push(x);
}
return true;
}
}class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
stack<int> stk;
int last = INT_MIN;
for (int x : preorder) {
if (x < last) return false;
while (!stk.empty() && stk.top() < x) {
last = stk.top();
stk.pop();
}
stk.push(x);
}
return true;
}
};func verifyPreorder(preorder []int) bool {
var stk []int
last := math.MinInt32
for _, x := range preorder {
if x < last {
return false
}
for len(stk) > 0 && stk[len(stk)-1] < x {
last = stk[len(stk)-1]
stk = stk[0 : len(stk)-1]
}
stk = append(stk, x)
}
return true
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Construct BST and Compare Traversal | O(n log n) avg, O(n^2) worst | O(n) | Conceptual understanding of how preorder builds a BST |
| Recursion with Value Bounds | O(n) | O(n) | When modeling subtree constraints using recursion |
| Monotonic Stack with Lower Bound | O(n) | O(n) | Optimal solution for interviews and large inputs |
Frequently asked questions
Is Verify Preorder Sequence in Binary Search Tree easy or hard?
Verify Preorder Sequence in Binary Search Tree is generally considered a medium difficulty problem. The challenge lies in recognizing the preorder traversal pattern of a BST and translating that constraint into a linear stack-based validation algorithm.
Verify Preorder Sequence in Binary Search Tree Python/Java solution
Python and Java implementations typically use a stack to store ancestor values and a variable to track the minimum allowed value. Iterate through the preorder array, pop smaller elements when transitioning to a right subtree, update the lower bound, and push the current value. If any value becomes smaller than the lower bound, return false.
How to solve Verify Preorder Sequence in Binary Search Tree in O(n)?
Traverse the preorder array once while maintaining a stack and a variable that represents the lowest valid value. If the current number is smaller than the allowed lower bound, the sequence is invalid. While the stack contains smaller values, pop them and update the lower bound because the traversal has entered a right subtree. Push the current value onto the stack. This single pass verifies the BST preorder property in linear time.
What is the best approach for Verify Preorder Sequence in Binary Search Tree?
The most efficient approach uses a monotonic stack with a lower bound check. As you scan the preorder array, the stack keeps track of ancestors whose right subtree has not been processed. Whenever a value is larger than the stack top, nodes are popped and the lower bound is updated. This ensures all nodes in the right subtree remain greater than their parent. The algorithm runs in O(n) time.
Is Verify Preorder Sequence in Binary Search Tree asked at Google/Amazon/Meta?
Verify Preorder Sequence in Binary Search Tree appears in interviews at companies that emphasize tree traversal reasoning and stack-based algorithms. Variants of this problem have been reported at companies such as Google, Meta, and Amazon because it tests understanding of BST properties and preorder traversal behavior.
What data structure is used in Verify Preorder Sequence in Binary Search Tree?
The optimal solution relies on a stack to simulate traversal through ancestors while validating BST constraints. The stack helps track nodes whose right subtree has not yet been visited. A lower bound variable ensures that once the traversal enters a right subtree, all future nodes remain greater than the parent value.
What is the time complexity of Verify Preorder Sequence in Binary Search Tree?
The optimal monotonic stack solution runs in O(n) time because each element is pushed and popped from the stack at most once. Space complexity is O(n) in the worst case when the preorder sequence represents a completely decreasing tree. Recursive solutions also run in O(n) time but use recursion stack space proportional to the tree height.