Check a given two Binary Trees are Mirror Image of each other.


How to determine a given two Binary Trees are Mirror Image of each other?



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

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





Java Program to check a given two Binary Trees are Mirror Image of each other.

Container: Node.java

package 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;
 }
}

CheckTwoTreesAreMirrorOfEachOther.java


package 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;
 }
}



Enjoy !!!! 

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

2 comments

Did you mean to use bit-wise AND here?

if(tree1==null & tree2==null){ //Both trees are NULL

Reply

Hi thirteenvegetables,

It was typo. I updated post.
Many thanks for informing and appreciate your time on this.

Reply

Post a Comment