CODEWITHSUNDEEP
algorithmrecursiontree
loremIpsum1771
loremIpsum1771

Reputation: 2527

Reversing Alternate Levels of a perfect binary tree

The problem statement is:

Given a Perfect Binary Tree, reverse the alternate level nodes of the binary tree.

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

Solution 3 from this site 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 

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->key, root2->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->left, root2->right, lvl+1);
    preorder(root1->right, root2->left, lvl+1);
}

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

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:

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

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.

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

Upvotes: 0

Views: 170

Answers (1)

rici
rici

Reputation: 241781

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

There is no bug with the algorithm. The bug is that the main function never calls reverseAlternate(), so it simply prints the same tree twice.

Add the missing call (line 76 in the link), and it works perfectly.

Upvotes: 3

Related Questions