# Recursive Spiral Order Traversal of Tree

This is also called zig-zag order traversal of a binary tree.

Approach: To print the nodes in spiral order, nodes at different levels should be printed in alternating order. To change the order of printing alt variable is used. If alt is 1 then printSpiralLevel() prints nodes from left to right else from right to left.

Non-Recursive solution of the problem is – Non-recursive Spiral Level Order Traversal

```'
void printSpiralLevel(struct node* root, int level, int alt);
int height(struct node* node);

/* Function to print spiral traversal of a tree*/
void printSpiral(struct node* root)
{
int h = height(root);
int i;
bool alt = false;
for(i=1; i<=h; i++)
{
printSpiralLevel(root, i, alt);

/*Revert alt to traverse next level in oppposite order*/
alt = !alt;
}
}

/* Print nodes at a given level */
void printSpiralLevel(struct node* root, int level, int alt)
{
if(root == NULL)
return;
if(level == 1)
printf("%d ", root->data);
else if (level > 1)
{
if(alt)
{
printSpiralLevel(root->left, level-1, alt);
printSpiralLevel(root->right, level-1, alt);
}
else
{
printSpiralLevel(root->right, level-1, alt);
printSpiralLevel(root->left, level-1, alt);
}
}
}
```

### One Thought on “Recursive Spiral Order Traversal of Tree”

1. this is O(n^2). A O(n) solution is also possible using a queue. Only an additional space of O(n) would be required.