In this post, We will Write a Java program to find given two trees are mirror image or not?
This Problem is the extension of Find a mirror image of a binary tree
A mirror image of a binary tree is another binary tree with left and right children of all non-leaf nodes of the given binary tree are interchanged.
Below are the images that show the given Binary Tree & mirror image of a given binary tree.
PreOrder Output of Given Binary Tree: 1 2 4 5 3 6 7 PreOrder Mirror Image of Binary Tree: 1 3 7 6 2 5 4
If we input the Above two trees to our Algorithm then it should pass the criteria(Both trees are a mirror image of each other) and must return true.
Below is the Complete Source code:
BinaryTree.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
package com.kkjavatutorials.tree; public class BinaryTree<E extends Comparable<? super E>> { /** * This internal class represents Node of Binary tree * @author KK JavaTutorials */ public static class Node<T> { //Data hold by Binary Tree Node public T data; //Left pointer/reference public Node<T> left; //Right pointer/reference public Node<T> right; public Node(T data) { this.data = data; } } /** * Recursive method for Binary Tree preOrder Processing * @param root Node */ public void preOrder(Node<E> root) { if(root != null) { System.out.print(root.data+" "); preOrder(root.left); preOrder(root.right); } } /** * Method to find a mirror image of a binary tree * @param root of BST * @return Mirror Image of BST */ public Node<E> mirrorBinaryTree(Node<E> root){ //If root is null then return null if (root == null){ return null; } //Getting Left and Right Sub trees Node<E> left = mirrorBinaryTree(root.left); Node<E> right = mirrorBinaryTree(root.right); /*Exchange Left with right Subtree and Right with Left Subtree*/ root.left = right; root.right = left; /*finally return mirror image of given Binary Tree*/ return root; } /** * @param root1 first Binary Tree * @param root2 Second Binary Tree * @return true if both binary trees are mirror image * of each Other */ public boolean areMirrorImage(Node<Integer> root1, Node<Integer> root2) { //if both trees are null then return true if(root1 == null & root2 == null) return true; //if any one of the tree is null then return flase if(root1 == null || root2 == null) return false; //If both trees are not null return areMirrorImage(root1.left, root2.right) && areMirrorImage(root1.right, root2.left); } } |
ClientTest.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
package com.kkjavatutorials.client; import com.kkjavatutorials.tree.BinaryTree; import com.kkjavatutorials.tree.BinaryTree.Node; /** * Client Program to find given two trees * are mirror Image or not ? * @author KK JavaTutorials */ public class ClientTest { public static void main(String[] args) { // Root Node of First Tree Node<Integer> root1 = new Node<Integer>(1); Node<Integer> secondNode = new Node<Integer>(2); Node<Integer> thirdNode = new Node<Integer>(3); Node<Integer> fourthNode = new Node<Integer>(4); Node<Integer> fifthNode = new Node<Integer>(5); Node<Integer> sixthNode = new Node<Integer>(6); Node<Integer> seventhNode = new Node<Integer>(7); // Setting Left and right of root Node root1.left = secondNode; root1.right = thirdNode; root1.left.left = fourthNode; root1.left.right = fifthNode; root1.right.left = sixthNode; root1.right.right = seventhNode; // Root Node of Second Tree Node<Integer> root2 = new Node<Integer>(1); secondNode = new Node<Integer>(2); thirdNode = new Node<Integer>(3); fourthNode = new Node<Integer>(4); fifthNode = new Node<Integer>(5); sixthNode = new Node<Integer>(6); seventhNode = new Node<Integer>(7); //Setting Left and right of root Node root2.left = thirdNode; root2.right = secondNode; root2.left.left = seventhNode; root2.left.right = sixthNode; root2.right.left = fifthNode; root2.right.right = fourthNode; // Create an Instance of BinaryTree BinaryTree<Integer> binaryTree = new BinaryTree<>(); // Call for preOrder processing System.out.println("PreOrder Processing output of Both Trees are...."); binaryTree.preOrder(root1); System.out.println(); binaryTree.preOrder(root2); System.out.println(); System.out.println("-------------------------------"); /*Calling method:areMirrorImage(root1, root2) to check both trees are mirror image of each other or not?*/ boolean isMirrorImage = binaryTree.areMirrorImage(root1, root2); if (isMirrorImage) System.out.println("Both Binary Trees are mirror image of each other"); else System.out.println("Both Binary Trees are not mirror image of each other"); } } |
The output of This Program:
PreOrder Processing output of Both Trees are….
1 2 4 5 3 6 7
1 3 7 6 2 5 4
——————————-
Both Binary Trees are mirror image of each other
You May Also Like:
Introduction to Tree Data Structure
Introduction to Binary Tree
Difference between binary and binary search trees
Structure of Binary Trees
Operations and use of Binary Trees
Insert operation in a binary search tree
Delete operation in a binary search tree
Search operation in a binary search tree
Find the sum of all elements in Binary Tree
Find the height or depth of a binary tree
Binary Tree Traversals
PreOrder traversal of binary tree implementation in Java
InOrder traversal of binary tree implementation in Java
PostOrder traversal of binary tree implementation in Java
Find the node with minimum and maximum values in a Binary Search Tree
Find a mirror image of a binary tree
How do you find if two given binary trees are the same or identical
That’s all about Write a Java program to find given two trees are mirror image or not ?
If you have any feedback or suggestion please feel free to drop in below comment box.