Zigzag or spiral traversal is a variation of level order traversal where nodes are printed alternately from left to right and right to left at each level. This makes the traversal follow a zigzag pattern across the tree. It is particularly useful when you want to visualize hierarchical data in an alternating fashion.
Understanding the Problem
In a simple level order traversal, we use a queue to process nodes level by level. However, zigzag traversal requires alternating the order at each level. One way to achieve this is by using two stacks — one for the current level and another for the next. The order of pushing children depends on the traversal direction, ensuring nodes are printed in zigzag fashion.
Program: Zigzag (Spiral) Level Order Traversal – Using Two Stacks
This program implements zigzag traversal using two stacks. At each level, nodes are popped from one stack and their children are pushed to the other stack in a specific order. The direction alternates between left-to-right and right-to-left on each level.
#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;
}
// Structure for a stack
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;
}
// Check if stack is empty
int isEmpty(Stack *stack) {
return stack->top == -1;
}
// 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 (isEmpty(stack)) return NULL;
return stack->arr[stack->top--];
}
// Zigzag (spiral) traversal
void zigzagTraversal(Node *root) {
if (!root) return;
Stack *currentLevel = createStack(100);
Stack *nextLevel = createStack(100);
int leftToRight = 1;
push(currentLevel, root);
while (!isEmpty(currentLevel)) {
Node *node = pop(currentLevel);
printf("%d ", node->data);
if (leftToRight) {
if (node->left) push(nextLevel, node->left);
if (node->right) push(nextLevel, node->right);
} else {
if (node->right) push(nextLevel, node->right);
if (node->left) push(nextLevel, node->left);
}
if (isEmpty(currentLevel)) {
leftToRight = !leftToRight; // Switch direction
Stack *temp = currentLevel;
currentLevel = nextLevel;
nextLevel = temp;
printf("\n"); // Move to new line after each level
}
}
free(currentLevel->arr);
free(currentLevel);
free(nextLevel->arr);
free(nextLevel);
}
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("Zigzag (Spiral) Level Order Traversal (Two Stacks):\n");
zigzagTraversal(root);
return 0;
}This implementation alternates between stacks to achieve zigzag order. On one level, nodes are pushed left-to-right, and on the next, right-to-left. By swapping stacks after each level, the traversal naturally flows in a spiral pattern.
Program: Zigzag (Spiral) Level Order Traversal – Using Recursion
This program implements zigzag traversal using recursion. The tree height is determined first, and then nodes are printed level by level, alternating between left-to-right and right-to-left order.
#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;
}
// Find the height of the tree
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 a given level
void printLevel(Node *root, int level, int leftToRight) {
if (root == NULL) return;
if (level == 1) {
printf("%d ", root->data);
} else {
if (leftToRight) {
printLevel(root->left, level - 1, leftToRight);
printLevel(root->right, level - 1, leftToRight);
} else {
printLevel(root->right, level - 1, leftToRight);
printLevel(root->left, level - 1, leftToRight);
}
}
}
// Recursive zigzag traversal
void zigzagTraversal(Node *root) {
int h = height(root);
int leftToRight = 1;
for (int i = 1; i <= h; i++) {
printLevel(root, i, leftToRight);
printf("\n");
leftToRight = !leftToRight;
}
}
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("Zigzag (Spiral) Level Order Traversal (Recursive):\n");
zigzagTraversal(root);
return 0;
}This recursive solution prints the tree level by level. At each level, the order alternates: one level is processed left-to-right, and the next right-to-left. The recursion handles traversal naturally without explicit stack structures, but it can be less efficient for large trees due to repeated traversal of nodes when printing each level.
FAQs
Q1: Why are two stacks used instead of one?
Two stacks help maintain the correct order of nodes when switching directions at each level, making the zigzag effect easy to implement.
Q2: What is the time complexity of zigzag traversal?
The time complexity is O(n) since each node is pushed and popped exactly once.
Q3: Can I implement zigzag traversal using a queue?
Yes. You can use a double-ended queue (deque) and control insertion/removal from both ends to achieve the same effect.
Q4: Is zigzag traversal different from spiral traversal?
No. Both terms are used interchangeably for the same traversal technique.
Conclusion
Zigzag traversal is a variation of level order traversal that alternates direction at each level. Using two stacks simplifies the implementation and ensures nodes are processed correctly in a spiral order. This traversal is widely used for tree visualization and interview problems related to binary trees.
References & Additional Resources
The following books and online resources provide theoretical insights and practical examples to help you understand tree traversals, including zigzag level order traversal and related algorithms in C.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Detailed coverage of binary trees and traversal algorithms.
- GeeksforGeeks: Zigzag Level Order Traversal – Explanation and implementation of zigzag (spiral) traversal in binary trees.
- Programiz: Binary Tree Traversals – Beginner-friendly guide with traversal techniques (inorder, preorder, postorder, and level order).
- Tutorialspoint: Tree Traversals in C – Overview of tree traversal methods with C code snippets.
