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: –
- We will traverse in inorder fashion for one tree and for reverse inorder for another tree.
- After that we will check for each value in each traversal and if values are not the same than these are not mirror images.
- 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: –
Leave a Reply