Wednesday, May 11, 2011

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.

0 comments:

Post a Comment