LEETCODE 255VERIFY PREORDER SEQUENCE IN BINARY SEARCH TREE

"""
Question:
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.

Follow up:
Could you do it using only constant space complexity?
"""

class Solution():
    def verifyPreorder(self,preorder):
        
        # keep visiting the array till one is greater than the last
        # then go back find the cutoff point in the array which is just smaller than the value last visited
        # then remove all values (left to the cutoff) smaller than the cutoff and the cutoff itself
        # therefore, if it is from BST, the future value should all on the right side of the cutoff 
        # if not (i.e.) a value is smaller than the cutoff value, then the array is not from BST
        
        low = -float('Inf')
        i = -1
        
        for p in preorder:
            if p < low:
                return False 
            
            if p > preorder[i]:
            	while i>=0 and p > preorder[i]:
                    low = preorder[i]
                    i -=1

i+=1
            preorder[i] = p
            
        
        return True

Browser Version Not Supported

Due to Python Fiddle's reliance on advanced JavaScript techniques, older browsers might have problems running it correctly. Please download the latest version of your favourite browser.
Chrome 10+ Firefox 4+ Safari 5+
IE 10+

Let me try anyway!

Python Fiddle

Python Cloud IDE