Why mirroring tree is not working when using inorder traversal to visit all the nodes?

Question

So basically I need to write a function that mirrors a binary tree. [Mirror trees example1

My approach : visit all nodes once and swap left and right children. To traverse we can use any of the three traversals. When I am using preorder and postorder, I am getting the desired result but not with inorder!

void asd(struct node* root)
    {if(root == NULL)
        return;
    asd(root->leftChild);
    struct node* t;
            t=root->leftChild;
            root->leftChild= root->rightChild;
            root->rightChild =t;
      asd(root->rightChild);
        }

My function for mirroring with inorder traversal. I am not able to understand why?

What result do you get from this program? Any error? We will not be able to help until we see the result — Anand Vaidya
for inserted array { 27, 14, 35, 10, 19, 31, 42 }. Before mirroring Preorder =27 14 10 19 35 31 42 , after mirroring preorder =27 35 31 42 14 10 19. Actually after mirroring it should be = 27 35 42 31 14 19 10. — Vimath

Anand Vaidya Anand Vaidya · Accepted Answer · 2019-12-08T09:46:03

I think the problem is with your traversal order

So, This is what happening as I can forsee -

{if(root == NULL)
    return;

Perfectly fine. Then you swap the leftchild and right child -

struct node* t;
        t=root->leftChild;
        root->leftChild= root->rightChild;
        root->rightChild =t;

So far good, but now your right child has become your left child, and left child has become right child. Now you call

asd(root->rightChild);

assuming you are processing right child, but actually you are processing left child again, because it has exchanged it's place.

The solution will be either pre-order or postorder, which will be straight forward. If you are keen on using inorder, then you will have to tweak the code a little. process left child again, as its originally was the right child.

void asd(struct node* root)
{if(root == NULL)
    return;
asd(root->leftChild);
struct node* t;
        t=root->leftChild;
        root->leftChild= root->rightChild;
        root->rightChild =t;
asd(root->leftChild);
    }

Hope this helps!

Why mirroring tree is not working when using inorder traversal to visit all the nodes?

1 Answers