Java program to Determine if Two Trees are Identical

In this tutorial, I will be showing how to check if two trees are identical or not in Java. I will be using Java language to implement my approach. Let us get started.

Check if two trees are identical in Java

I have used binary trees to check whether two trees are identical or not. For two trees to be identical, the following conditions need to be checked:

  1. If both the trees are empty, they are identical trees.
  2. When both the trees have further children and sub-tree, first check if the root nodes are equal or not. If they are equal, call the function recursively and check for further sub-tree.
  3. If one tree has a child and the other does not have, or for any other condition, the trees will be non-identical.

I will be using OOPs concepts of Java to code my approach. I have made two classes: node and Identical_Tree.

The class node has the basic structure of the tree defined. The class Identical_Tree has two functions: check_trees and main function.

In the check_trees function, I have passed two parameters which are node A and node B of the two trees. After that, I have used if-else statements to check for the various conditions that are explained above in detail. check_trees is a boolean function that returns true or false according to the conditions defined. Hence, at the end of this function, it returns a boolean value.

In the main() function, an object of the Scanner class is made so as to take user input. After this, an instance of the class is defined, which will be used to call functions and methods. I have given input on the two binary trees that need to be checked. Finally, I check whether the check_trees function returns a true or false value and displays the message accordingly.

I have shown my code below:

//Class 1

public class node
{
    int key;
    node left, right;

    node(int val)
    {
        key = val;
        left =  right = null;
    }
}

//Class 2

import java.util.*;
public class Identical_Tree
{
    node rootA, rootB;
    
    boolean check_trees(node A, node B)
    {
        //if both trees are empty, them they are identical
        if(A == null && B == null)
        {
            return true;
        }

        //if both trees have further sub-trees/ or children
        //check for futher sub-trees by recursive function call
        if((A != null && B != null) && A.key == B.key)
        {
            return ((check_trees(A.left, B.left))
                    && (check_trees(A.right, B.right ))
                    );
        }

        //if one tree has child and the other doesn't then
        //no need to check further
        else
        {
            return false;
        }
    }

    public static void main(String[] args)
    {
        Scanner ob = new Scanner(System.in);
        
        Identical_Tree t = new Identical_Tree();
        
        System.out.println("Enter tree A");

        t.rootA = new node(ob.nextInt());
        t.rootA.left = new node(ob.nextInt());
        t.rootA.right = new node(ob.nextInt());
        t.rootA.left.left = new node(ob.nextInt());
        t.rootA.left.right = new node(ob.nextInt());
        t.rootA.right.left = new node(ob.nextInt());
        t.rootA.right.right = new node(ob.nextInt());

        System.out.println("Enter tree B");

        t.rootB = new node(ob.nextInt());
        t.rootB.left = new node(ob.nextInt());
        t.rootB.right = new node(ob.nextInt());
        t.rootB.left.left = new node(ob.nextInt());
        t.rootB.left.right = new node(ob.nextInt());
        t.rootB.right.left = new node(ob.nextInt());
        t.rootB.right.right = new node(ob.nextInt());

        if(t.check_trees(t.rootA, t.rootB))
        {
            System.out.println("The trees are identical");
        }
        else
        {
            System.out.println("The trees a non-identical");
        }
        
    }
}

Input:

I have entered the two binary trees:

              1                                                   1

           /     \                                            /     \

         2         3                                         2         3

       /   \     /   \                                    /   \     /   \

      4     5   6     7                                  4     5   6     7

Output:

The trees are identical

 

Leave a Reply

Your email address will not be published. Required fields are marked *