#NEWLINE# def verifyPreorder( self , preorder ) : #NEWLINE# #INDENT# '\n        * Draw a valid BST, and swap a pair of nodes to get an invalid BST.\n        * Get the preorder traversal of the 2 BSTs and compare and contrast them.\n        * For tree traversal, a stack or a queue is normally involved.\n        :type preorder:List[int]\n        :rtype: bool\n        ' #NEWLINE# left_finished = None #NEWLINE# stk = [ ] #NEWLINE# for num in preorder : #NEWLINE# #INDENT# if ( left_finished and ( num < left_finished ) ) : #NEWLINE# #INDENT# return False #NEWLINE# #UNINDENT# while ( stk and ( stk [ ( - 1 ) ] < num ) ) : #NEWLINE# #INDENT# left_finished = stk . pop ( ) #NEWLINE# #UNINDENT# stk . append ( left_finished ) #NEWLINE# #UNINDENT# return True