print level order traversal of binary tree in Zigzag manner

Question

I have to print the nodes of a binary tree using level order traversal but in spiral form i.e nodes at different level should be printed in spiral form.

for eg: If the tree look like:

The output should be 10 5 20 25 15 6 4.

The algorithm i used is simple and is just a small variation of level order traversal. I just took a variable p.if the variable is equal to 1 than print the order at a given level left to right , if it is -1 print right to left.

void getlevel(struct node *root,int n,int p)
{
        if(root==NULL)
        return;
        if(n==0)
        {
                printf("%d ",root->info);
                return;
        }
        if(n>0)
        {
            if(p==1)
            {
                 getlevel(root->left,n-1,p);
                 getlevel(root->right,n-1,p);
            }
            if(p==-1)
            {
                 getlevel(root->right,n-1,p);
                 getlevel(root->left,n-1,p);
            }
        }
}

I am getting the answer but the worst case complexity is probably O(n^2) in case of skewed tree.

Can there be a better algorithm for this task?..

My entire program is here

Answer 1

Yes.

You can do something similar to normal level order traversal.

You have to use two stacks

1. first stack for printing from left to right
2. second stack for printing from right to left.

Start from the root node. Store it's children in one stack. In every iteration, you have nodes of one level in one of the stacks. Print the nodes, and push nodes of next level in other stack. Repeat until your reach the final level.

Time Complexity O(n) and space complexity O(n).