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