Reverse level order traversal is a variation of the traditional level order traversal. In this method, we visit nodes level by level, but instead of printing from top to bottom, we print from bottom to top. This makes the traversal useful for problems where deeper levels should be processed before higher ones, such as evaluating hierarchical structures from leaves upward.
Understanding the Problem
In normal level order traversal, a queue is used to process nodes level by level. To reverse this order, we can first perform a level order traversal and then use a stack to reverse the printing order. The stack ensures that the last level visited will be printed first, achieving the reverse effect.
Program: Reverse Level Order Traversal – USing Stack & Queue
This program uses a queue to store nodes in level order and a stack to reverse the order of printing.
#include <stdio.h>
#include <stdlib.h>
// Structure for a tree node
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
// Function to create a new node
Node* createNode(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Queue structure for level order traversal
typedef struct Queue {
Node **arr;
int front, rear, size, capacity;
} Queue;
// Function to create a queue
Queue* createQueue(int capacity) {
Queue *queue = (Queue*) malloc(sizeof(Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1;
queue->arr = (Node**) malloc(capacity * sizeof(Node*));
return queue;
}
// Check if queue is empty
int isQueueEmpty(Queue *queue) {
return (queue->size == 0);
}
// Enqueue
void enqueue(Queue *queue, Node *item) {
if (queue->size == queue->capacity) return; // Overflow
queue->rear = (queue->rear + 1) % queue->capacity;
queue->arr[queue->rear] = item;
queue->size++;
}
// Dequeue
Node* dequeue(Queue *queue) {
if (isQueueEmpty(queue)) return NULL;
Node *item = queue->arr[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size--;
return item;
}
// Stack structure
typedef struct Stack {
Node **arr;
int top, capacity;
} Stack;
// Function to create a stack
Stack* createStack(int capacity) {
Stack *stack = (Stack*) malloc(sizeof(Stack));
stack->capacity = capacity;
stack->top = -1;
stack->arr = (Node**) malloc(capacity * sizeof(Node*));
return stack;
}
// Push operation
void push(Stack *stack, Node *node) {
if (stack->top == stack->capacity - 1) return; // Overflow
stack->arr[++stack->top] = node;
}
// Pop operation
Node* pop(Stack *stack) {
if (stack->top == -1) return NULL;
return stack->arr[stack->top--];
}
// Reverse level order traversal
void reverseLevelOrder(Node *root) {
if (!root) return;
Queue *queue = createQueue(100);
Stack *stack = createStack(100);
enqueue(queue, root);
while (!isQueueEmpty(queue)) {
Node *node = dequeue(queue);
push(stack, node);
// Enqueue right first so left is processed last
if (node->right) enqueue(queue, node->right);
if (node->left) enqueue(queue, node->left);
}
while (stack->top != -1) {
Node *node = pop(stack);
printf("%d ", node->data);
}
free(queue->arr);
free(queue);
free(stack->arr);
free(stack);
}
int main() {
Node *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Reverse Level Order Traversal:\n");
reverseLevelOrder(root);
return 0;
}In this program, the queue ensures level order traversal, while the stack reverses the output. By pushing nodes into the stack during traversal and then popping them out, the nodes are printed in reverse level order. The right child is enqueued before the left to maintain correct order when reversed.
Program: Reverse Level Order Traversal – Using Recursion (Height Method)
This program finds the height of the tree and prints nodes level by level starting from the bottom. It uses recursion to print nodes at a given level.
#include <stdio.h>
#include <stdlib.h>
// Structure for a tree node
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
// Create a new node
Node* createNode(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Find tree height
int height(Node *root) {
if (root == NULL) return 0;
int leftH = height(root->left);
int rightH = height(root->right);
return (leftH > rightH ? leftH : rightH) + 1;
}
// Print nodes at a given level
void printLevel(Node *root, int level) {
if (root == NULL) return;
if (level == 1)
printf("%d ", root->data);
else {
printLevel(root->left, level - 1);
printLevel(root->right, level - 1);
}
}
// Reverse level order using height
void reverseLevelOrder(Node *root) {
int h = height(root);
for (int i = h; i >= 1; i--) {
printLevel(root, i);
}
}
int main() {
Node *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Reverse Level Order Traversal (Recursion):\n");
reverseLevelOrder(root);
return 0;
}This recursive approach avoids extra data structures like stacks. Instead, it prints levels from the bottom by repeatedly traversing the tree. While conceptually simple, it can be less efficient for large trees due to repeated traversal at each level.
Program: Reverse Level Order Traversal – Using Queue and Array
This program stores nodes in an array during level order traversal, then prints them in reverse.
#include <stdio.h>
#include <stdlib.h>
// Structure for a tree node
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
// Create a new node
Node* createNode(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Queue structure
typedef struct Queue {
Node **arr;
int front, rear, size, capacity;
} Queue;
Queue* createQueue(int capacity) {
Queue *queue = (Queue*) malloc(sizeof(Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1;
queue->arr = (Node**) malloc(capacity * sizeof(Node*));
return queue;
}
int isQueueEmpty(Queue *queue) {
return (queue->size == 0);
}
void enqueue(Queue *queue, Node *item) {
if (queue->size == queue->capacity) return; // Overflow
queue->rear = (queue->rear + 1) % queue->capacity;
queue->arr[queue->rear] = item;
queue->size++;
}
Node* dequeue(Queue *queue) {
if (isQueueEmpty(queue)) return NULL;
Node *item = queue->arr[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size--;
return item;
}
// Reverse level order using array
void reverseLevelOrder(Node *root) {
if (!root) return;
Queue *queue = createQueue(100);
Node **nodes = (Node**) malloc(100 * sizeof(Node*));
int count = 0;
enqueue(queue, root);
while (!isQueueEmpty(queue)) {
Node *node = dequeue(queue);
nodes[count++] = node;
// Enqueue right first, then left to ensure left-to-right per level after reversal
if (node->right) enqueue(queue, node->right);
if (node->left) enqueue(queue, node->left);
}
// Print nodes in reverse
for (int i = count - 1; i >= 0; i--) {
printf("%d ", nodes[i]->data);
}
printf("\n");
free(queue->arr);
free(queue);
free(nodes);
}
int main() {
Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Reverse Level Order Traversal (Queue + Array - Corrected):\n");
reverseLevelOrder(root);
return 0;
}This version leverages an array to store the traversal and then simply prints it in reverse. It is efficient in terms of time complexity but uses extra memory proportional to the number of nodes.
Program: Reverse Level Order Traversal – Using HashMap
This program uses a hash map to group nodes by their level during traversal. After populating the map, it prints the levels from bottom to top.
#include <stdio.h>
#include <stdlib.h>
// Structure for a tree node
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
// Create a new node
Node* createNode(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Structure for list of nodes at each level
typedef struct List {
int *arr;
int size;
int capacity;
} List;
// Initialize a list
List* createList(int capacity) {
List *list = (List*)malloc(sizeof(List));
list->arr = (int*) malloc(capacity * sizeof(int));
list->size = 0;
list->capacity = capacity;
return list;
}
// Add a value to list
void addToList(List *list, int value) {
if (list->size == list->capacity) return;
list->arr[list->size++] = value;
}
// Structure for hashmap (simple array indexed by level)
typedef struct HashMap {
List **levels;
int capacity;
} HashMap;
// Initialize hashmap
HashMap* createHashMap(int capacity) {
HashMap *map = (HashMap*) malloc(sizeof(HashMap));
map->levels = (List**) malloc(capacity * sizeof(List*));
for (int i = 0; i < capacity; i++) map->levels[i] = NULL;
map->capacity = capacity;
return map;
}
// Insert node data into hashmap at given level
void put(HashMap *map, int level, int value) {
if (map->levels[level] == NULL)
map->levels[level] = createList(100);
addToList(map->levels[level], value);
}
// Recursive function to fill hashmap
void fillMap(Node *root, int level, HashMap *map) {
if (root == NULL) return;
put(map, level, root->data);
fillMap(root->left, level + 1, map);
fillMap(root->right, level + 1, map);
}
// Find tree height
int height(Node *root) {
if (root == NULL) return 0;
int leftH = height(root->left);
int rightH = height(root->right);
return (leftH > rightH ? leftH : rightH) + 1;
}
// Print reverse level order from hashmap
void reverseLevelOrder(Node *root) {
int h = height(root);
HashMap *map = createHashMap(h);
fillMap(root, 0, map);
for (int i = h - 1; i >= 0; i--) {
if (map->levels[i] != NULL) {
for (int j = 0; j < map->levels[i]->size; j++) {
printf("%d ", map->levels[i]->arr[j]);
}
}
}
}
int main() {
Node *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Reverse Level Order Traversal (HashMap):\n");
reverseLevelOrder(root);
return 0;
}This method recursively populates a hash map with nodes at each level. After the traversal, we simply print the levels in reverse order. Using a hashmap (or array indexed by level) makes it easier to handle dynamic tree structures without manually reversing stacks or arrays.
FAQs
Q1: Why enqueue the right child before the left child?
This ensures that when the stack reverses the order, the left child appears before the right child, preserving the correct traversal sequence.
Q2: What is the time complexity of reverse level order traversal?
The time complexity is O(n), as each node is visited once.
Q3: What data structures are essential for this traversal?
A queue is used for level order traversal, and a stack is used to reverse the order.
Q4: Can reverse level order traversal be implemented without a stack?
Yes, but it would require recursion and calculating tree height, which is less efficient compared to using a stack.
Conclusion
Reverse level order traversal is an important variation of level order traversal that processes nodes from bottom to top. It is easy to implement with the help of a queue and stack combination. This traversal is often used in problems where bottom-up processing of a binary tree is required.
References & Additional Resources
These books and online tutorials provide foundational theory and practical examples for understanding reverse level order traversal and other binary tree operations in C.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Detailed coverage of binary trees, traversal techniques, and memory management.
- GeeksforGeeks: Reverse Level Order Traversal – Explanation and C implementation of reverse level order traversal in binary trees.
- Programiz: Binary Tree Traversals – Beginner-friendly guide covering all tree traversal techniques.
- Tutorialspoint: Binary Trees in C – Overview of binary tree operations and traversal methods with C code examples.
