1. Introduction

In computational problems involving binary trees, it is often necessary to compare two trees for equality. Two binary trees are considered identical if they have the same structure and the nodes have the same value. In this article, we will explore how to determine if two binary trees are identical using a recursive approach.

2. Program Steps

1. If both trees are null, then they are identical.

2. If one of the trees is null and the other isn’t, they are not identical.

3. Compare the root values of both trees.

4. Recursively compare the left subtree of tree1 with the left subtree of tree2 and the right subtree of tree1 with the right subtree of tree2.

3. Code Program

class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root1, root2;

    boolean identicalTrees(Node a, Node b) {
        if (a == null && b == null)
            return true;

        if (a != null && b != null)
            return (a.data == b.data && identicalTrees(a.left, b.left) && identicalTrees(a.right, b.right));

        return false;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        tree.root1 = new Node(1);
        tree.root1.left = new Node(2);
        tree.root1.right = new Node(3);
        tree.root1.left.left = new Node(4);
        tree.root1.left.right = new Node(5);

        tree.root2 = new Node(1);
        tree.root2.left = new Node(2);
        tree.root2.right = new Node(3);
        tree.root2.left.left = new Node(4);
        tree.root2.left.right = new Node(5);

        if (tree.identicalTrees(tree.root1, tree.root2))
            System.out.println("Both trees are identical");
        else
            System.out.println("Trees are not identical");
    }
}

Output:

Both trees are identical

4. Step By Step Explanation

1. The Node class represents each node in the binary tree with attributes data, left, and right which signify the value, left child, and right child respectively.

2. The BinaryTree class contains the method identicalTrees which compares two binary trees for equality.

3. The comparison starts from the root. If both the trees' roots are null, then they are deemed identical. If only one of them is null, they are not identical.

4. If both nodes are not null, their data values are compared. Additionally, their left and right children are also compared recursively.

5. In the main function, two sample binary trees are constructed and the identicalTrees method is called to determine their equality. The output is then printed based on the comparison result.