# 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.