Check if two binary trees are identical

Check if two binary trees are identical or not?

---

In this post we will check if given binary trees are identical or not using recursive approach.

 

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

Check if two binary trees are identical or not

 Algorithm to check if given two binary trees are identical

---

Two Binary Trees are considered identical or equal if they are identical in structure as well as node value in one tree should match the node value in other tree at the same location.

I recommend reading Preorder traversal of Binary tree, Preorder traversal

 

Idea is to traverse both tree at the same time in a preorder traversal and check 

1. If node exist in one tree then it should exist in other tree as well for trees to be identical. (Checking structure of the tree is same)
2. If node exist in both tree then value of the node in both tree should be equal. (Checking node data). 
3. If node doesn't exist in one tree then it should not exist in other tree as well. (Checking structure of the tree is same)

Java Program to Check if Two Trees are identical or not.

---

CheckTwoTreesAreIdentical.java

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

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.