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

problem: given array of integers, determine if can postorder traversal sequence of bst. ex: [5, 7, 6, 9, 11, 10, 8] returns true, [7, 4, 6, 5] returns false.

i'm wondering if can in linear time. here solutions n^2 , nlgn came with.

n^2 solution: scan through array , check root's left , right subtree values smaller , larger root's value respectively. repeat each subtree.

nlgn solution: build bst going right left of input array. keep track of max number can encounter @ point. max number updates parent node every time insert left child. if ever try insert node greater tracked max number, can return false.

here's linear-time algorithm that's simpler last revision of answer.

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

one can imagine recursive procedure uses fact root value comes last follows. scan right left until value less root found. split maximal proper prefix of array after value. verify right half recursively. validate values in left half less root , verify half recursively.

the latter recursion in tail position , can converted iteration. check values less root can deferred, since upperbound decreases monotonically on time. keep remains of recursive stack in stack, namely, sequence of root values made non-tail recursion. inner loop determines how of call stack should consider current element. amortized constant time.