How to check if a given array represents postorder traversal of Binary Search Tree?

Question

There is a given array and we need to know if it represents a post-order traversal of BST. (example: if the question was in-order instead of post-order , we only need to check if the array is sorted time o(n))

Answer 1

Postorder traversal is done by {LEFT Subtree}{Right Subtree}{ROOT}. Hence the idea here is to start traversing the array from the right end. The last element in the array is the root, and from Right to left, when you encounter smaller element, that marks the boundary to start with the left subtree, BST won't have a larger element from this index, this applies for each subtree. Algorithm in C++ goes like this -

bool isBST(int arr[], int n){

//Set root to the max integer value.
int root = INT_MAX;

//Stack used to keep track of current subtree
std::stack<int>s;

//Start at the end of the array because Postorder traversal is
// <L><R><D>
for (int i = n-1; i>=0; i--) {
    //False if any larger number in the left subtree
    if (arr[i]> root) {
        return false;
    }

    //Reset the root for boundary of every subtree,
    //when current item is smaller than top,
    //that means we are starting with left subtree of this root
    while (!s.empty() &&  arr[i] < s.top()) {
        root = s.top();
        s.pop();
    }
    //Keep pushing the elements otherwise
    s.push(arr[i]);
  }
  return true;

}

Answer 2

With the following code it can be estimated if the given array can possibly represent a BST or not.

PROCEDURE:

       10
      /  \
     7   12
    / \    \
   6   9    31
           /
          14

let the array be arr={6,9,7,14,31,12,10}

now we start traversing the array from the end till we reach the index with the element less than the end_index (arr[end_index]=10).And we store that that index in temp. (here temp=2 i.e. arr[temp]=7 as 7<10) we traverse again from temp till the start_index. if we find a number greater than 10(element of the last index), we return false.if not ,traverse till the start_index. now we split the array in two halves {6,9,7} and {14,31,12,10}. and follow the same procedure for both.

LOGIC:

post order means {{LEFT elements},{RIGHT elements},{ROOT}}. hence the order of array should be {(elements smaller than parent),(elements greater than parents),(parent) }

and this is what we make sure while traversing the array.

The code is as follows:

public class ckeckIfPostOrderAbinaryTree {

    public static void main(String[] args) {

        int[] arr={6,9,7,14,31,12,10};
        System.out.println(solve(arr,0,arr.length-1));

    }
    public static boolean solve(int[] arr,int strt,int end){
        if(strt>=end){
            return true;
        }

        int x=arr[end],index=end-1;
        while(index>=strt && arr[index]>x){
            index--;
        }
        int temp=index;
        while(index>=strt){
            if(arr[index]>x){
                return false;
            }
            index--;
        }
        if(temp==strt){
            return solve(arr,strt,end-1);
        }
        else{
        return (solve(arr,strt,temp) && solve(arr,temp+1,end-1));
        }
    }

}

Answer 3

Quick sanity check: if the last item in the array isn't the root node then it's not the result of a post-order traversal. Similarly, the first item in an array is the root if a pre-order traversal was done.