⚡Flashcard Drill➔
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

  1. 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.
  2. Maintain a stack of ancestors and low, the lower bound for all subsequent values.
  3. When the current value exceeds the stack top, pop: each popped value becomes the new low, because everything after it must be larger.
  4. 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 < low check: the lower bound is what distinguishes a valid BST pre-order from an arbitrary decreasing sequence.
  • Popping with <=: values are unique, so either works, but while st and st[-1] < v is 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems