Find if given vertical level of binary tree is sorted or not | Python program to determine whether vertical level l of binary tree is sorted or not . ; Structure of a tree node . ; Helper function to determine if vertical level l of given binary tree is sorted or not . ; If root is null , then the answer is an empty subset and an empty subset is always considered to be sorted . ; Variable to store previous value in vertical level l . ; Variable to store current level while traversing tree vertically . ; Variable to store current node while traversing tree vertically . ; Declare queue to do vertical order traversal . A pair is used as element of queue . The first element in pair represents the node and the second element represents vertical level of that node . ; Insert root in queue . Vertical level of root is 0. ; Do vertical order traversal until all the nodes are not visited . ; Check if level of node extracted from queue is required level or not . If it is the required level then check if previous value in that level is less than or equal to value of node . ; If left child is not NULL then push it in queue with level reduced by 1. ; If right child is not NULL then push it in queue with level increased by 1. ; If the level asked is not present in the given binary tree , that means that level will contain an empty subset . Therefore answer will be true . ; Driver Code ; 1 / \ 2 5 / \ 7 4 / 6
from collections import deque NEW_LINE from sys import maxsize NEW_LINE INT_MIN = - maxsize NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def isSorted ( root : Node , level : int ) -> bool : NEW_LINE INDENT if root is None : NEW_LINE INDENT return True NEW_LINE DEDENT prevVal = INT_MIN NEW_LINE currLevel = 0 NEW_LINE currNode = Node ( 0 ) NEW_LINE q = deque ( ) NEW_LINE q . append ( ( root , 0 ) ) NEW_LINE while q : NEW_LINE INDENT currNode = q [ 0 ] [ 0 ] NEW_LINE currLevel = q [ 0 ] [ 1 ] NEW_LINE q . popleft ( ) NEW_LINE if currLevel == level : NEW_LINE INDENT if prevVal <= currNode . key : NEW_LINE INDENT prevVal = currNode . key NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT if currNode . left : NEW_LINE INDENT q . append ( ( currNode . left , currLevel - 1 ) ) NEW_LINE DEDENT if currNode . right : NEW_LINE INDENT q . append ( ( currNode . right , currLevel + 1 ) ) NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT root = Node ( 1 ) NEW_LINE root . left = Node ( 2 ) NEW_LINE root . right = Node ( 5 ) NEW_LINE root . left . left = Node ( 7 ) NEW_LINE root . left . right = Node ( 4 ) NEW_LINE root . left . right . left = Node ( 6 ) NEW_LINE level = - 1 NEW_LINE if isSorted ( root , level ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT