Reversing Alternate Levels of a perfect binary tree
<p>The problem statement is:</p>

<blockquote>
  <p>Given a Perfect Binary Tree, reverse the alternate level nodes of the binary tree.</p>
</blockquote>

<pre><code>Given tree: 
               a
            /     \
           b       c
         /  \     /  \
        d    e    f    g
       / \  / \  / \  / \
       h  i j  k l  m  n  o 

Modified tree:
               a
            /     \
           c       b
         /  \     /  \
        d    e    f    g
       / \  / \  / \  / \
      o  n m  l k  j  i  h 
</code></pre>

<p>Solution 3 from  <a href="http://www.geeksforgeeks.org/reverse-alternate-levels-binary-tree/" rel="nofollow">this site</a> provides a particularly elegant solution in which it uses a the swap method on the nodes of the even numbered levels of the tree:void </p>

<pre><code>preorder(struct Node *root1, struct Node* root2, int lvl)
{
    // Base cases
    if (root1 == NULL || root2==NULL)
        return;

    // Swap subtrees if level is even
    if (lvl%2 == 0)
        swap(root1-&gt;key, root2-&gt;key);

    // Recur for left and right subtrees (Note : left of root1
    // is passed and right of root2 in first call and opposite
    // in second call.
    preorder(root1-&gt;left, root2-&gt;right, lvl+1);
    preorder(root1-&gt;right, root2-&gt;left, lvl+1);
}

// This function calls preorder() for left and right children
// of root
void reverseAlternate(struct Node *root)
{
   preorder(root-&gt;left, root-&gt;right, 0);
}
</code></pre>

<p>For some reason, though, when the in order traversals of the original and modified versions of the tree are printed, they yield the same output:</p>

<pre><code>Inorder Traversal of given tree
h d i b j e k a l f m c n g o 

Inorder Traversal of modified tree
h d i b j e k a l f m c n g o 
</code></pre>

<p>For some reason, the writers of the article didn't recognize the issue and left this as the final solution as it is the shortest of the three methods I'm assuming. Method 2 in the post is longer, but it produces the correct output. </p>

<p><strong>Is there a bug with the solution that is causing the output for both versions of the tree to be the same?</strong></p>