Check two binary trees are equal/identical/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

Check both nodes of both tree1 and tree2
- If tree1 and tree2 is null, tree traversal completed successfully.
- return true
If node of any of tree is null.
- Trees are not identical, return false .
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
After above traversal, we will know whether binary trees are identical or equal or same.
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

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

Examples to check binary trees are equal or identical

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

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

Algorithm to check binary trees are identical

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

Output – Check binary trees are same (Fig 1)

Download Code – Check Binary Trees are Identical or Same

Examples to check binary trees are equal or identical

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

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

Algorithm to check binary trees are identical

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

Output – Check binary trees are same (Fig 1)

You may also like: