Anti-Clockwise spiral traversal of a binary tree in C++
In this article, you will learn about the anti-clockwise spiral traversal of a binary tree in C++ with its algorithm and example.
Introduction:
Within the field of tree traversals, the anti-clockwise spiral traversal offers a visually appealing and thought-provoking look at the architecture of a binary tree. It winds its way around the tree in a mesmerizing dance, defying convention by going against the usual left-to-right or right-to-left directions and visiting nodes in a distinctive spiralling pattern.
Algorithm:
Initialize variables:
- i: Starts at 1, which represents the level to begin from (bottom level for anti-clockwise spiral).
- j: Starts at the height of the tree, which represents the level to end at (root level).
- flag: Boolean variable, which is initially set to false to indicate right-to-left traversal.
Loop until all levels are covered:
- Check the flag value:
- flag is true (left-to-right):
- Traverse levels from i (current bottom level) to j (current top level), printing node data at each level.
- flag is false (right-to-left):
- Traverse levels from j (current top level) down to i (current bottom level), printing node data at each level.
- Change the flag value to its opposite for the next level.
- Update i and j according to the flag value:
- flag is true (left-to-right):Increment i to move down to the next level.
- Decrement j to exclude the top level for left-to-right traversal.
- flag is false (right-to-left):
- Increment i to move down to the next level for right-to-left traversal.
Data Structures:
No stacks or queues are explicitly required for this algorithm.
Auxiliary variables:
i, j: These variable track the current and ending levels for traversal.
flag: It indicates the direction of traversal (left-to-right or right-to-left).
Implementation:
The provided C++ code implements the algorithm with these improvements:
- Error handling: It checks for empty trees and invalid level values.
- printNode function: It replaces with your specific logic to print node data at a given level (might involve level order traversal for larger trees).
Example:
Let us take an example to illustrate the anti-clockwise spiral traversal of a binary tree in C++.
#include
#include
#include
using namespace std;
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : value(value), left(nullptr), right(nullptr) {}
};
int calculateHeight(TreeNode* root);
void printSpiralLevel(TreeNode* root, int level, bool leftToRight);
void spiralTraversal(TreeNode* root) {
if (!root) {
return;
}
int treeHeight = calculateHeight(root);
bool leftToRight = false;
for (int currentLevel = 1; currentLevel <= treeHeight; currentLevel++) {
printSpiralLevel(root, currentLevel, leftToRight);
leftToRight = !leftToRight;
}
}
int calculateHeight(TreeNode* root) {
if (!root) {
return 0;
}
int leftHeight = calculateHeight(root->left);
int rightHeight = calculateHeight(root->right);
return max(leftHeight, rightHeight) + 1;
}
void printSpiralLevel(TreeNode* root, int level, bool leftToRight) {
if (!root) {
return;
}
if (level == 1) {
cout << root->value << " ";
} else if (level > 1) {
if (leftToRight) {
printSpiralLevel(root->left, level - 1, leftToRight);
printSpiralLevel(root->right, level - 1, leftToRight);
} else {
printSpiralLevel(root->right, level - 1, leftToRight);
printSpiralLevel(root->left, level - 1, leftToRight);
}
}
}
TreeNode* constructTree() {
int rootValue;
cout << "Enter value for root node: ";
cin >> rootValue;
TreeNode* root = new TreeNode(rootValue);
queue nodesQueue;
nodesQueue.push(root);
while (!nodesQueue.empty()) {
TreeNode* currentNode = nodesQueue.front();
nodesQueue.pop();
int leftValue, rightValue;
cout << "Enter left child value of " << currentNode->value << " (or -1 if none): ";
cin >> leftValue;
if (leftValue != -1) {
currentNode->left = new TreeNode(leftValue);
nodesQueue.push(currentNode->left);
}
cout << "Enter right child value of " << currentNode->value << " (or -1 if none): ";
cin >> rightValue;
if (rightValue != -1) {
currentNode->right = new TreeNode(rightValue);
nodesQueue.push(currentNode->right);
}
}
return root;
}
int main() {
TreeNode* root = constructTree();
spiralTraversal(root);
return 0;
}
Output:
Explanation of the code:
- In this example, the antiClockwiseSpiralTraversal function takes the root node of the binary tree as input.
- After that, the height function calculates the height of the tree efficiently.
- Next, the printNode function is a placeholder that replace it with your actual printing logic, depending on your requirements.
- The main loop iterates until all levels (i <= j) are covered.
- Inside the loop, the flag value determines the direction of traversal.
- Levels are traversed, and nodes are printed according to the direction and current level.
- The flag and level indicators are updated for the next iteration.
Time Complexity Analysis:
Constructing the Tree:
- The amount of nodes in the tree determines how time-consuming it is to build.
- The user enters the left and right child values of each node, yielding a linear time complexity of O(N), where N is the total number of nodes.
Calculating Tree Height:
- The calculateHeight function iteratively goes through the whole tree to determine the height of a tree.
- The temporal complexity is O(N), where N is the number of nodes because each node is visited once.
Spiral Traversal:
- The spiral traversal function goes through the tree's levels one by one until it reaches its peak.
- The printSpiralLevel function is executed for each level, traversing the level's nodes.
- In the worst-case scenario, when all nodes are visited once, the time complexity is O(N), where N is the total number of nodes.
- Overall, the time complexity of the code is O(N), where N is the number of nodes in the tree.
Space Complexity Analysis:
Tree Construction:
- The queue to build trees and the tree nodes must be stored somewhere.
- This section has an O(N) space complexity, where N is the number of nodes in the tree.
Calculating Tree Height:
- The tree height affects the space complexity of the recursive calls to calculateHeight.
- The space complexity is O(H), where H is the tree's height in the worst scenario when the tree is skewed.
Spiral Traversal:
- The tree's height also affects the space complexity during the spiral traversal.
- The space complexity is O(H) in the worst scenario, where the tree is skewed.