Check if a binary tree is sorted level | Python3 program to determine whether binary tree is level sorted or not . ; Function to create new tree node . ; Function to determine if given binary tree is level sorted or not . ; to store maximum value of previous level . ; to store minimum value of current level . ; to store maximum value of current level . ; to store number of nodes in current level . ; queue to perform level order traversal . ; find number of nodes in current level . ; traverse current level and find minimum and maximum value of this level . ; if minimum value of this level is not greater than maximum value of previous level then given tree is not level sorted . ; maximum value of this level is previous maximum value for next level . ; Driver Code ; 1 / 4 \ 6 / \ 8 9 / \ 12 10
from queue import Queue NEW_LINE class newNode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def isSorted ( root ) : NEW_LINE INDENT prevMax = - 999999999999 NEW_LINE minval = None NEW_LINE maxval = None NEW_LINE levelSize = None NEW_LINE q = Queue ( ) NEW_LINE q . put ( root ) NEW_LINE while ( not q . empty ( ) ) : NEW_LINE INDENT levelSize = q . qsize ( ) NEW_LINE minval = 999999999999 NEW_LINE maxval = - 999999999999 NEW_LINE while ( levelSize > 0 ) : NEW_LINE INDENT root = q . queue [ 0 ] NEW_LINE q . get ( ) NEW_LINE levelSize -= 1 NEW_LINE minval = min ( minval , root . key ) NEW_LINE maxval = max ( maxval , root . key ) NEW_LINE if ( root . left ) : NEW_LINE INDENT q . put ( root . left ) NEW_LINE DEDENT if ( root . right ) : NEW_LINE INDENT q . put ( root . right ) NEW_LINE DEDENT DEDENT if ( minval <= prevMax ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT prevMax = maxval NEW_LINE DEDENT return 1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 1 ) NEW_LINE root . left = newNode ( 4 ) NEW_LINE root . left . right = newNode ( 6 ) NEW_LINE root . left . right . left = newNode ( 8 ) NEW_LINE root . left . right . right = newNode ( 9 ) NEW_LINE root . left . right . left . left = newNode ( 12 ) NEW_LINE root . left . right . right . right = newNode ( 10 ) NEW_LINE if ( isSorted ( root ) ) : NEW_LINE INDENT print ( " Sorted " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not ▁ sorted " ) NEW_LINE DEDENT DEDENT