We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Verify Preorder Sequence in Binary Search Tree

Number: 255

Difficulty: Medium

Paid? Yes

Companies: Salesforce, Nvidia, Zenefits

Problem Description

Given an array of unique integers preorder, determine if it is the correct preorder traversal sequence of a Binary Search Tree (BST).

Key Insights

  • A BST has the property that every node's left subtree contains values less than the node, and every right subtree contains values greater.
  • Preorder traversal processes nodes as: root, left subtree, then right subtree.
  • Using a monotonic stack, we can simulate constructing the BST while tracking a lower bound for allowable node values.
  • When moving to a right child, update the lower bound to ensure subsequent nodes are valid.

Space and Time Complexity

Time Complexity: O(n) - Each element is processed once. Space Complexity: O(n) - In the worst-case an explicit stack is used; can be optimized to O(1) by reusing the input array.

Solution

We use a monotonic stack to simulate the BST construction from the preorder sequence. The process is:

  • Initialize a variable lower_bound to -∞.
  • Iterate through each value in the preorder array:
    • If a value is less than lower_bound, it violates BST properties and the sequence is invalid.
    • While the stack is not empty and the current value is greater than the element at the top of the stack, pop from the stack and update lower_bound to the popped value. This simulates moving to the right subtree.
    • Push the current value onto the stack.
  • If the sequence is processed without violations, return true.

This approach efficiently ensures that each value adheres to BST requirements during preorder traversal.

Code Solutions

# Python solution using a monotonic stack with detailed comments
def verifyPreorder(preorder):
    lower_bound = float('-inf')  # Set initial lower bound to negative infinity
    stack = []  # Use a stack to track the BST construction
    for value in preorder:
        # If the current value is less than lower_bound, the BST property is violated
        if value < lower_bound:
            return False
        # If current value is greater than the top of stack, pop elements and update lower_bound
        while stack and value > stack[-1]:
            lower_bound = stack.pop()  # Update lower_bound as we move to the right subtree
        # Push the current value onto the stack
        stack.append(value)
    return True

# Example usage:
# print(verifyPreorder([5,2,1,3,6]))  # Expected output: True
← Back to All Questions