Binary Tree: Given a binary tree, perform reverse level order traversal

Problem Statement:

Given a binary tree, perform reverse level order traversal from bottom up and from left to right

Example:

Input:

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

Output:

[[2, 9], [11, 14], [8, 12], [10]]

Solution Explanation:

We will use BFS to solve the problem.

We do normal level order traversal. collect nodes level by level from top to bottom.

To satisfy the problem requirement that we have to collect levels from bottom to top.

So instead of reversing at the end, we will insert each level at the beginning of the result.

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

Code Solution

#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node 
{
    int data;
    struct Node *left;
    struct Node *right;
};


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void display_inorder(Node* root)
{
    if (root == NULL)
        return;

    display_inorder(root->left);
    cout << root->data << " ";
    display_inorder(root->right);
}

vector<vector<int>> solution(Node* root) 
{
    vector<vector<int>> res;
    if (!root) 
        return res;

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) 
    {
        int levelSize = q.size();
        vector<int> level;

        for (int i = 0; i < levelSize; ++i) 
        {
            Node* node = q.front(); 
            q.pop();
            level.push_back(node->data);

            if (node->left) 
                q.push(node->left);

            if (node->right) 
                q.push(node->right);
        }

        res.insert(res.begin(), level);
    }

    return res;
}


int main(void)
{
    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(12);
    root->left->left = newNode(2);
    root->left->right = newNode(9);
    root->right->left = newNode(11);
    root->right->right = newNode(14);

    vector<vector<int>> res = solution(root);
    
    for (const auto& row : res)
    {
        for (int val : row)
            cout << val << " ";
        cout << endl;
    }    


    return 0;
}

Output

2 9 11 14 
8 12 
10