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