if it violates the constraint we stop--the bst property has been violated otherwisewe add its children along with the corresponding constraint for the example in figure on page we initialize the queue with ( [-]each time we pop nodewe first check the constraint we pop the first entry( [-])and add its childrenwith the corresponding constraintsi ( [- ]and ( [ ]next we pop ( [- ])and add its childreni ( [- ]and ( [ ]continuing through the nodeswe check that all nodes satisfy their constraintsand thus verify the tree is bst if the bst property is violated in subtree consisting of nodes within particular depththe violation will be discovered without visiting any nodes at greater depth this is because each time we enqueue an entrythe lower and upper bounds on the node' key are the tightest possible def is_binary_tree_bst (tree)queueentry collections namedtuple ('queueentry '('node ''lower ''upper ')bfs_queue collections deque queueentry (tree float ('-inf ')float('inf '))]while bfs_queue front bfs_queue popleft (if front nodeif not front lower <front node data <front upper return false bfs_queue +queueentry front node left front lower front node data)queueentry front node right front node data front upper return true the time complexity is ( )and the additional space complexity is (