Verify Preorder Sequence In Binary Search Tree - Leetcode Solution

The problem "Verify Preorder Sequence in Binary Search Tree" on LeetCode requires us to determine whether a given sequence of numbers represents the preorder traversal of a valid binary search tree.

A binary search tree (BST) is a binary tree where the left subtree of a node contains only nodes with values smaller than the node's value, and the right subtree contains only nodes with values larger than the node's value. The preorder traversal of a BST visits each node in the following order: root, left, right.

Approach:

We can use a stack to keep track of the nodes we've visited so far, and a variable to keep track of the lower bound of values for nodes in the right subtree.

We start by setting the lower bound for right subtree to -infinity, which means that any value we see must be greater than this bound for it to be part of the right subtree. We iterate through the array of numbers representing the preorder traversal, and for each element x:

1. If x is less than the lower bound for the right subtree, then this element cannot be part of the right subtree, so we return false.
2. While the stack is not empty and x is greater than the value of the top element of the stack, we pop elements from the stack and update the lower bound for the right subtree to be the value of the most recently popped element.
3. Push x onto the stack.
4. If we've reached the end of the array, then the preorder sequence represents a valid BST, so we return true.

Code:

Below is the implementation of the above approach in Python.

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        stack = []
        lower_bound = float('-inf')
        for x in preorder:
            if x < lower_bound:
                return False
            while stack and x > stack[-1]:
                lower_bound = stack.pop()
            stack.append(x)
        return True

Time Complexity: O(n), where n is the size of the input array. Space Complexity: O(n), for the stack to keep track of the nodes.

1