LeetCode 255: Verify Preorder Sequence in Binary Search Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 255: Verify Preorder Sequence in Binary Search Tree?

In LeetCode 255: Verify Preorder Sequence in Binary Search Tree, you’re given an array of integers preorder, representing a preorder traversal (root, left, right) of a tree. Your task is to determine if this sequence could come from a valid BST, where for every node, all left subtree values are less than the node, and all right subtree values are greater. This problem builds on BST concepts from challenges like LeetCode 98: Validate Binary Search Tree, but focuses on a sequence rather than a tree structure.

Problem Statement

• Input: An integer array preorder.
• Output: A boolean—true if it’s a valid BST preorder sequence, false otherwise.
• Rules: BST has unique values; left < root < right; preorder is root-first.

Constraints

• Array length: 1 to 10^4.
• Values: -10^5 to 10^5.
• No duplicates in the sequence.

Examples

• Input: preorder = [5,2,6,1,3]
• Output: false (6 > 5, but appears in left subtree).
• Input: preorder = [5,2,1,3,6]
• Output: true (valid BST preorder).
• Input: preorder = [1]
• Output: true (single node is valid).

Understanding the Problem: Validating Preorder

To solve LeetCode 255: Verify Preorder Sequence in Binary Search Tree in Python, we need to check if the given array follows BST rules in a preorder traversal (root, left, right). In a BST:

• Left subtree values < root.
• Right subtree values > root.
• Preorder lists the root first, then left subtree, then right subtree.

A naive approach—building the tree and validating it—takes extra space. We’ll use two methods: 1. Best Solution (Stack-Based Validation): O(n) time—fast and space-efficient. 2. Alternative Solution (Recursive Bounds Checking): O(n) time—clear but more complex.

Let’s dive into the best solution with extra detail for beginners.

Best Solution: Stack-Based Validation

Why This Is the Best Solution

The stack-based validation approach is the top choice for LeetCode 255 because it runs in O(n) time and uses O(h) space (where h is the tree height), efficiently tracking BST properties without rebuilding the tree. It’s beginner-friendly once explained, leveraging a stack to mimic the preorder traversal, making it both fast and practical.

How It Works

Think of this solution as walking through the sequence with a stack of “parents” you’ve seen, like a trail of breadcrumbs. As you move along, you check if each number fits where it should in a BST—smaller numbers go left, bigger ones signal a switch to the right. Here’s how it works, step-by-step, explained simply for beginners:

• Step 1: Understand Preorder:
• In preorder (root, left, right), you see the root first, then all left subtree nodes (smaller), then right subtree nodes (larger).
• For [5, 2, 1, 3, 6], 5 is root, 2, 1, 3 are left, 6 is right.
• Step 2: Use a Stack:
• Start with an empty stack to track nodes you’ve visited but haven’t finished (parents).
• Keep a low variable to mark the smallest value that must be exceeded when switching to a right subtree.
• Step 3: Process Each Number:
• For each number in the array:
• Check Right Subtree Switch: If it’s bigger than the top of the stack (last parent), you’re moving to a right subtree. Pop stack nodes until the top is bigger than the current number, and set low to the last popped value (it’s the root of the subtree you’re leaving).
• Validate: If the number is less than low, it’s in the wrong spot (too small for a right subtree)—return false.
• Add to Stack: Push the number onto the stack (it’s a new parent).
• Step 4: Finish:
• If you process all numbers without issues, return true.

It’s like following a treasure map: the stack keeps your path, and low ensures you don’t backtrack too far!

Step-by-Step Example

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

• Setup: Stack = [], low = -infinity.
• Step-by-Step:
• 5: Stack = [5], low = -inf (root).
• 2: 2 < 5, no pop, Stack = [5, 2], low = -inf (left child).
• 1: 1 < 2, no pop, Stack = [5, 2, 1], low = -inf (left child).
• 3: 3 > 1, pop 1 (3 > 1), Stack = [5, 2], low = 1. 3 < 5, Stack = [5, 2, 3], low = 1 (right of 2).
• 6: 6 > 3, pop 3 (6 > 3), pop 2 (6 > 2), pop 5 (6 > 5), Stack = [], low = 5. Stack = [6], low = 5 (right of root).
• Result: All processed, no violations → true.

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

