Introduction
In navigating through a binary tree, it encompasses the exploration of every provided node in a methodical sequence. The counterclockwise spiral traversal stands out as the exclusive approach for moving through a binary tree. This traversal commences at the root node, proceeds to the farthest left leaf, then to the farthest right leaf, and repeats this pattern in a spiral fashion. This particular technique of traversal introduces an intriguing variation to the array of tree traversal strategies.
History
The idea of binary trees and how to navigate them dates back to the early stages of computer science. Trees play a crucial role in illustrating the hierarchical connections among the nodes of a binary tree. Efficiently traversing a tree is essential for effectively carrying out operations and handling the data it contains.
The concept of traversing a binary tree in an anti-clockwise spiral manner offers a distinct approach to exploring the tree structure. Unlike conventional methods such as in-order, pre-order, and post-order traversal, this spiral traversal introduces a novel perspective to tree navigation. It proves particularly beneficial when dealing with trees arranged in patterns that deviate from the linear progression typically seen in other traversal techniques.
Approach
The approach involves utilizing two variables, with one set to 1 and the other initialized to the tree's height. A while loop is employed, continuing until the first variable surpasses the second. Another variable, flag, is introduced and set to 0. Within the loop, a condition is checked: if flag is 0, the tree is navigated from right to left, flag is set to 1, and the value of the first variable is incremented to explore the level below the current one in the subsequent iteration. Furthermore, flag is reset to 0 upon transitioning from bottom to top levels, enabling left to right traversal in the next iteration, with the second variable decremented to target the level directly above the current one. This process is reiterated until the entire binary tree is thoroughly traversed.
Implementation in C++
Example 1:
Let's consider a scenario to demonstrate the counterclockwise 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's consider a different scenario to demonstrate the counterclockwise spiral traversal of a binary tree using 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 algorithm for traversing a binary tree in an anti-clockwise spiral pattern, demonstrated in the C++ code snippets above, offers a unique and insightful approach to visiting the tree's nodes. It switches directions between left and right as it moves through each level of the tree, creating a spiral-like traversal pattern. We have explored both the recursive and class-oriented approaches to implementing this algorithm effectively, ensuring a straightforward traversal process.
Time Complexity: The linear time complexity increases proportionally with the quantity of nodes in the system.
Space complexity increases in relation to the maximum width of the tree at each level.
In summary, this algorithm offers a unique and innovative method for navigating a binary tree.
