Java Code to check if two binary trees are identical or not

Java Code to check if two binary trees are identical or not

The idea is to traverse both trees and compare value at their root node. If the value matches, we recursively check if left subtree of first tree is identical to left subtree of second tree and right subtree of first tree is identical to right subtree of second tree. If the value at their root node differs, the trees violates data property. If at any point in the recursion, the first tree is empty & second tree is non-empty or second tree is empty & first tree is non-empty, the trees violates structural property and they cannot be identical.

// Java program to see if two trees are identical

  // A binary tree node

class Node 
{
    int data;
    Node left, right;  

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

  
class BinaryTree 
{
    Node root1, root2;
    /* Given two trees, return true if they are structurally identical */
boolean identicalTrees(Node a, Node b) 
    {
      /*1. both empty */
        if (a == null && b == null)
            return true;

        /* 2. both non-empty -> compare them */
        if (a != null && b != null) 
            return (a.data == b.data
           identicalTrees(a.left, b.left)
identicalTrees(a.right, b.right)); 

        /* 3. one empty, one not -> false */
        return false;
    }

    /* Driver program to test identicalTrees() function */

    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");  
    }
}