Check if Array Represents preorder of BST

Check if Array Represents preorder of BST

  September 14, 2017    

---

Explanation:

Here we will use stack.
Initialize root with min value.

Loop from 1 to arr.length
check if arr[i]<root it means it is voilating property
Pop all the elements from stack who are lesser than arr[i]
Finally push arr[i]


Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class hackerranksolutionc
 {
     public static boolean isBst(int arr[],int n)
     {
         Deque<Integer> q=new ArrayDeque<Integer>();
        // q.add(Integer.MIN_VALUE);
         int i=0;
         int root=Integer.MIN_VALUE;
         for(i=0;i<n;++i)
         {
            if(arr[i]<root)
            return false;
            while(!q.isEmpty() && q.peekFirst()<arr[i])
            {
                root=q.removeFirst();
            }
            q.addFirst(arr[i]);
            
         }
         return true;
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   int n=ab.nextInt();
   int arr[]=new int[n];
   for(int i=0;i<n;i++)
   arr[i]=ab.nextInt();
   System.out.println(isBst(arr,n)?1:0);
}
}
}

Ref

http://www.geeksforgeeks.org/check-if-a-given-array-can-represent-preorder-traversal-of-binary-search-tree/