//function to check if a given array is BST or Not
boolean canRepresentBST(int pre[])
{
Stack<Integer> s = new Stack<Integer>();
int root = Integer.MIN_VALUE; // Integer.MIN_VALUE=2147483648
// Traverse given array
for (int i = 0; i < pre.length; i++)
{
if (pre[i] < root) /* if current elemnt is less than root*/
{
return false;
}
/*if TOP of the stack is less than the current element
then make the ROOT= TOP and TOP=ELEMENT */
while (!s.empty() && s.peek() < pre[i])
{
root = s.peek();
s.pop();
}
s.push(pre[i]);
}
return true;
}
_______________________________________________________________
_______________________________________________________________
50 30 20 25 10 35 32 36 70 60 55 65 75 72 77
_______________________________________________________________
50
30 70
20 35 60 75
10 25 32 36 55 65 72 77
_______________________________________________________________
50 30 20 25 10 35 32 36 70 60 55 65 75 72 77
Note:
put all the LEFT values in the stack until first right(25)
come to traverse. when first right(25) comes then remove all
the values(10,20) those are less than first right(25) and store
the rest values(25,30,50) in the stack and make the root=20 i.e just less than the
right value(25) and so on...
