116 views
Level Order Traversal in Spiral form in C++
Level order traversal of a binary tree in a spiral (or zigzag) form means that you traverse the tree level by level, alternating the direction in which you visit nodes. In one level, you visit nodes from left to right, and in the next level, you visit nodes from right to left. You continue this pattern for each level of the tree. You can implement this using a queue and a stack to maintain the order of traversal. Here’s a C++ code example to perform a level order traversal in spiral form:
C++
#include <iostream>
#include <queue>
#include <stack>
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
void spiralLevelOrderTraversal(TreeNode* root) {
if (!root) {
return;
}
std::queue<TreeNode*> levelQueue;
std::stack<TreeNode*> levelStack;
levelQueue.push(root);
bool leftToRight = true; // Flag to track traversal direction
while (!levelQueue.empty()) {
int levelSize = levelQueue.size();
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = levelQueue.front();
levelQueue.pop();
if (leftToRight) {
std::cout << node->data << " ";
} else {
levelStack.push(node);
}
if (node->left) {
levelQueue.push(node->left);
}
if (node->right) {
levelQueue.push(node->right);
}
}
while (!levelStack.empty()) {
TreeNode* node = levelStack.top();
levelStack.pop();
std::cout << node->data << " ";
}
leftToRight = !leftToRight; // Toggle the traversal direction
}
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
std::cout << "Spiral Level Order Traversal: ";
spiralLevelOrderTraversal(root);
std::cout << std::endl;
return 0;
}In this code:
- We use a queue (
levelQueue) to perform regular level order traversal and a stack (levelStack) to reverse the order of nodes in alternating levels. - We maintain a flag
leftToRightto toggle between the left-to-right and right-to-left directions. - We process each level of the tree in the specified direction, pushing nodes onto the stack for reversal when needed.
- Finally, we print the nodes in the desired spiral order.
Running this code with the provided binary tree will give you the spiral level order traversal:
Spiral Level Order Traversal: 1 3 2 4 5 6 7It traverses the tree in a zigzag pattern, alternating between left-to-right and right-to-left at each level.