Check two binary trees are equal or identical or same (DFS & Examples)

• Given two binary trees, find out whether one binary tree is equal or identical or same to another binary tree.
• Traverse the binary trees using depth first search (DFS) recursive algorithm
• What identical binary tree?
  • Composition of binary trees should be same.
  • Data nodes of binary trees (at respective position) should be same.
• We have discussed similar problem to check given binary tree is mirror of another binary tree.

Examples to check binary trees are equal or identical

Example 1: Identical or Same binary trees (Fig 1)

• Structure of both the trees is same
• Data nodes of corresponding binary trees are same.

Example 2: Non-Identical binary trees (Fig 2)

• Structure of both the trees is same
• Data nodes of corresponding binary trees are NOT same.
  • Node C and Node R has different values.
  • Node D and Node S has different values.

Algorithm to check binary trees are identical

1. Check both nodes of both tree1 and tree2
   • If tree1 and tree2 is null,  tree traversal completed successfully.
   • return true
2. If node of any of tree is null.
   • Trees are not identical, return false .
3. Compare data of tree1 and tree2
   • Data is same for both nodes
     • Go through Left subtree and right subtree
       • Traverse Left child of binary tree1 and left child of tree2
       • Traverse Right child of binary tree1 and right child of tree2
   • Data is not same
     • Trees are not identical, return false
4. After above traversal, we will know whether binary trees are identical or equal or same.
5. Time Complexity:
   • Let tree1 contains p number of nodes & tree2 contains q number of nodes.
   • Time Complexity: O(p) where p > q

Program – Check binary tree is identical to another binary tree:

1.) BinaryTreesAreSame class: BinaryTreesAreSame class is responsible for checking binary trees are identical or same or equal using recursive algorithm.

package org.learn.Question;

import org.learn.PrepareTree.Node;

public class BinaryTreesAreSame {
 public static boolean isSameBinaryTree(Node tree1, Node tree2) {
  if (tree1 == null && tree2 == null) {
   return true;
  }
  if (tree1 == null || tree2 == null) {
   return false;
  }
  if (tree1.data != tree2.data)
   return false;

  if (false == isSameBinaryTree(tree1.left, tree2.left))
   return false;

  if (false == isSameBinaryTree(tree1.right, tree2.right))
   return false;

  return true;
 }
}

2) App Class:

• We are constructing the Binary Tree in main method.
• We are calling BinaryTreesAreSame.isSameBinaryTree, to check both binary trees are identical or equal or same.

package org.learn.Client;

import org.learn.PrepareTree.Node;
import org.learn.Question.BinaryTreesAreSame;

public class App 
{
 public static void main( String[] args )
    {  
  Node tree1 = Node.createNode(50);
  tree1.left = Node.createNode(30);
  tree1.right = Node.createNode(30);
  // left sub tree
  tree1.left.left = Node.createNode(40);
  tree1.left.right = Node.createNode(10);

  // right subtree
  tree1.right.left = Node.createNode(30);
  tree1.right.right = Node.createNode(60);
  
  Node tree2 = Node.createNode(50);
  tree2.left = Node.createNode(30);
  tree2.right = Node.createNode(30);
  // left sub tree
  tree2.left.left = Node.createNode(40);
  tree2.left.right = Node.createNode(10);

  // right subtree
  tree2.right.left = Node.createNode(30);
  tree2.right.right = Node.createNode(60);

  boolean isSame = BinaryTreesAreSame.isSameBinaryTree(tree1, tree2);
  if(isSame) {
   System.out.println("Trees are identical");
  } else {
   System.out.println("Trees are not identical");
  }
    }
}

3.) Node Class: Node class representing the nodes of Binary Tree.

package org.learn.PrepareTree;

public class Node {
 public int data;
 public Node left;
 public Node right;

 public Node(int num) {
  this.data = num;
  this.left = null;
  this.right = null;
 }

 public Node() {
  this.left = null;
  this.right = null;
 }
 public static Node createNode(int number) {
  return new Node(number);
 }
}

Output – Check binary trees are same (Fig 1)

Trees are identical

Download Code – Check Binary Trees are Identical or Same