Reverse Level Order Traversal - GFG

This was 7th May's POTD, and I remember that I had taken more than required time for this, which was because of the Title of the problem that might confuse you that we'll be finding the level order traversal and then reverse it but actually they won't you to go from right to left at each level. 

Then this idea for getting the level separately struck my mind. We are just traversing the tree Left to right, top to bottom and are storing each level, then at the end just get the reverse of those levels. 

Although I feel that this problem could be a medium level prob, because firstly not many people know the logic of Level Order Traversal and in this prob on top of knowing that logic we had to even find the idea of getting the reverse of each level for which had to find the idea of using 2 queues( okay maybe there would be a better way, but I am cynical about that cause we gotta know the whole level and then only we can get the level below na? )

Overall, the moral of the story is that I am late for bed, it's 11:09, so gotta get to the buho and then hit the...

Problem Statement:-

Given a binary tree of size n, find its reverse level order traversal. ie- the traversal must begin from the last level.

Example 1:

Input :
        1
      /   \
     3     2

Output: 
3 2 1
Explanation:
Traversing level 1 : 3 2
Traversing level 0 : 1

Example 2:

Input :
       10
      /  \
     20   30
    / \ 
   40  60

Output: 
40 60 20 30 10
Explanation:
Traversing level 2 : 40 60
Traversing level 1 : 20 30
Traversing level 0 : 10

Your Task: 
You don't need to read input or print anything. Complete the function reverseLevelOrder() which takes the root of the tree as input parameter and returns a list containing the reverse level order traversal of the given tree.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Constraints:
1 ≤ n ≤ 104

Code Implementation:-

def reverseLevelOrder(root):

    # code here

    # Will use the standard way of doing Level Order Traversal, just maintain

    # a queue of nodes and keep storing the left, right child nodes in

    # respective order untill the queue becomes empty, just visualise yourself

    # goin through the traversal

    ''' Catching the idea of using 2 queues is a bit tricky but can grasp '''

    trav=[]

    queue=[]

    queue.append(root)

    while(len(queue)!=0):

       

        queue2=queue.copy()

        queue=[]

        currLevel=[]

        while(len(queue2)!=0):

            node=queue2.pop(0)

            # print(node.data)

            currLevel.append(node.data)

            # trav.append(node.data)

            if(node.left!=None):

                queue.append(node.left)

            if(node.right!=None):

                queue.append(node.right)

        trav.append(currLevel)

        # print()

       

    # just got all the levels in trav,

    # print(trav)

    ans=list()

    # now will use these levels bottom to up order

    for ls in reversed(trav):

        for i in ls:

            ans.append(i)

   

    ''' First this code failed 3 test cases in time, but then the same code

        got passed on submitting again

    '''

    return ans