Iterative method to check if two trees are mirror of each other in Java

In this tutorial, we are going to learn an iterative approach to check if trees are mirror images. So, we will be comparing two trees’ returns true if both the trees are mirror images of each other.

Two trees are mirror images of each other when in the non-leaf nodes the left and right child are exchanged. We will be using a stack as it is a good approach when we are working with reverse. Inorder and reverse inorder traversal(It is a traversal technique in which first we traverse right, root and then left subtree) will be used to traverse the tree.

These are the steps that we will follow in order to check: –

1. We will traverse in inorder fashion for one tree and for reverse inorder for another tree.
2. After that we will check for each value in each traversal and if values are not the same than these are not mirror images.
3. If values are the same and in both iteration, if one if null other is not then these are not.

Code: –

import java.util.*; 
import java.lang.*;

class Main{  
static class Node  
{  
    int value;  
    Node left;
    Node right;  
} 
//Creating new node
static Node createNode(int value)  
{  
    Node n= new Node();  
    n.value = value;  
    n.left = null; 
    n.right = null;  
    return n;  
}  
static String checkMirrorTree(Node r1, Node r2)  
{  
    Stack<Node> stack1 = new Stack<Node> (); 
    Stack<Node> stack2  = new Stack<Node> ();  
    while (true)  
    {  
        //Inorder and reverse inorder traversal  
        while (r1 != null && r2 != null)  
        {  
            if (r1.value != r2.value)  {
                return "Not A Mirror Image";
            }  
            stack1.push(r1);  
            stack2.push(r2);  
            r1 = r1.left;// Seeing left subtree  
            r2 = r2.right;// Seeing right subtree      
        }  
        // If one null other not null than not a Mirror image
        if (!(r1 == null && r2 == null))  {
            return "Not A Mirror Image";
        }  
        if (!stack1.isEmpty() && !stack2.isEmpty())  
        {  //Seeing node now
            r1 = stack1.peek();  
            r2 = stack2.peek();  
            stack1.pop();  
            stack2.pop();  
            // See right subtree
            r1 = r1.right;  
            // See left subtree
            r2 = r2.left;  
        }      
        else{
            break;
        }  
    }  
    return "Tree Are Mirror To Each Other";  
}  
public static void main(String[] args)  
{  
    Node r1 = createNode(9);                             
    r1.left = createNode(5);     
    r1.right = createNode(1);    
    r1.right.left = createNode(3);
    r1.right.right = createNode(7);
      
    Node r2 = createNode(9);                           
    r2.left = createNode(1);       
    r2.right = createNode(5);
    r2.left.left = createNode(7);
    r2.left.right = createNode(3);  
          
    System.out.println(checkMirrorTree(r1, r2));  
} 
}

Output: –

Tree Are Mirror To Each Other

This is how we check if the trees are mirror images or not.

Also read: –

Inorder tree traversal with Recursion in Java