title: print level order traversal of binary tree in Zigzag manner
body: <p>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.</p>
  
  <p>for eg: If the tree look like:</p>
  
  <p><img src="https://i.stack.imgur.com/DJCOE.jpg" alt=""></p>
  
  <p>The output should be 10 5 20 25 15 6 4.</p>
  
  <p>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.</p>
  
  <pre><code>void getlevel(struct node *root,int n,int p)
  {
          if(root==NULL)
          return;
          if(n==0)
          {
                  printf("%d ",root-&gt;info);
                  return;
          }
          if(n&gt;0)
          {
              if(p==1)
              {
                   getlevel(root-&gt;left,n-1,p);
                   getlevel(root-&gt;right,n-1,p);
              }
              if(p==-1)
              {
                   getlevel(root-&gt;right,n-1,p);
                   getlevel(root-&gt;left,n-1,p);
              }
          }
  }
  </code></pre>
  
  <p>I am getting the answer but the worst case complexity is probably O(n^2) in case of skewed tree.</p>
  
  <p>Can there be a better algorithm for this task?..</p>
  
  <p>My entire program is <a href="http://ideone.com/pOCdQ1" rel="noreferrer">here</a></p>