This blog will soon be merged with

JavaByPatel

which explains each solution in detail, to visit new blog, click JavaByPatel

Monday, 29 June 2015

Check if two binary trees are mirror image of each other. OR To check if two trees are inversions of each other or not.


package tree;

/*
  Write a Function to Check a given two Binary Trees are Mirror of each other.
  (Mirror Tree: Mirror Tree of a binary tree is where left and right child of every node of given binary tree is interexchange.)

  Input:      
                
              50                          50           
             /  \                        /  \
            /    \                      /    \
          20      80                  80      20
         /  \    /  \                /  \    /  \
        10  30  70  100            100  70  30  10     
            
  output: true
*/
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==tree2){ //Both NULL check
   return true;
  }
  if(tree1==null || tree2==null){ //Any one of them is NULL check
   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;
 }

}