Given a BST, create a mirror of it.

Problem
Change a tree so that the roles of the left and right pointers are swapped at every node.

Example
So the tree…
       4
      / \
     2   5
    / \
   1   3
is changed to…
       4
      / \
     5   2
        / \
       3   1
The solution is short, but very recursive. 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.

Recursive solution

/\*  
 Change a tree so that the roles of the  
 left and right pointers are swapped at every node.  So the tree...  
       4  
      / \\  
     2   5  
    / \\  
   1   3  
 is changed to...  
       4  
      / \\  
     5   2  
        / \\  
       3   1  
\*/  
void mirror(struct node\* node) {  
  if (node==NULL) {  
    return;  
  }  
  else {  
    struct node\* temp;  
    // do the subtrees  
    mirror(node->left);  
    mirror(node->right);  
    // swap the pointers in this node  
    temp = node->left;  
    node->left = node->right;  
    node->right = temp;  
  }  
}

Iterative solution
Here is the solution:

void MirrorIterative(Node \* tree)  
{  
 if (!tree)  
  return;  
  
 Stack s;  
 s.push(tree);  
 while(!s.empty())  
 {  
  Node \* current = s.pop();  
    
  // Swap the children  
  //  
  Node \* temp = current->right;  
  current->right = current->left;  
  current->left = temp;  
  
  // Push the children on the stack  
  //  
  if (current->right)  
   s.push(current->right);  
  
  if (current->left)  
   s.push(current->left);  
 }  
}

This is similar to level order traversal.Thanks.

See also