gfg potd solution python | geeks for geeks potd solution today 7 May 2024

Todays problem is Reverse Level Order Traversal on gfg potd for 7 May 2024. This problem is an easy level questions on tree data structures. It is one of the widely asked questions by some of the MAANGS and other reputed tech giants and top IT firms.

In order to solve a reverse level order traversal on a binary tree, we can use a queue data structure in python solution to store the nodes level by level, and then print the elements from the queue in reverse order.

Here’s how the reverseLevelOrder function works:

1. We first check if the root is None. If so, we return an empty list. As no tree exist so cant really traverse
2. We create a queue named queue and a deque result to store the reverse level order traversal.
3. We enqueue the root node into the queue.
4. We start a loop that continues until the queue is empty.
5. Inside the loop, we dequeue a node from the queue and append its value to the left end of the result deque using result.appendleft(node.val). This way, the values are added to the deque in reverse order.
6. We then enqueue the left and right child nodes of the current node (if they exist) to the queue.
7. After the loop finishes, we convert the result deque to a list and return it.

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree, as we visit each node once. The space complexity is also O(n) in the worst case when the tree is a perfect binary tree, as we need to store all the nodes in the queue at some point.

Below is the Python code to perform the reverse level order traversal of a binary tree:

from collections import deque

def reverseLevelOrder(root):
    if not root:
        return []
    
    queue = deque([root])
    result = deque()
    
    while queue:
        node = queue.popleft()
        result.appendleft(node.data)
        
        if node.right:
            queue.append(node.right)
        if node.left:
            queue.append(node.left)
    
    return list(result)