Monday, 19 January 2015

Finding the mirror of the binary tree with the solution in C++ with example


Finding the mirror of the binary tree with the solution in Cpp and explain with examples:


The mirror of the binary tree means change a tree so that the roles of the left and right pointers are swapped at every node. Let us consider the sample example tree.

             14

             / \

            12  15

           / \

         11  13  


is changed to...
                              14

                             / \

                            15  12

                           / \

                          13   11





To get the mirror of the binary tree we need to write the solution using recursion.
As it happens, this can be accomplished without changing the root node
pointer, so the return-the-new-root construct is not necessary. Alternately, if you do not want to change the tree nodes, you may construct and return a new mirror tree based on the original tree.
Function prototype is

 void mirror(struct node* node)

The solution is shown below

void FindMirror (struct stNode* pstNode)
{

if (pstNode == NULL) {
  return;
}
else {
     struct stNode* pstTempNode;

    // do the subtrees

     FindMirror (pstNode->left);

    FindMirror (pstNode->right);

    // swap the pointers in this pstNode

    pstTempNode = pstNode->left;

    pstNode->left = pstNode->right;

    pstNode->right = pstTempNode;

  }

}

No comments: