Spiral Order Traversal Of A Tree Using Recursion In C

Let's begin by examining the fundamental concepts that form the basis of spiral order traversal prior to delving into the C program and algorithm:

Commence at the Root:

The primary node of the binary tree acts as the initial point for the traversal process.

Changing Directions:

At every tier of the tree, there is an alternating pattern of shifting from left to right and then from right to left. The initial level is explored from left to right, then the subsequent level from left to right again, continuing this alternation throughout the tree's structure.

Recursion:

You have the option to employ a recursive approach when coding the spiral order traversal. The key lies in keeping track of both the traversal direction and the current level during each iteration.

Spiral Order Traversal Algorithm:-

It is the recursive spiral order traversal algorithm for a binary tree:

✅ Construct a spiral function . It is a traversal that requires the current level, node, and direction ( left-to-right or right-to-left ) flags.
✅ In the function of spiralTraversa l: Return if the current node is NULL. Print the current node's value if the level is even (beginning at 0). Save the value of the current node in a temporary data structure (such as a stack) for subsequent reverse printing if the current level is odd. In order to incremente the level and toggle the direction flag, recursively call spiralTraversal for the left and right children of the current node.
✅ Call the spiralTraversal function in the main program, passing in the tree's root, initial direction flag set to left-to-right, and starting level 0.
✅ Return if the current node is NULL.
✅ Print the current node's value if the level is even (beginning at 0).
✅ Save the value of the current node in a temporary data structure (such as a stack) for subsequent reverse printing if the current level is odd.
✅ In order to incremente the level and toggle the direction flag, recursively call spiralTraversal for the left and right children of the current node.

Example:

Let's consider a C program that demonstrates Recursive Spiral Order Traversal of a Tree:

Example


#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

// Structure for a binary tree node

struct Node {

 int data;

 struct Node* left;

 struct Node* right;

};

// Function to create a new binary tree node

struct Node* createNode(int data) {

 struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

 newNode->data = data;

 newNode->left = NULL;

 newNode->right = NULL;

 return newNode;

}

// Function to find the height of a binary tree

int getHeight(struct Node* root) {

 if (root == NULL)

 return 0;

 int leftHeight = getHeight(root->left);

 int rightHeight = getHeight(root->right);



 return (leftHeight > rightHeight)? (leftHeight + 1) : (rightHeight + 1);

}

// Function to print nodes at a specific level from left to right

void printLevelLeftToRight(struct Node* root, int level) {

 if (root == NULL)

 return;

 if (level == 0)

 printf("%d ", root->data);

 else {

 printLevelLeftToRight(root->left, level - 1);

 printLevelLeftToRight(root->right, level - 1);

 }

}

// Function to print nodes at a specific level from right to left

void printLevelRightToLeft(struct Node* root, int level) {

 if (root == NULL)

 return;

 if (level == 0)

 printf("%d ", root->data);

 else {

 printLevelRightToLeft(root->right, level - 1);

 printLevelRightToLeft(root->left, level - 1);

 }

}

// Function to perform spiral order traversal using recursion

void spiralTraversal(struct Node* root) {

 int height = getHeight(root);

 bool leftToRight = true;

 for (int i = 0; i < height; i++) {

 if (leftToRight)

 printLevelLeftToRight(root, i);

 else

 printLevelRightToLeft(root, i);

 leftToRight = !leftToRight;

 }

}

int main() {

 struct Node* root = createNode(1);

 root->left = createNode(2);

 root->right = createNode(3);

 root->left->left = createNode(4);

 root->left->right = createNode(5);

 root->right->left = createNode(6);

 root->right->right = createNode(7);

 // Perform spiral order traversal using recursion

 spiralTraversal(root);

 return 0;

}

Output:

Output


[value] [value]

Code Explanation:

Node Creation and Data Structures:

✅ In this example, we construct a structure called struct Node to represent a binary tree node.
✅ Every node has a right child (right), a left child (left), and an integer data (right).
✅ After that, we write the createNode function to allocate memory and initialize a new binary tree node.

Determining the Tree's Height:

✅ Next, we define the function getHeight to determine the binary tree's height (maximum depth).
✅ It is necessary to calculate the tree's level count.

Nodes Printing at a Particular Level:

✅ We build two recursive functions, printLevelLeftToRig ht and printLevelRightToLeft to print nodes at a particular level of the tree from left to right and right to left, respectively.
✅ These functions recursively scan the tree, outputting the nodes at the designated level after taking the current node and the level we wish to print.

Logic of Spiral Order Traversal:

✅ The spiralTraversal function contains the primary traversal logic.
✅ First, we use getHeight to determine the tree's height.
✅ After that, we initialize a boolean variable called leftToRight with true (left to right) to specify the traversal direction.
✅ We toggle the direction at each level as we loop through every level from 0 to height-1.
✅ For each stage: To print the nodes at that level from left to right, we execute printLevelLeftToRight if leftToRight is true. To print the nodes at that level from right to left, we call printLevelRightToLeft if leftToRight is false. We flip the leftToRight flag to change the direction for the next level after printing every node at the current level.
✅ To print the nodes at that level from left to right, we execute printLevelLeftToRight if leftToRight is true.
✅ To print the nodes at that level from right to left, we call printLevelRightToLeft if leftToRight is false.
✅ We flip the leftToRight flag to change the direction for the next level after printing every node at the current level.

Main Function:

✅ For testing reasons, we build a binary tree using example data in the main function.
✅ To execute the spiral order traversal on the binary tree, we call the spiralTraversal

Printing the Results:

✅ As the nodes are visited, the spiral order traversal's output is printed, creating the required zigzag pattern.

The key to this method is to display nodes at every tier in the specified zigzag format by navigating through the tree recursively. On each tier, the algorithm switches between outputting from left to right and from right to left, enabling a spiral-like traversal of the binary tree.

Spiral Order Traversal Algorithm:-

Example:

Code Explanation:

Input Required