?? Binary Trees Series ??

?? Reverse Level Order Traversal

Given a binary tree, perform a reverse level order traversal, i.e., start the traversal from the last level.

Implemented a solution to reverse level order traversal in binary trees. This approach involves using a queue to store nodes during traversal.

?? Click Here for Full Code ??

Approach:

1) Initialization: Create an empty queue and add the root node to it.

2) Level-by-Level Traversal:

While the queue is not empty:

• Get the size of the queue for the current level.
• Dequeue and process nodes for the current level.
• Enqueue children of the processed nodes for the next level.

3) Reverse Order: Print the nodes in the reverse order they were processed.

vector<int> reverseLevelOrder(Node *root)
{
    vector<int>ans;
    
    if(root == NULL){
        return ans;
    }
    
    queue<Node*>q;
    q.push(root);
    
    while(!q.empty()){
        vector<int>res;
        int size = q.size();
        
        
        
        for(int i=0 ; i<size ; i++){
            Node* frontNode = q.front();
            q.pop();
            
            res.push_back(frontNode->data);
            
            if(frontNode->right){
                q.push(frontNode->right);
            }
            if(frontNode->left){
                q.push(frontNode->left);
            }
        }
        for(auto i: res){
            ans.push_back(i);
        }
    }
    reverse(ans.begin(), ans.end());
    return ans;
    
}        

Time Complexity: O(n)

Space Complexity: O(n)

https://github.com/pranaysaini/Supreme-Data-Structures-Algorithms/tree/main/Binary%20Trees