Table of Contents
Binary Tree Zig-Zag traversal or Spiral Form Traversal:
Spiral form traversal of a Binary Tree involves traversing the nodes level by level, alternating the direction between left to right and right to left. This creates a “zigzag” pattern as you move down the levels.
Consider this Binary Tree:
1
/ \
2 3
/ \ / \
4 5 6 7
The Spiral form traversal sequence for this tree would be: 1, 3, 2, 4, 5, 6, 7.
Zig-Zag traversal C++:
#include <iostream>
#include <deque> // Include the deque (double-ended queue) library
// Define a node structure for the Binary Tree
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
// Function to perform Spiral form traversal
void spiralTraversal(Node* root) {
if (root == nullptr)
return;
// Create a double-ended queue for traversal
std::deque<Node*> dq;
// Push the root node initially
dq.push_back(root);
// Variable to toggle the direction of traversal
bool leftToRight = true;
while (!dq.empty()) {
int levelSize = dq.size();
for (int i = 0; i < levelSize; ++i) {
if (leftToRight) {
Node* current = dq.front();
dq.pop_front();
std::cout << current->data << " ";
if (current->left)
dq.push_back(current->left);
if (current->right)
dq.push_back(current->right);
} else {
Node* current = dq.back();
dq.pop_back();
std::cout << current->data << " ";
if (current->right)
dq.push_front(current->right);
if (current->left)
dq.push_front(current->left);
}
}
// Toggle the direction for the next level
leftToRight = !leftToRight;
}
}
int main() {
// Creating the Binary Tree
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
// Perform Spiral form traversal
std::cout << "Spiral form traversal: ";
spiralTraversal(root);
return 0;
}
In this code:
- We define a
Nodestructure for the Binary Tree, which holds data, a left child, and a right child. - The
spiralTraversalfunction uses a double-ended queue to traverse the Binary Tree in spiral form. - We alternate the direction of traversal (left to right and right to left) level by level.
When you run the code, it creates the Binary Tree, performs Spiral form traversal, and prints the sequence 1, 3, 2, 4, 5, 6, 7.
Execution Steps:
- Start at the root node (1).
- Traverse left to right: Visit node 1 (print its value).
- Enqueue nodes 2 and 3.
- Traverse right to left: Visit node 3 (print its value).
- Enqueue nodes 6 and 7.
- Traverse left to right: Visit node 2 (print its value).
- Enqueue nodes 4 and 5.
Spiral form traversal zigzags through the Binary Tree, moving left to right and right to left at each level. This traversal order is useful when you want to explore nodes in a different pattern than the usual level order traversal. It’s especially helpful in scenarios like printing a tree structure in a visually appealing manner.