Check if two trees are mirror images of each other

How to check if two binary trees are mirror images of each other?

---

In this post we will look at algorithm to check if two trees are mirror images of each other with Java program.

See below image for better understanding of which Trees are called Mirror Image of each other

Check if two trees are mirror images of each other

Algorithm.

---

Two Binary Trees are considered mirror image of each other if left and right child of every node is inter-exchange. (Left child moved to Right and Right child moved to Left)

lets understand in simple language, what will happen if you look yourself in a mirror, you will notice if say you are wearing a shirt with pocket on right side than in mirror you will notice the same pocket on left side.

so we can say in mirror right goes to left and left moves to right.

Similarly, in binary trees if we want to check if given two binary trees(A and B) are mirror image of each other than what we have to do is traverse A in prorder traversal(root, left, right) and B in mirror preorder traversal(root, right, left) and compare both binary tree at the same time to see if any of below condition is true, If yes,  then A and B is not a mirror image. 

1. If node in tree A is present and node in tree B is not present then is not a mirror image of each other.
2. If node in tree B is present and node in tree A is not present then is not a mirror image of each other.
3. If the node in both the tree are present and is not same then is not a mirror image of each other.

Java Program to check if two trees are a mirror image of each other or not.

---

CheckTwoTreesAreMirrorOfEachOther.java

package javabypatel.tree;

class CheckTwoTreesAreMirrorOfEachOther{
 
 public static void main(String[] args) {
  
  Node rootNode1=null; 
  rootNode1  = addNode(rootNode1, 50, true);
  rootNode1  = addNode(rootNode1, 20, true);
  rootNode1  = addNode(rootNode1, 80, true);
  rootNode1  = addNode(rootNode1, 10, true);
  rootNode1  = addNode(rootNode1, 30, true);
  rootNode1  = addNode(rootNode1, 70, true);
  rootNode1  = addNode(rootNode1, 100, true);
  
  Node rootNode2=null; 
  rootNode2  = addNode(rootNode2, 50, false);
  rootNode2  = addNode(rootNode2, 20, false);
  rootNode2  = addNode(rootNode2, 80, false);
  rootNode2  = addNode(rootNode2, 10, false);
  rootNode2  = addNode(rootNode2, 30, false);
  rootNode2  = addNode(rootNode2, 70, false);
  rootNode2  = addNode(rootNode2, 100, false);
  
  
  System.out.println(isMirrorImage(rootNode1, rootNode2));
 }
 
 private static boolean isMirrorImage(Node tree1, Node tree2){
  if(tree1==null && tree2==null){ //Both trees are NULL
   return true;
  }
  if(tree1==null || tree2==null){ //Any one of the Tree is NULL
   return false;
  }  
  if(tree1.getData() != tree2.getData()){ // Data check
   return false;
  }
  
  boolean leftCheck = isMirrorImage(tree1.getLeft(), tree2.getRight());
  boolean rightCheck = isMirrorImage(tree1.getRight(), tree2.getLeft());
  
  if(leftCheck && rightCheck){
   return true;
  }else{
   return false;
  }
 }

 private static Node addNode(Node rootNode, int i, boolean isRootNode1) {
  if(rootNode==null){
   return new Node(i);
  }else{
   if(i > rootNode.getData()){
    if(isRootNode1){
     Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode1);
     rootNode.setRight(nodeToAdd);
    }else{
     Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode1);
     rootNode.setLeft(nodeToAdd);
    }

   }else{
    if(isRootNode1){
     Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode1);
     rootNode.setLeft(nodeToAdd);
    }else{
     Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode1);
     rootNode.setRight(nodeToAdd);
    }
   }
  }
  return rootNode;
 }
}

Node.java

package javabypatel.tree;

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

 public Node getLeft() {
  return left;
 }

 public void setLeft(Node left) {
  this.left = left;
 }

 public Node getRight() {
  return right;
 }

 public void setRight(Node right) {
  this.right = right;
 }

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }
}

Find Kth SMALLEST element in BST(Binary Search Tree)

Check whether Binary Tree is foldable or not.

Check if two nodes are cousins in a Binary Tree.

Get Level/Height of node in binary tree

Print nodes at K distance from Leaf node in Binary tree.

Construct a Binary Tree from In-order and Post-order traversals.

Print Nodes in Top View of Binary Tree.

Zig Zag Traversal of Binary Tree.

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.