Check if the given array can represent Level Order Traversal of Binary Search Tree | Java implementation to check if the given array can represent Level Order Traversal of Binary Search Tree ; to store details of a node like node ' s ▁ data , ▁ ' min ' ▁ and ▁ ' max ' ▁ to ▁ obtain ▁ the ▁ range ▁ of ▁ values ▁ where ▁ node ' s left and right child 's should lie ; function to check if the given array can represent Level Order Traversal of Binary Search Tree ; if tree is empty ; queue to store NodeDetails ; index variable to access array elements ; node details for the root of the BST ; until there are no more elements in arr [ ] or queue is not empty ; extracting NodeDetails of a node from the queue ; check whether there are more elements in the arr [ ] and arr [ i ] can be left child of ' temp . data ' or not ; Create NodeDetails for newNode and add it to the queue ; check whether there are more elements in the arr [ ] and arr [ i ] can be right child of ' temp . data ' or not ; Create NodeDetails for newNode and add it to the queue ; given array represents level order traversal of BST ; given array do not represent level order traversal of BST ; Driver code
import java . util . * ; class Solution { static class NodeDetails { int data ; int min , max ; } ; static boolean levelOrderIsOfBST ( int arr [ ] , int n ) { if ( n == 0 ) return true ; Queue < NodeDetails > q = new LinkedList < NodeDetails > ( ) ; int i = 0 ; NodeDetails newNode = new NodeDetails ( ) ; newNode . data = arr [ i ++ ] ; newNode . min = Integer . MIN_VALUE ; newNode . max = Integer . MAX_VALUE ; q . add ( newNode ) ; while ( i != n && q . size ( ) > 0 ) { NodeDetails temp = q . peek ( ) ; q . remove ( ) ; newNode = new NodeDetails ( ) ; if ( i < n && ( arr [ i ] < ( int ) temp . data && arr [ i ] > ( int ) temp . min ) ) { newNode . data = arr [ i ++ ] ; newNode . min = temp . min ; newNode . max = temp . data ; q . add ( newNode ) ; } newNode = new NodeDetails ( ) ; if ( i < n && ( arr [ i ] > ( int ) temp . data && arr [ i ] < ( int ) temp . max ) ) { newNode . data = arr [ i ++ ] ; newNode . min = temp . data ; newNode . max = temp . max ; q . add ( newNode ) ; } } if ( i == n ) return true ; return false ; } public static void main ( String args [ ] ) { int arr [ ] = { 7 , 4 , 12 , 3 , 6 , 8 , 1 , 5 , 10 } ; int n = arr . length ; if ( levelOrderIsOfBST ( arr , n ) ) System . out . print ( " Yes " ) ; else System . out . print ( " No " ) ; } }