Verify Preorder Sequence in Binary Search Tree

Problem: Verify Preorder Sequence in Binary Search Tree

In preorder of binary search tree, if a number is bigger than its previous number, all its following numbers should be smaller than the previous number. However, previous number is not enough. We need to find root node which split these two subtrees.

Code in Python:

class Solution(object):
    def verifyPreorder(self, preorder):
        """
        :type preorder: List[int]
        :rtype: bool
        """
        stack = []
        min = -1 << 31
        for number in preorder:
            if number < min: return False
            while stack and number > stack[-1]:
                min = stack.pop()
            stack.append(number)
        return True