Is there a linear solution to determining whether a postorder sequence is a valid BST?

2
votes

Problem: Given an array of integers, determine if it can be the postorder traversal sequence of a BST. Ex: [5, 7, 6, 9, 11, 10, 8] returns true, but [7, 4, 6, 5] returns false.

I'm wondering if we can do this in linear time. Here are solutions for N^2 and NlgN I came up with.

N^2 solution: Scan through the array and check the root's left and right subtree values are all smaller and larger than the root's value respectively. Repeat for each subtree.

NlgN solution: Build a BST going from right to left of the input array. Keep track of some max number we can encounter at any point. This max number updates to the parent node every time we insert a left child. If we ever try to insert a node greater than the tracked max number, we can return false.

2
performancealgorithmdata-structurestreebinary-search-tree

2 Answers

2
votes

Here's a linear-time algorithm that's much simpler than the last revision of this answer.

def checkbst(lst):
    # stack contains the values of nodes from which the current path departs right
    stack = [float('-inf')]
    # upperbound is the value of the leafmost node from which the path departs left
    upperbound = float('inf')
    for x in reversed(lst):
        # pop stack elements greater than or equal to x
        # stack[-1] is the top
        while stack[-1] >= x:
            upperbound = stack.pop()
        if x >= upperbound:
            return False
        # push
        stack.append(x)
    return True

One can imagine a recursive procedure that uses the fact that the root value comes last as follows. Scan right to left until a value less than the root is found. Split the maximal proper prefix of the array just after that value. Verify the right half recursively. Validate that the values in the left half all are less than the root and then verify that half recursively.

The latter recursion is in tail position and can be converted to iteration. The check that the values are less than the root can be deferred, since the upperbound decreases monotonically over time. We keep what remains of the recursive stack in stack, namely, the sequence of root values from which we made a non-tail recursion. The inner loop determines how much of the call stack should consider the current element. It is amortized constant time.

1
votes

here is the C++ code

bool verifyPostorder(vector<int>& nums)
{
     int high=INT_MAX,index=nums.size();
     for(int j=int(nums.size())-1;j>=0;--j)
  {
       if(nums[j]>high)return false;
       while(i<=int(nums.size())-1 && nums[j]<nums[i])
             high=nums[i++];
       nums[--i]=nums[j];
  }
  return true;

}

you can try to write the verifyPreorder according to this.