when order needs to be preserved table top tips for queues know your queue libraries some of the problems require you to implement your own queue classfor othersuse the collections deque class append(epushes an element onto the queue not much can go wrong with call to push [ will retrievebut not removethe element at the front of the queue similarlyq[- will retrievebut not removethe element at the back of the queue popleft(will remove and return the element at the front of the queue dequeing or accessing the head/tail of an empty collection results in an indexerror exception being raised compute binary tree nodes in order of increasing depth binary trees are formally defined in in particulareach node in binary tree has depthwhich is its distance from the root given binary treereturn an array consisting of the keys at the same level keys should appear in the order of the corresponding nodesdepthsbreaking ties from left to right for exampleyou should return hh ih ih ih ih ih ii for the binary tree in figure on page hintfirst think about solving this problem with pair of queues solutiona brute force approach might be to write the nodes into an array while simultaneously computing their depth we can use preorder traversal to compute this array--by traversing node' left child first we can ensure that nodes at the same depth are sorted from left to right now we can sort this array using stable sorting algorithm with node depth being the sort key the time complexity is dominated by the time taken to sorti ( log )and the space complexity is ( )which is the space to store the node depths intuitivelysince nodes are already presented in somewhat ordered fashion in the treeit should be possible to avoid full-blow sortthereby reducing time complexity furthermoreby processing nodes in order of depthwe do not need to label every node with its depth in the followingwe use queue of nodes to store nodes at depth and queue of nodes at depth after all nodes at depth are processedwe are done with that queueand can start processing the queue with nodes at depth putting the depth nodes in new queue def binary_tree_depth_order (tree)result curr_depth_nodes []collections deque (tree ]while curr_depth_nodes next_depth_nodes this_level collections deque ([][while curr_depth_nodes curr curr_depth_nodes popleft (if currthis_level append (curr data