Check Postordered Array Forms a BST - Algorithms and Problem SolvingAlgorithms and Problem Solving

Check Postordered Array Forms a BST - Algorithms and Problem SolvingAlgorithms and Problem Solving

Given an array that contains a Post order traversal of a Binary Tree. Check if a possible Binary Tree formed from the postorder traversal is a Binary Search Tree.

For example, a1=[1, 3, 4, 2, 7, 6, 5] is a BST but a2=[1, 3, 4, 6, 7, 2, 5] is not a BST.

public static boolean isBSTPostOrder(int[] a, int p, int q){
 int n = q-p+1;;
 //base case always true for 1 element
 if(n < 2){
  return true;
 }
 
 //partition into left subtree a[p..right-1] and right subtree a[right..q-1]
 int right = p;
 while(a[right] < a[q]) right++;
 
 //check validity of right subtree
 int i = right;
 while(i < q && a[i] > a[q]) i++;
 if(i < q){
  return false;
 }
 
 return isBSTPostOrder(a, p, right-1) && isBSTPostOrder(a, right, q-1);
}

Read full article from Check Postordered Array Forms a BST - Algorithms and Problem SolvingAlgorithms and Problem Solving