Skip to content
Shadow Cipher

Reverse Level order

#include <bits/stdc++.h>
#include "BinaryTree.h"


using namespace std;


int main() {


}
#include <bits/stdc++.h> // Includes iostream, queue, stack, etc. for common operations
using namespace std;     // Uses the standard namespace


// Definition for a Binary Tree Node
class Node {
public:
    int data;     // Data stored in the node
    Node* left;   // Pointer to the left child node
    Node* right;  // Pointer to the right child node


    // Constructor for a Node
    Node(int d) {
        this->data = d;
        this->left = NULL;  // Initialize left child to NULL
        this->right = NULL; // Initialize right child to NULL
    }
};


// Function to build a Binary Tree recursively (pre-order like input)
// Input: Use -1 to represent a NULL node.
Node* buildTree(Node* root) {
    int data;
    cout << "Enter the data (-1 for NULL) : "; // Prompt user for node data
    cin >> data;                              // Read data


    // Base case: If data is -1, it means this node is NULL
    if(data == -1) {
        return NULL; // Return NULL, stopping the recursion for this branch
    }


    root = new Node(data); // Create a new node with the entered data


    // Recursive call for the left child
    cout << "Enter LEFT child of " << data << " : ";
    root->left = buildTree(root->left); // Recursively build the left subtree


    // Recursive call for the right child
    cout << "Enter RIGHT child of " << data << " : ";
    root->right = buildTree(root->right); // Recursively build the right subtree


    return root; // Return the constructed root of the (sub)tree
}


// Function to perform Reverse Level Order Traversal
// Uses a queue for BFS and a stack to reverse the levels/nodes.
void reverseLevelOrder(Node* root) {
    if (root == NULL) { // Handle empty tree case
        return;
    }


    queue<Node*> q;    // Queue for standard level order traversal (BFS)
    stack<Node*> s;    // Stack to store nodes in reverse order of processing


    q.push(root); // Start BFS by pushing the root


    // Perform Level Order Traversal, but push nodes to stack instead of printing
    while (!q.empty()) {
        Node* current = q.front(); // Get the front node from the queue
        q.pop();                   // Remove it from the queue


        s.push(current); // Push the current node onto the stack


        // IMPORTANT: Push right child first, then left child.
        // This ensures that when popped from the stack, they appear left-to-right.
        // However, since we're reversing at the end, if we want right-to-left within level,
        // we push left child first then right child here.
        // Let's go with standard level order into stack, then stack pops for reverse order.
        // For actual "right to left within level" and "bottom to top"
        // we need to push right child first to queue, then left child.
        if (current->right) { // Push right child (will be processed after left in next queue iteration)
            q.push(current->right);
        }
        if (current->left) { // Push left child (will be processed before right in next queue iteration)
            q.push(current->left);
        }
    }


    // Now, pop all nodes from the stack and print them
    // This will give nodes from last level to root, and right-to-left within each level.
    cout << "Reverse Level Order Traversal: ";
    while (!s.empty()) {
        cout << s.top()->data << " "; // Print the data of the node at stack top
        s.pop();                      // Pop the node from stack
    }
    cout << endl; // Newline for clean output
}




int main() {
    Node* root = NULL; // Initialize the root of the tree to NULL


    // Creating a tree using buildTree function (pre-order input)
    // Example INPUT: 1 2 4 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1
    // This creates a tree like:
    //      1
    //     / \
    //    2   3
    //   / \ / \
    //  4  5 6  7
    root = buildTree(root);


    cout << "\n--- Traversals ---" << endl;


    // Perform and print the Reverse Level Order Traversal
    reverseLevelOrder(root);


    return 0; // End of the program
}


/*
Example INPUT for buildTree function:
1 2 4 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1


This input creates a tree structure like this:
        1
       / \
      2   3
     / \ / \
    4  5 6  7


Standard Level Order: 1 2 3 4 5 6 7
Reverse Level Order (as implemented here: bottom-up, right-to-left within level): 7 6 5 4 3 2 1
(If you push Left then Right to queue, the within-level order would be Left-to-Right.
The current code pushes Right then Left to queue, so the stack pops Right-to-Left within a level)
*/

1. Binary Tree Node Structure

  • A Node in a Binary Tree typically consists of:
    • data: The value stored in the node.
    • left: A pointer to the left child node.
    • right: A pointer to the right child node.

2. buildTree(Node* root) (Recursive Pre-order Build)

  • Logic: Builds the tree recursively by taking input in a pre-order fashion (Root -> Left -> Right).
  • Uses -1 as a sentinel value to indicate a NULL child (base case for recursion).
  • Use Case: Useful when you want to construct a tree directly from a pre-order sequence where NULL nodes are explicitly marked.

3. Reverse Level Order Traversal

  • Definition: Traverses the tree level by level, but from the last level up to the root, and for each level, from right to left.

  • It’s essentially a Level Order Traversal (BFS) where the results are stored and then printed in reverse.

  • Algorithm (Using Auxiliary Queue and Stack):

    1. Initialize an empty queue<Node*> (for standard BFS).
    2. Initialize an empty stack<Node*> (to store nodes in reverse order of visit).
    3. If the root is NULL, return.
    4. Enqueue the root node into the queue.
    5. While the queue is not empty: a. Dequeue a node (temp) from the queue. b. Push temp onto the stack. This accumulates nodes level by level. c. IMPORTANT: Enqueue the right child first, then the left child (if they exist). This ensures that when nodes are popped from the stack, children are printed from right to left within a level.
    6. After the queue becomes empty, all nodes are in the stack.
    7. While the stack is not empty: a. Pop a node from the stack. b. Print its data. This prints nodes from the last level to the root, and from right to left within each level.

4. Complexity Analysis

  • Time Complexity: O(N)
    • Each node is enqueued and dequeued once from the queue.
    • Each node is pushed and popped once from the stack.
    • Total operations are proportional to N.
  • Space Complexity: O(N)
    • The queue stores nodes up to the maximum width of the tree (O(W)).
    • The stack stores all N nodes (O(N)).
    • Therefore, the overall space complexity is O(N).