NUHMAN.com

Introduction

LeetCode 255: Verify Preorder Sequence in Binary Search Tree asks you to determine whether a given list of numbers could represent the preorder traversal of a valid Binary Search Tree (BST).

This problem tests your understanding of BST properties and traversal logic—especially preorder traversal.

Problem Statement

Given an array of unique integers, determine if it could represent the preorder traversal of a binary search tree.

Example 1:

vbnet

Input: preorder = [5, 2, 1, 3, 6]
Output: True

Example 2:

vbnet

Input: preorder = [5, 2, 6, 1, 3]
Output: False

Understanding the Problem

In preorder traversal, the order is:

sql

[ root, left subtree..., right subtree... ]

A valid BST has the property:

• Left subtree < root
• Right subtree > root

The idea is to simulate the traversal and validate that no number violates the BST rules.

Step-by-Step Solution in Python

✅ Step 1: Use a Stack

• The stack simulates the recursion stack of preorder traversal.
• As we go deeper into the tree, we push nodes onto the stack.
• When we find a node greater than the top of the stack, we’re moving to the right subtree.

✅ Step 2: Track a Lower Bound

• Every time we move to the right, we pop the last smaller node.
• This node becomes the lower bound for the rest of the traversal (all future nodes must be greater than this).

Step 3: Code It

python

def verifyPreorder(preorder: list[int]) -> bool:
    stack = []
    lower_bound = float('-inf')

    for value in preorder:
        # If we find a value less than allowed, return False
        if value < lower_bound:
            return False

        # Find the parent node this value belongs to (going right)
        while stack and value > stack[-1]:
            lower_bound = stack.pop()

        stack.append(value)

    return True

Explanation of the Code

• lower_bound:
• Keeps track of the most recent node we finished visiting on the left. Any future value must be greater than this.
• Popping from stack:
• When the current value is greater than the top of the stack, it indicates we are transitioning to the right subtree.
• Validation:
• If any value is smaller than the current lower bound, it violates BST rules.

Dry Run Example

Input: [5, 2, 1, 3, 6]

• Stack: [], Lower Bound: -inf
• 5 → OK → Stack: [5]
• 2 → OK → Stack: [5, 2]
• 1 → OK → Stack: [5, 2, 1]
• 3 → 3 > 1 → pop 1 → pop 2 → Stack: [5], Lower: 2 → 3 > 2 → OK
• 6 → 6 > 5 → pop 5 → OK → ✅ All valid

Time and Space Complexity

• Time Complexity: O(n)
• Each element is pushed and popped at most once.
• Space Complexity: O(n)
• For the stack in the worst case (completely left-skewed tree).

Conclusion

LeetCode 255 offers a neat and efficient way to validate preorder sequences in BSTs using a greedy stack-based approach. It avoids tree construction and leverages BST and preorder traversal rules.

This is a great interview question for practicing:

• Stack usage
• Tree traversal logic
• Maintaining invariants (like bounds)