next_depth_nodes +[curr left curr right if this_level result append this_level curr_depth_nodes next_depth_nodes return result since each node is enqueued and dequeued exactly oncethe time complexity is (nthe space complexity is ( )where is the maximum number of nodes at any single depth variantwrite program which takes as input binary tree and returns the keys in top downalternating left-to-right and right-to-left orderstarting from left-to-right for exampleif the input is the tree in figure on the following pageyour program should return hh ih ih ih ih ih ii variantwrite program which takes as input binary tree and returns the keys in bottom upleft-to-right order for exampleif the input is the tree in figure on the next pageyour program should return hh ih ih ih ih ih ii variantwrite program which takes as input binary tree with integer keysand returns the average of the keys at each level for exampleif the input is the tree in figure on the following pageyour program should return