This algorithm is designed to take in a binary tree (not necessarily a BST/Binary Search Tree) and reverse the nodes at each level to generate the mirror image of that binary tree.

How Does it Work?

The mirror image of a binary tree is simply the result of reversing the nodes at every level. So, the trick is to recursively visit every node, starting with the root and going to its left and right sub-trees. For every node visited, including the root itself, you just swap the left and right sub-trees. When there are no nodes left (i.e. the left and right sub-trees of the current node are null), then the algorithm returns.

Sample Implementation

Here is a sample implementation of the algorithm. It is fully working code, so you may double click on it and copy the whole example into your preferred IDE to test it and debug it for better understanding. Sample output is provided below the sample.

 //Algorithm to get the mirror image of a binary tree and
 //print out the before and after images.
 public class MirrorTree {

     private static class Node {
         public int value;
         public Node left;
         public Node right;
         public Node(int value) { this.value = value; }
     }

     //Example of algorithm being used.
     public static void main(String[] args) {

         //Create a tree on which to run the mirror algorithm.
         Node root = new Node(1);
         root.left = new Node(2);
         root.left.left = new Node(3);
         root.left.right = new Node (4);
         root.right = new Node(5);
         root.right.right = new Node(6);
         root.right.right.right = new Node(7);

         //Print out the original tree.
         System.out.println("Tree before mirror:");
         printTree(root);

         //Run the mirror algorithm.
         mirror(root);

         //Print out the resulting tree.
         System.out.println("\nTree after mirror:");
         printTree(root);
     }

     //The mirror algorithm itself.
     public static void mirror(Node root) {

         //Terminate when the root is null.
         if (root == null) return;

         //Swap the left and right subtrees.
         Node tmp = root.left;
         root.left = root.right;
         root.right = tmp;

         //Recursively repeat on left and right subtrees.
         mirror(root.left);
         mirror(root.right);
     }

     //Utility function to print the binary tree as an example.
     public static void printTree(Node root) {
         if (root == null) return;
         printTree(root, 0);
     }

     //Private utility function for formatting the tree display.
     private static void printTree(Node root, int level) {
         if (root == null) return;
         printTree(root.left, level + 1);
         for (int i = 0; i < level; ++i) System.out.print("  ");
         System.out.print(root.value + "\n");
         printTree(root.right, level + 1);
     }
 }

Output From Example

This is an admittedly lazy way of printing a binary tree, but if you look at it as if the left side of your screen is the top of the screen, it gets the job done. You can see that that every node in this tree is displaying the mirror image of its original in the second printout.

 Tree before mirror:
     3
   2
     4
 1
   5
     6
       7
 
 Tree after mirror:
       7
     6
   5
 1
     4
   2
     3