255. Verify Preorder Sequence in Binary Search Tree (Python)

Related Topic

Stack .

Description

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Consider the following binary search tree:

     5
    / \
   2   6
  / \
 1   3

Sample I/O

Example 1

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

Example 2

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

Follow up:

Could you do it using only constant space complexity?

Methodology

Kinda simulate the traversal, keeping a stack of nodes (just their values) of which we’re still in the left subtree. If the next number is smaller than the last stack value, then we’re still in the left subtree of all stack nodes, so just push the new one onto the stack. But before that, pop all smaller ancestor values, as we must now be in their right subtrees (or even further, in the right subtree of an ancestor). Also, use the popped values as a lower bound, since being in their right subtree means we must never come across a smaller number anymore.

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

BigO

We iterate the list once so the total cost will be O(n)