?? 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


要查看或添加评论,请登录

Pranay Saini的更多文章

  • Maximum sum of nodes in Binary tree such that no two are adjacent

    Maximum sum of nodes in Binary tree such that no two are adjacent

    Given a binary tree with a value associated with each node, we need to choose a subset of these nodes such that sum of…

    2 条评论
  • Largest Subtree Sum

    Largest Subtree Sum

    Given a binary tree. The task is to find subtree with maximum sum in the tree and return its sum.

    2 条评论
  • Sum of Longest Blood Line of Tree

    Sum of Longest Blood Line of Tree

    Given a binary tree having n nodes. Find the sum of all nodes on the longest path from root to any leaf node.

  • Check Mirror Tree

    Check Mirror Tree

    Given two n-ary trees. Check if they are mirror images of each other or not.

    2 条评论
  • Duplicate Subtree

    Duplicate Subtree

    Given a binary tree, find out whether it contains a duplicate sub-tree of size two or more, or not. Note: Two same leaf…

    2 条评论
  • Leaves at Same Level

    Leaves at Same Level

    Given a binary tree with n nodes, determine whether all the leaf nodes are at the same level or not. Return true if all…

  • Sum Tree

    Sum Tree

    Given a Binary Tree. Check for the Sum Tree for every node except the leaf node.

  • Transform to Sum Tree

    Transform to Sum Tree

    Given a Binary Tree of size N , where each node can have positive or negative values. Convert this to a tree where each…

    2 条评论
  • Boundary Traversal of Binary Tree

    Boundary Traversal of Binary Tree

    Given a Binary Tree, find its Boundary Traversal. The traversal should be in the following order: Left boundary nodes:…

  • Diagonal Traversal of Binary Tree

    Diagonal Traversal of Binary Tree

    Consider lines of slope -1 passing between nodes. Given a Binary Tree, print all diagonal elements in a binary tree…

    2 条评论

社区洞察

其他会员也浏览了