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
class NodeDetails : NEW_LINE INDENT def __init__ ( self , data , min , max ) : NEW_LINE INDENT self . data = data NEW_LINE self . min = min NEW_LINE self . max = max NEW_LINE DEDENT DEDENT def levelOrderIsOfBST ( arr , n ) : NEW_LINE INDENT if n == 0 : NEW_LINE INDENT return True NEW_LINE DEDENT q = [ ] NEW_LINE i = 0 NEW_LINE newNode = NodeDetails ( arr [ i ] , INT_MIN , INT_MAX ) NEW_LINE i += 1 NEW_LINE q . append ( newNode ) NEW_LINE while i != n and len ( q ) != 0 : NEW_LINE INDENT temp = q . pop ( 0 ) NEW_LINE if i < n and ( arr [ i ] < temp . data and arr [ i ] > temp . min ) : NEW_LINE INDENT newNode = NodeDetails ( arr [ i ] , temp . min , temp . data ) NEW_LINE i += 1 NEW_LINE q . append ( newNode ) NEW_LINE DEDENT if i < n and ( arr [ i ] > temp . data and arr [ i ] < temp . max ) : NEW_LINE INDENT newNode = NodeDetails ( arr [ i ] , temp . data , temp . max ) NEW_LINE i += 1 NEW_LINE q . append ( newNode ) NEW_LINE DEDENT DEDENT if i == n : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 7 , 4 , 12 , 3 , 6 , 8 , 1 , 5 , 10 ] NEW_LINE n = len ( arr ) NEW_LINE if levelOrderIsOfBST ( arr , n ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT