This blog will soon be merged with

JavaByPatel

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

Sunday, 28 June 2015

Given two Binary Trees, write a function to check if they are same. OR Check if given Two Binary Trees are Identical.


package tree;

/*
 Given two binary trees, write a function to check if they are equal or not. 
 Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
 
  Note: Below trees are not identical. Data in all the below trees are same but are structurally different.
 
   B         C        C      A
  / \       / \      / \      \
 A   D     B   D    A   D      B
    /     /          \          \
   C     A            B          C
                                  \
                                   D
                                   
  Identical Trees example below,
   
          50                  50           
         /  \                /  \
        /    \              /    \
      20      80          20      80
     /  \    /  \         / \    /  \
    10  30  70  100     10  30  70  100                                   
                                  
 */
public class CheckTwoTreesAreIdentical {

 private Node rootNode1;
 private Node rootNode2;

 public static void main(String[] args) {
  new CheckTwoTreesAreIdentical();
 }

 public CheckTwoTreesAreIdentical() {
  rootNode1 = addNode(rootNode1, 100);
  rootNode1 = addNode(rootNode1, 30); 
  rootNode1 = addNode(rootNode1, 20); 
  rootNode1 = addNode(rootNode1, 40);
  rootNode1 = addNode(rootNode1, 200);

  rootNode2 = addNode(rootNode2, 100); 
  rootNode2 = addNode(rootNode2, 60); 
  rootNode2 = addNode(rootNode2, 20); 
  rootNode2 = addNode(rootNode2, 40);
  rootNode2 = addNode(rootNode2, 200);

  System.out.println("Result :"+checkTreeAreIdentical(rootNode1, rootNode2));
 }

 private boolean checkTreeAreIdentical(Node tree1, Node tree2){
  if(tree1==null && tree2==null){ //OR if(tree1 == tree2)
   return true;
  }

  if(tree1==null || tree2==null){
   return false;
  }

  //Data check, Left Tree check and Right Tree check can be done in same line,
  //but for simplicity I have separated it.
  if(tree1.getData()!=tree2.getData()){ 
   return false;
  }

  boolean isLeftSame = checkTreeAreIdentical(tree1.getLeft(), tree2.getLeft());
  boolean isRightSame = checkTreeAreIdentical(tree1.getRight(), tree2.getRight());

  if(isLeftSame && isRightSame){
   return true;
  }else{
   return false;
  }
 }

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

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