👨‍💻 738LeetCode

Binary Search Tree Post Order

Question

Given an int array, check if t can be the result of a post-order traversal of a binary search tree. No repeated numbers. Empty array returns false.

Solution

class Solution:
    def isPostOrder(self, arr):
        def helper(arr):
            if not arr:
                return False

            root = arr[-1]
            # Find the first greater value to split arr
            for i in range(len(arr)):
                if arr[i] > root:
                    break
            for j in range(i, len(arr)):
                if arr[j] < root:
                    return False

            left = helper(arr[:i]) if i > 0 else True
            right = helper(arr[i:]) if i < len(arr) - 1 else True
            return left and right


        return helper(arr)

Comment

  • Binary Search Tree must follow: L < curr < R.
  • Post order: L R root
  • There exists an O(N) solution.