Anti Clockwise spiral traversal of a binary tree in Java
The binary tree is a unique form of a tree that has at most two children. The binary tree can be traversed in multiple formats as per the requirements. In this article, we will understand how to traverse the binary tree in an anti-clockwise direction in a spiral pattern.
We are given a binary tree, as shown below; the requirement is to traverse the binary tree in an anti-clockwise direction in a spiral pattern.
Example
For the binary tree shown above, the Anti-clockwise Spiral Traversal will be:
1, 4, 5, 6, 7, 3, 2.
Approach1
The basic idea behind this approach is to first calculate the height of the binary tree and then print the nodes from left to right and right to left node accordingly.
Algorithm
1. First, find the height of the given binary tree.
2. Initialize variables i to 1 and j to store the tree's height.
3. Initialize Boolean variable flag = true, which will identify the change in the traversal direction.
4. Create a while loop that will traverse till i <= j.
a) If flag == true
- Print the nodes from right to left
- Set flag = false
- Increment value of i
b) else
- Print the nodes from left to right
- Set flag = true
- Decrement value of j
FileName: AntiClockwise.java
// Java program to display anti-clockwise traversal of binary tree in a spiral pattern
class AntiClockwise
{
// Nodes of binary tree
static class Node
{
Node left, right;
int data;
Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
//Method to find the height of the given binary tree
static int getHeight(Node root)
{
// Base case
if (root == null)
return 0;
// Find the height of both left and right subtree
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
// return the max height between the left and right subtree
return Math.max(1 + leftHeight, 1 + rightHeight);
}
//Method to display the nodes from left node to right node
static void displayLeftToRight(Node root, int lvl)
{
if (root == null)
return;
// display the root node
if (lvl == 1)
System.out.print(root.data + " ");
else if (lvl > 1)
{
displayLeftToRight(root.left, lvl - 1);
displayLeftToRight(root.right, lvl - 1);
}
}
//Method to display the nodes from right node to left node
static void displayRightToLeft(Node root, int lvl)
{
if (root == null)
return;
// display the root node
if (lvl == 1)
System.out.print(root.data + " ");
else if (lvl > 1)
{
displayRightToLeft(root.right, lvl - 1);
displayRightToLeft(root.left, lvl - 1);
}
}
//Method to display anti-clockwise spiral traversal of a binary tree
static void antiClockWiseTraversal(Node root)
{
int i = 1;
int j = getHeight(root);
//The flag variable assigns the change in the direction of traversal
boolean flag = true;
while (i <= j)
{
// If the flag is true, display the nodes from right to left
if (flag)
{
displayRightToLeft(root, i);
//Change the value of the flag to false
// so that the traversal direction for the next level
// is changed
flag = false;
// Increase the value of i
i++;
}
// If the flag is false, display the nodes from left to right
else {
displayLeftToRight(root, j);
//Change the value of the flag to true
// so that the traversal direction for the next level
// is changed
flag = true;
// Decrease the value of j
j--;
}
}
}
// main Method
public static void main(String[] args)
{
// Adding the nodes in the binary tree
Node root = new Node(10);
root.left = new Node(11);
root.right = new Node(12);
root.left.left = new Node(13);
root.right.left = new Node(14);
root.right.right = new Node(15);
root.left.left.left = new Node(16);
root.left.left.right = new Node(17);
root.right.left.left = new Node(18);
root.right.right.left = new Node(19);
root.right.right.right = new Node(20);
// Display the output
System.out.println("The Anti-clockwise spiral traversal of the given binary tree is: ");
antiClockWiseTraversal(root);
}
}
Output:
The anti-clockwise spiral traversal of the given binary tree is: 10 16 17 18 19 20 12 11 13 14 15
Another Approach
The previous approach for anti-clockwise spiral traversal is not the most efficient as its worst-case time complexity is O(n^2), as we call the display level every time. An optimization to the previous approach can be made by storing the nodes according to level and then displaying them.
FileName: AntiClockwise1.java
import java.util.*;
public class AntiClockwise1 {
// Nodes of binary tree
static class Node {
int value;
Node left;
Node right;
Node(int value)
{
this.value = value;
this.left = null;
this.right = null;
}
}
static void compute(Node root)
{
// Create a queue
Queue queue = new LinkedList<>();
// Insert the root node
queue.add(root);
// Create a vector
Vector vector = new Vector<>();
// while the queue is not empty
while (!queue.isEmpty()) {
int size = queue.size();
// while the size is greater than zero
while (size > 0) {
// Gets the head of the queue
Node node = queue.poll();
if (node != null) {
vector.add(node);
if (node.right != null)
queue.add(node.right);
if (node.left != null)
queue.add(node.left);
}
// Decrement the size
size--;
}
vector.add(null);
}
boolean direction = true;
int left = 0;
int right = vector.size() - 2;
while (left < right) {
if (direction) {
while (left < vector.size()) {
Node node = vector.get(left++);
if (node == null) {
break;
}
// Display the node
System.out.print(node.value + " ");
}
}
else {
while (right >= left) {
Node node = vector.get(right--);
if (node == null) {
break;
}
// Display the node
System.out.print(node.value + " ");
}
}
direction = !direction;
}
}
// main method
public static void main(String[] args)
{
// Adding the nodes in the binary tree
Node root = new Node(2);
root.left = new Node(7);
root.right = new Node(8);
root.left.left = new Node(2);
root.left.right = new Node(6);
root.left.right.left = new Node(5);
root.left.right.right = new Node(11);
root.right.right = new Node(9);
root.right.right.left = new Node(4);
root.right.right.right = new Node(10);
// Display the output
compute(root);
}
}
Output:
2 5 11 4 10 8 7 2 6 9
Time complexity:
O(n)
Space complexity:
O(n)