NeetCode #406LC-255MediumTreesNC Algo100
← Back to All Problems#406 · #255 · Verify Preorder Sequence in Binary Search Tree(验证前序遍历序列二叉搜索树)
📌 Problem Statement & Constraints
Given an array of unique integers
preorder, return true if it is the pre-order traversal of some binary search tree. Constraints: 1 <= preorder.length <= 10^4, 1 <= preorder[i] <= 10^4.💡 Core Algorithmic Approaches
- In a pre-order traversal of a BST, the values decrease as you go down the left spine and jump up when a right subtree begins.
- Maintain a stack of ancestors and
low, the lower bound for all subsequent values. - When the current value exceeds the stack top, pop: each popped value becomes the new
low, because everything after it must be larger. - If a value is ever below
low, the sequence is not a valid BST pre-order.
💻 Benchmark Python3 Implementation
class Solution:
def verifyPreorder(self, preorder: List[int]) -> bool:
st = []
low = float("-inf") # all remaining values must exceed this
for v in preorder:
if v < low:
return False # violates a right-subtree lower bound
while st and st[-1] < v:
low = st.pop() # v starts a right subtree of the popped node
st.append(v)
return True⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each value is pushed and popped at most once.
💾 Space Complexity
O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the
v < lowcheck: the lower bound is what distinguishes a valid BST pre-order from an arbitrary decreasing sequence. - Popping with
<=: values are unique, so either works, butwhile st and st[-1] < vis the standard form. - Trying to reconstruct the tree: unnecessary and O(n) space for the nodes.
- Assuming the array is sorted: it is a pre-order sequence, not a sorted one.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.