• Setup: Stack = [], low = -inf.
• Step-by-Step:
• 5: Stack = [5], low = -inf.
• 2: Stack = [5, 2], low = -inf.
• 6: 6 > 2, pop 2, Stack = [5], low = 2. 6 > 5, pop 5, Stack = [], low = 5. Stack = [6], low = 5.
• 1: 1 < 6, but 1 < low = 5—violation (1 can’t be in right subtree after 5).
• Result: false.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        # Step 1: Set up our tools
        stack = []  # Tracks parent nodes
        low = float('-inf')  # Smallest value allowed (starts super low)

        # Step 2: Go through each number
        for num in preorder:
            # Step 3: Check if num is too small
            if num < low:
                # If num is less than the last root we left, it’s wrong
                return False

            # Step 4: Moving to right subtree?
            while stack and num > stack[-1]:
                # Pop until we find a bigger parent or stack is empty
                low = stack.pop()  # Update low to last popped (root we’re done with)

            # Step 5: Add current number as a parent
            stack.append(num)

        # Step 6: All numbers fit!
        return True

• Time Complexity: O(n)—one pass through the array.
• Space Complexity: O(h)—stack size up to tree height.

This solution is like a BST guide—checking each step with a handy stack!

Alternative Solution: Recursive Bounds Checking

Why an Alternative Approach?

The recursive bounds-checking approach splits the sequence into root, left, and right parts, validating each recursively with min/max bounds. It’s less space-efficient but shows the BST structure clearly, making it a good alternative for beginners.

How It Works

Imagine breaking the sequence into chunks: the root, then everything smaller (left), then everything bigger (right). Check each chunk fits BST rules. Here’s how it works, explained simply:

• Step 1: Define Bounds:
• Root sets a min (left must be smaller) and max (right must be bigger).
• Step 2: Recurse:
• Find where left ends and right begins, then check each subtree.
• Step 3: Validate:
• Ensure all values stay within bounds.

Step-by-Step Example

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

• Root 5: Left < 5, Right > 5.
• Left [2,1,3]: All < 5, split at 2.
• Right [6]: All > 5.
• Result: true.

Code for Recursive Approach

Copy codeclass Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        def verify(start, end, min_val, max_val):
            if start >= end:
                return True
            root = preorder[start]
            if root <= min_val or root >= max_val:
                return False
            i = start + 1
            while i < end and preorder[i] < root:
                i += 1
            return verify(start + 1, i, min_val, root) and verify(i, end, root, max_val)

        return verify(0, len(preorder), float('-inf'), float('inf'))

• Time Complexity: O(n)—traverses once.
• Space Complexity: O(h)—recursion stack.

It’s intuitive but heavier.

Comparing the Two Solutions

• Best Solution (Stack):
• Pros: O(n) time, O(h) space, efficient.
• Cons: Stack logic might be new.
• Alternative Solution (Recursive):
• Pros: Clear BST split.
• Cons: O(h) space, more complex.

Stack wins for simplicity.

Additional Examples and Edge Cases

Single Node

• [5] → true

Invalid Order

• [5,6,2] → false

All Left

• [5,4,3] → true

Both handle these well.

Complexity Breakdown

• Stack:
• Time: O(n)—single pass.
• Space: O(h)—stack.
• Recursive:
• Time: O(n)—traversal.
• Space: O(h)—stack.

Stack is leaner.

Key Takeaways for Beginners

• Stack: Tracks parents efficiently.
• Bounds: Enforce BST rules.
• Recursive: Split and check—logical but heavy.
• Python Tip: Stacks are just lists—see [Python Basics](/python/basics).

Final Thoughts: Verify Like a Pro

LeetCode 255: Verify Preorder Sequence in Binary Search Tree in Python is a clever BST challenge. The stack solution offers O(n) efficiency, while recursive bounds provide clarity. Want more? Try LeetCode 98: Validate BST or LeetCode 94: Binary Tree Inorder Traversal. Ready to verify? Head to Solve LeetCode 255 on LeetCode and check those sequences today!