Mirror image of a binary tree

Question

Suppose there is a tree:

             1
            / \
           2   3
              / \
             4   5

Then the mirror image will be:

              1
             / \
            3   2
           / \
          5   4

Assume the nodes are of this structure:

struct node{
      node left;
      node right;
      int value;
}

Can someone suggest an algorithm for this?

Answer 1

Sounds like homework.

It looks very easy. Write a recursive routine that depth-first visits every node and builds the mirror tree with left and right reversed.

struct node *mirror(struct node *here) {

  if (here == NULL)
     return NULL;
  else {

    struct node *newNode = malloc (sizeof(struct node));

    newNode->value = here->value;
    newNode->left = mirror(here->right);
    newNode->right = mirror(here->left);

    return newNode;
  }
}

This returns a new tree - some other answers do this in place. Depends on what your assignment asked you to do :)

Answer 2

void swap_node(node n) {
  if(n != null) {
    node tmp = n.left;
    n.left = n.right;
    n.right = tmp;

    swap_node(n.left);
    swap_node(n.right);
  }
}

swap_node(root);