Java program to Check if two trees are Mirror

In this tutorial, we will see how to check if two given trees are mirror to each other in Java.

Checking if two trees are mirror in Java

What are mirror trees?
Given 2 trees, if mirror representation of one tree exactly represents the other then those trees are mirror trees.
In other words, the left subtree of one tree should exactly match with right subtree of other tree and vice-versa.

Algorithm

  1. We first check if both trees are non-empty.
  2. If yes, we return true.
  3. Else we check if either one is non-empty, in that case, we return false.
  4. Since we need the left subtree of one tree to be equal to right subtree of other tree and vice-versa.
    We recursively call our function by passing left subtree of one tree and right subtree of another tree.
    Again we call the function by passing right subtree of one tree and left subtree of the other tree.

Code to check if two trees are mirror in Java

class Node  
{ 
    int data; 
    Node left, right; 
  
    public Node(int x) 
    { 
        this.data = x; 
        this.left=null;
        this.right=null;
        
    } 
} 
  
public class MirrorTrees  
{ 
    //Create 2 trees
    Node firstTree, secondTree;
    
    
    //Function which will check if
    //given trees are mirror
    boolean areMirror(Node firstTree, Node secondTree)  
    { 
        
        //Base case
        if (firstTree == null && secondTree == null) 
            return true; 
  
        //If only one is empty then the
        //other tree is not , so they can't
        //be mirror trees
        if (firstTree == null || secondTree == null)  
            return false; 
  
        //If they are non-empty then
        //check for values in the nodes
        //then call the function recursively
        //by passing left of a tree and right of the
        //other tree as one call,
        // and right of a tree and left
        //of the other tree as another call
        return firstTree.data == secondTree.data 
                && areMirror(firstTree.left, secondTree.right) 
                && areMirror(firstTree.right, secondTree.left); 
    } 
  
    public static void main(String[] args)  
    { 
        
        /*The trees are
         
              1         1
             / \       / \
            2   3     3   2
           / \           / \
          4   5         5   4
          
        */  
           
        MirrorTrees mt = new MirrorTrees(); 
        Node firstTree = new Node(1); 
        Node secondTree = new Node(1); 
        firstTree.left = new Node(2); 
        firstTree.right = new Node(3); 
        firstTree.left.left = new Node(4); 
        firstTree.left.right = new Node(5); 
  
        secondTree.left = new Node(3); 
        secondTree.right = new Node(2); 
        secondTree.right.left = new Node(5); 
        secondTree.right.right = new Node(4); 
  
        if (mt.areMirror(firstTree, secondTree)){ 
            System.out.println("They are mirror trees"); 
        }
        else{
            System.out.println("They are not mirror trees"); 
        }
  
    } 
}

Output

They are mirror trees

Leave a Reply

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