Python solution with detailed explanation


  • 0
    G

    Solution

    Verify Preorder Sequence in Binary Search Tree https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/

    Brute Force

    • preOrder range from lo to hi. The first element or preOrder[lo] is the root.
    • The remaining sequence should be partitioned into 2 sequences. One sequence is less than root and the other is more than root. If that doesnt happen, we return False.
    • We then recurse into two sequences and make sure both of them are also valid sequences.
    • This is N^2 at worst and N * Lg (N) at best when we have a balanced tree.
    • The python version TLE but Java version passes the cases.
    class Solution(object):
        def is_preorder(self, preorder, lo, hi):
            if lo >= hi:
                return True
            increasing, j = False, hi+1
            for i in range(lo+1, hi+1):
                if not increasing and preorder[i] > preorder[lo]:
                    increasing, j = True, i
                if increasing and preorder[i] < preorder[lo]:
                    return False
            if increasing == False:
                return self.is_preorder(preorder, lo+1, j-1)
            else:
                return self.is_preorder(preorder, lo+1, j-1) and self.is_preorder(preorder, j, hi)            
    
        def verifyPreorder(self, preorder):
            """
            :type preorder: List[int]
            :rtype: bool
            """
            return self.is_preorder(preorder, 0, len(preorder)-1)
    

    Test if every number is withing bounds

    class Solution(object):
        def is_preorder(self, preorder, s, e, lb, ub):
            if s >= e:
                return True
            j = e+1
            r = preorder[s]
            for i in range(s, e+1):
                if lb <= preorder[i] <= ub:
                    if preorder[i] > r:
                        j = i
                        break
                else:
                    return False
            return self.is_preorder(preorder, s+1, j-1, lb, r-1) and self.is_preorder(preorder, j, e, r+1, ub)            
    
        def verifyPreorder(self, preorder):
            """
            :type preorder: List[int]
            :rtype: bool
            """
            return self.is_preorder(preorder, 0, len(preorder)-1, float('-inf'), float('inf'))
    

    Optimized O(N) Solution

    • Core concept: At any point, we need to figure out the lower bound for all the values yet to be seen or processed. Now how would be manage that? Visualize a BST.
    • Initially that lower bound is -INF.
    • You start pushing all the left most values into a stack. When you find preorder[i] > preorder[i-1], it indicates a right child. We now want to find the predecessor of this right child. The predecessor will serve as new lower bound.
    • How do we find predecessor? Keep popping till you preorder[i] > st[-1].
    • https://discuss.leetcode.com/topic/41210/c-easy-to-understand-solution-with-thought-process-and-detailed-explanation
    class Solution(object):
        def verifyPreorder(self, preorder):
            """
            :type preorder: List[int]
            :rtype: bool
            """
            st = []
            low = float('-inf')
            for x in preorder:
                if x < low:
                    return False
                while st and st[-1] < x:
                    low = st.pop()
                st.append(x)
            return True
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.