Check if the given array can represent Level Order Traversal of Binary Search Tree | C ++ 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 program to test above
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct NodeDetails { int data ; int min , max ; } ; bool levelOrderIsOfBST ( int arr [ ] , int n ) { if ( n == 0 ) return true ; queue < NodeDetails > q ; int i = 0 ; NodeDetails newNode ; newNode . data = arr [ i ++ ] ; newNode . min = INT_MIN ; newNode . max = INT_MAX ; q . push ( newNode ) ; while ( i != n && ! q . empty ( ) ) { NodeDetails temp = q . front ( ) ; q . pop ( ) ; if ( i < n && ( arr [ i ] < temp . data && arr [ i ] > temp . min ) ) { newNode . data = arr [ i ++ ] ; newNode . min = temp . min ; newNode . max = temp . data ; q . push ( newNode ) ; } if ( i < n && ( arr [ i ] > temp . data && arr [ i ] < temp . max ) ) { newNode . data = arr [ i ++ ] ; newNode . min = temp . data ; newNode . max = temp . max ; q . push ( newNode ) ; } } if ( i == n ) return true ; return false ; } int main ( ) { int arr [ ] = { 7 , 4 , 12 , 3 , 6 , 8 , 1 , 5 , 10 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; if ( levelOrderIsOfBST ( arr , n ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }