Introduction
In traversing a binary tree it involves the visiting of the all given nodes in a systematic order. Anti-clockwise spiral traversal is the only way to traverse a binary tree. This traversal begins at the root and goes to the leftmost leaf, then to the rightmost leaf, and so on, making a spiral pattern. This method of traversing adds up a unique twist to the tree traversal techniques.
History
This concept of binary trees and their traversals was seen during early days of computer science. Tree data structures are fundamental in representing the hierarchical relationships in between the elements of the binary tree. The main theme of traversing a tree is necessary for performing the task efficiently and processing the elements which are stored in it.
The anti-clockwise spiral traversal concept provides a unique way for us to explore a binary tree. Whereas the traditional tree traversal methods like in-order, pre-order, and post-order can also perform the traversing but this spiral traversal brings a different way to tree traversal. This traversal method is useful in situations like the tree in a pattern that is different from the linear fashion of other traversal techniques.
Approach
The concept is to use two variables in which i initialized to 1 and j initialized to the height of tree and run a while loop which won't break until i becomes greater than j. We will use another variable flag and initialize it to 0. In the while loop, we will now check a condition that states that if flag == 0, we will traverse the tree from right to left, marking flag as 1, and then increment the value of i to visit the level immediately below the current level next time. In addition, we will mark the flag as 0 when we cross the level from bottom to top so that the next time, we can travel the tree from left to right and then decrease the value of j to reach the level that is just above the current level. Till the binary tree is fully explored, we will repeat the entire procedure.
Implementation in C++
Example 1:
Let us take an example to illustrate the anti-clockwise spiral traversal of a binary tree in C++.
#include <iostream>
#include <deque>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void antiClockwiseSpiralTraversal(TreeNode* root) {
if (!root) return;
deque<TreeNode*> nodes;
nodes.push_back(root);
bool leftToRight = true;
while (!nodes.empty()) {
int levelSize = nodes.size();
for (int i = 0; i < levelSize; ++i) {
if (leftToRight) {
TreeNode* current = nodes.front();
nodes.pop_front();
cout << current->val << " ";
if (current->left) nodes.push_back(current->left);
if (current->right) nodes.push_back(current->right);
} else {
TreeNode* current = nodes.back();
nodes.pop_back();
cout << current->val << " ";
if (current->right) nodes.push_front(current->right);
if (current->left) nodes.push_front(current->left);
}
}
leftToRight = !leftToRight;
}
}
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);
cout << "Anti-clockwise Spiral Traversal: ";
antiClockwiseSpiralTraversal(root);
return 0;
}
Output:
Anti-clockwise Spiral Traversal: 1 3 2 4 5 6 7
Explanation:
- Include Headers:
- The code has necessary headers for input/output operations and also deque container.
- Binary Tree Node Definition:
- We have a structure called TreeNode representing nodes in a binary tree.
- Each node has an integer value (val) and pointers to its left and right children.
- Anti-clockwise Spiral Traversal Function:
- The antiClockwiseSpiralTraversal function helps us for traversing a binary tree in an anti-clockwise spiral pattern.
- It uses a deque (double-ended queue) to store nodes at each level.
- The traversal is like going from left to right and right to left at each level.
- Nodes are printed according to the dequeue from the front or back of the deque.
- Main Function:
- The main function creates a binary tree with a specific structure.
- After that, it calls the antiClockwiseSpiralTraversal function to print the nodes of the tree in an anti-clockwise spiral pattern.
- The traversal creates a spiral pattern by following the direction from left to right and right to left at every level.
Time and Space Complexities:
- Time Complexity:
- The time complexity is O(N) , here N is the number of nodes in a binary tree.
- Each node is involved once during the traversal.
- In the worst case, we have to traverse all nodes.
- Space Complexity:
- The space complexity is O(W) , here W denotes the maximum width of the binary tree
- The space required is proportional to the maximum number of nodes.
- In the worst case, the deque may store all the nodes at a level, and then we have the space complexity proportional to the width of the widest level.
Example 2:
Let us take another example to illustrate the anti-clockwise spiral traversal of a binary tree in C++.
#include <iostream>
#include <deque>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void antiClockwiseSpiralTraversal(TreeNode* root) {
if (!root) return;
deque<TreeNode*> nodes;
nodes.push_back(root);
bool leftToRight = true;
while (!nodes.empty()) {
int levelSize = nodes.size();
for (int i = 0; i < levelSize; ++i) {
if (leftToRight) {
TreeNode* current = nodes.front();
nodes.pop_front();
cout << current->val << " ";
if (current->left) nodes.push_back(current->left);
if (current->right) nodes.push_back(current->right);
} else {
TreeNode* current = nodes.back();
nodes.pop_back();
cout << current->val << " ";
if (current->right) nodes.push_front(current->right);
if (current->left) nodes.push_front(current->left);
}
}
leftToRight = !leftToRight;
}
}
int main() {
// Construct a more complex binary tree
// 1
// / \
// 2 3
// / \ \
// 4 5 6
// / \
// 7 8
// / \
// 9 10
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->right = new TreeNode(6);
root->left->left->left = new TreeNode(7);
root->left->left->right = new TreeNode(8);
root->left->left->left->left = new TreeNode(9);
root->left->left->right->right = new TreeNode(10);
cout << "Anti-clockwise Spiral Traversal: ";
antiClockwiseSpiralTraversal(root);
return 0;
}
Output:
Anti-clockwise Spiral Traversal: 1 3 2 4 5 6 8 7 9 10
Explanation:
- In this example, the code gives a structure called TreeNode to denote individual nodes in a binary tree. Each point has a number and is connected to its left and right "children" .
- Traversal logic includes a function antiClockwiseSpiralTraversal . This function works as a guide, helping us to explore the binary tree in a unique way by moving in a spiral pattern.
- After that, we take "deque" functions which is similar to a queue, allowing us to add or delete elements from both ends.
- The function goes through each level, beginning at the top (root) of the tree.
- It moves in a zigzag pattern , going from left to right, generating a spiral as it goes down.
Time and Space Complexities:
- Time Complexity:
- The time complexity is O(N) , here N is the number of nodes in a binary tree.
- Each node is involved once during the traversal.
- In the worst case, we have to traverse all nodes.
- Space Complexity:
- The space complexity is O(W) , here W denotes the maximum width of the binary tree.
- The space required is proportional to the maximum number of nodes.
- In the worst case, the deque may store all the nodes at a level, and then we have the space complexity proportional to the width of the widest level.
Example 3:
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Anticlockwise spiral traversal of a binary tree
// Using recursion
// Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = nullptr;
this->right = nullptr;
}
};
// Implement Binary Tree
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = nullptr;
}
// Find height of given binary tree
int treeHeight(TreeNode *node)
{
if (node != nullptr)
{
int l = this->treeHeight(node->left) + 1;
int r = this->treeHeight(node->right) + 1;
if (l > r)
{
return l;
}
else
{
return r;
}
}
else
{
return 0;
}
}
// Display given level from left to right
void printLeftToRight(TreeNode *node, int level)
{
if (node == nullptr)
{
return;
}
if (level == 1)
{
// Print level node
cout << " " << node->data;
}
else
{
// First visit left child
this->printLeftToRight(node->left, level - 1);
this->printLeftToRight(node->right, level - 1);
}
}
// Display given level from right to left
void printRightToLeft(TreeNode *node, int level)
{
if (node == nullptr)
{
return;
}
if (level == 1)
{
// Print level node
cout << " " << node->data;
}
else
{
// First visit right child
this->printRightToLeft(node->right, level - 1);
this->printRightToLeft(node->left, level - 1);
}
}
// Handles the request of printing
// anticlockwise spiral of binary tree.
void antiClockWiseSpiral()
{
if (this->root == nullptr)
{
cout << "\n Empty Tree " << endl;
}
else
{
// Start level
int top = 1;
// Last level
int down = this->treeHeight(this->root);
// This is level indicator (top to down selector)
bool selection = false;
// When the top level less than or equal to down level
while (top <= down)
{
if (selection == false)
{
// right to left
this->printRightToLeft(this->root, top);
// Increase level
top++;
// Next is bottom level
selection = true;
}
else
{
// left to right
this->printLeftToRight(this->root, down);
// Decrease the level
down--;
// Next is top level
selection = false;
}
}
}
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*
6
/ \
/ \
4 7
/ \ \
2 3 12
/ \ /
10 8 5
/ \
9 -1
-----------------
Binary tree
*/
// Add tree node
tree->root = new TreeNode(6);
tree->root->left = new TreeNode(4);
tree->root->left->right = new TreeNode(3);
tree->root->left->right->left = new TreeNode(10);
tree->root->left->right->left->left = new TreeNode(9);
tree->root->left->right->right = new TreeNode(8);
tree->root->left->right->right->right = new TreeNode(-1);
tree->root->left->left = new TreeNode(2);
tree->root->right = new TreeNode(7);
tree->root->right->right = new TreeNode(12);
tree->root->right->right->left = new TreeNode(5);
// Test
tree->antiClockWiseSpiral();
return 0;
}
Output:
6 7 4 2 3 12 5 8 10 9 -1
Explanation:
- Binary Tree Node Definition:
- In this example, the code defines the TreeNode class, which represents individual nodes in a binary tree.
- Each node is assigned an integer value and has pointers to its left and right children.
- Binary Tree Implementation (the BinaryTree class):
- The BinaryTree class is used to manage the binary tree.
- It includes a root node, which is initially set to nullptr .
- The class has functions for determining the height of the tree and printing nodes at a given level from left to right or right to left.
- Height of the Binary Tree:
- The treeHeight function recursively computes the height of the binary tree. This function returns the maximum height between the left and right subtrees plus one.
- Printing Level:
- Two functions, printLeftToRight and printRightToLeft , are used to print nodes at a given level from left to right and right to left.
- Anticlockwise Spiral Traversal:
- The antiClockWiseSpiral function gives the binary tree's anticlockwise spiral traversal.
- It uses a printLeftToRight and printRightToLeft functions based on the level, switching between them.
- Main function:
- The main function creates a BinaryTree
- A sample binary tree is built using various nodes and links.
- The antiClockwiseSpiral function is used to print the tree's anticlockwise spiral traversal.
Time and Space Complexities:
- Time Complexity:
- The time complexity is O(N) , here N is the number of nodes in a binary tree.
- Each node is involved once during the traversal.
- In the worst case, we have to traverse all nodes.
- Space Complexity:
- The space complexity is O(W) , here W denotes the maximum width of the binary tree.
- The space required is proportional to the maximum number of nodes.
- In the worst case, the deque may store all the nodes at a level, and then we have the space complexity proportional to the width of the widest level.
Conclusion:
The anti-clockwise spiral tree traversal algorithm, as shown in the C++ codes above, provides an interesting and informative way to traverse the nodes of the binary tree. The algorithm alternates from left to right, and from right to left, at each level of the tree, to form the spiral pattern. We have discussed both the recursive and class-based implementation of the algorithm efficiently traverse the tree while keeping it simple.
Time Complexity: Linear time complexity scales with number of nodes.
Space complexity scales with maximum width of tree at each level.
In conclusion, this algorithm provides an interesting and creative way to traverse a binary tree.