Zig-Zag & Spiral Traversal Of A Binary Tree Made Easy

Zig-Zag and Spiral Traversal of a Binary Tree are some of those problems which appear different but have a lot of things in common and thus, can also be solved easily using a common approach.

Let's understand what a Zig-Zag & Spiral traversal exactly is :

Zig-Zag traversal for the above binary tree is :
                                                               1
                                                             3   2
                                                        4   5   6    7
                                                       11   10  9   8
So, how did we get this output?
i. We simply printed our first level in Left To Right direction obtained -> 1
ii. Then, printed the second level in Right to Left direction thus obtained -> 3,  2
Similarly, did this for other levels as well until we reach the last level.

Zig-Zag Traversal
"For every odd level print that level's node in Left to Right direction and for every even level print that level's node in Right to Left direction until we reach the last level".

Spiral Traversal for the above binary tree is :
                                                               1
                                                      11   10  9   8
                                                             2   3
                                                        7   6   5   5

So, how did we get this output? 
Unlike Zig-Zag traversal we're not going to traverse a tree level by level instead we'll use 2 pointers top & bottom which represent the first level and last level of the binary tree respectively.
1. We'll print the top level in Left To Right direction this will give us -> 1 then top++
2. We'll print the bottom level in Right To Left direction which will give us -> 11, 10, 9, 8 then bottom--
We'll repeat steps 1 and 2  while(top<=bottom)

Spiral Traversal
"For every top-level print that level's node in Left to Right direction and for every bottom level print that level's node in Right to Left direction while (top<=bottom)".

This is how our binary tree looks like after marking directions & levels :

Implementing what we just discussed :

Zig-Zag Traversal

//function for finding the number of levels in a binary tree
int height(Node *root)
{
    if(root==NULL)
        return 0;
    else
    {    int left_h=height(root->left);
        int right_h=height(root->right);
        return max(left_h,right_h)+1;
    }
}

// function for printing nodes in Right To Left Direction
void right_to_left(Node *root,int h,vector <int> &res)
{
    if(root==NULL)
        return ;
    if(h==1)
        res.push_back(root->data); // include this node
    else
        if(h>1)
        {
            right_to_left(root->right,h-1,res);
            right_to_left(root->left,h-1,res);
        }
}

// function for printing nodes in Left To Right Direction
void left_to_right(Node *root,int h,vector<int> &res)
{
    if(root==NULL)
        return ;
    if(h==1)
        res.push_back(root->data);
    else
        if(h>1)
        {
            left_to_right(root->left,h-1,res);
            left_to_right(root->right,h-1,res);
        }
}

// return a vector containing the zig zag traversal for given Binary Tree
vector <int> zigZagTraversal(Node* root)
{
    bool flag=true;
    int h=height(root);
    vector<int> res;
    for(int i=1;i<=h;i++)
    {
        if(flag==true)
        {
            left_to_right(root,i,res);
            flag=false;
        }
        else
        if(flag==false)
        {
            right_to_left(root,i,res);
            flag=true;
        }
    }
    return res;
} 

Spiral Traversal

//function for finding the number of levels in a binary tree
int height(Node *root)
{
    if(root==NULL)
        return 0;
    else
    {    int left_h=height(root->left);
        int right_h=height(root->right);
        return max(left_h,right_h)+1;
    }
}

// function for printing nodes in Right To Left Direction
void right_to_left(Node *root,int h,vector <int> &res)
{
    if(root==NULL)
        return ;
    if(h==1)
        res.push_back(root->data); // include this node
    else
        if(h>1)
        {
            right_to_left(root->right,h-1,res);
            right_to_left(root->left,h-1,res);
        }
}

// function for printing nodes in Left To Right Direction
void left_to_right(Node *root,int h,vector<int> &res)
{
    if(root==NULL)
        return ;
    if(h==1)
        res.push_back(root->data);
    else
        if(h>1)
        {
            left_to_right(root->left,h-1,res);
            left_to_right(root->right,h-1,res);
        }
}

// return a vector containing the spiral traversal for given Binary Tree
vector <int> spiralTraversal(Node* root)
{
    bool flag=true;
    int h=height(root);
    vector<int> res;
    int i=1;    
    while(i<=h)
    {
        if(flag==true)
        {
            left_to_right(root,i,res);
            flag=false;
            i++;
        }
        else
        if(flag==false)
        {
            right_to_left(root,h,res);
            flag=true;
            h--;
        }
    }
    return res;
} 

So,  you can check as I said both the problems are quite similar to each other and thus, were solved using a common approach.

I hope this tutorial helped you!
Happy Coding!