Determine if Two Binary Trees are identical.


How to determine if two Binary Trees are Identical?



Two Binary Trees are considered equal if they are structurally identical and the nodes have the same value.
 

See below image for better understanding of which Trees are called Identical and which not.




Java Program to Check if Two Trees are Identical

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

CheckTwoTreesAreIdentical.java


package tree;

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){
   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;
 }
}




Enjoy !!!! 

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

2 comments

The sequence in which nodes are being added (addNode) also plays an important role

Reply

Michael, you are right. addNode method coded in this example adds node in Binary Search Tree (BST) fashion. Our objective is to identify whether given two Binary Trees are Identical or not, for this addNode method is just a utility to create a tree in a way you want.

Reply

Post a Comment