Leetcode 255. Verify Preorder Sequence in Binary Search Tree

Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= preorder.length <= 104
• 1 <= preorder[i] <= 104
• All the elements of preorder are unique.

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

DFS is the common way to go, but it may takes O(NlogN). Stack is the best solution for this problem, but it might be hard to realize it.

class Solution:
  def verifyPreorder(self, preorder: List[int]) -> bool:
        return self.dfs(preorder, 0, len(preorder) - 1)
        
  def dfs(self, preorder, start, end):
        if start >= end:
            return True

        root = preorder[start]

        left_tree_root = start + 1
        left_tree_end = start + 1
        
        while left_tree_end <= end and preorder[left_tree_end] < root:
            left_tree_end += 1
        
        for i in range(left_tree_end, end + 1):
            if preorder[i] <= root:
                return False
        
        return self.dfs(preorder, left_tree_root, left_tree_end - 1) and self.dfs(preorder, left_tree_end, end)

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        stack = []
        min_value = -sys.maxsize - 1

        for num in preorder:
            if num < min_value:
                return False
            
            while stack and stack[-1] < num:
                min_value = stack[-1]
                stack.pop()
            
            stack.append(num)
        
        return True