Find a mirror image of a binary tree

In this post, we will learn How to write a java program to find a mirror image of a binary tree?

To implement the algorithm to find the mirror image of a given binary tree in Java. 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.

Algorithm Implementation

The left child of any node in the given tree will be the right child of the node in the mirror image. Below is the implementation for the same. The PreOrdeer traversal is just to validate the mirrored binary tree.

We will be going to use a recursive approach to find the 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

Below is the Complete Source code:

BinaryTree.java

package com.kkjavatutorials.tree;

public class BinaryTree<E extends Comparable<? super E>> {
	
	/**
	 * This internal class represents Node in 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;
    }
}

package com.kkjavatutorials.tree;

public class BinaryTree<E extends Comparable<? super E>> {

/**

* This internal class represents Node in 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;

}

ClientTest.java

package com.kkjavatutorials.client;

import com.kkjavatutorials.tree.BinaryTree;
import com.kkjavatutorials.tree.BinaryTree.Node;
/**
 * Client Program to find a mirror image
 * of a binary Search tree?
 * @author KK JavaTutorials
 */
public class ClientTest {

	public static void main(String[] args) {
		
		//Create an Instance of BinaryTree
		BinaryTree<Integer> binaryTree = new BinaryTree<>();
		
		//Root Node
		Node<Integer> rootNode = 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
		rootNode.left = secondNode;
		rootNode.right = thirdNode;
		
		rootNode.left.left = fourthNode;
		rootNode.left.right = fifthNode;
		
		rootNode.right.left = sixthNode;
		rootNode.right.right = seventhNode;
		
		//Call for preOrder processing
		System.out.println("Binary Tree PreOrder Processing output....");
		binaryTree.preOrder(rootNode);
		
		System.out.println();
		
		System.out.println("Binary Tree PreOrder Processing output after converting into it's Mirror Image....");
		Node<Integer> mirrorBinaryTree = binaryTree.mirrorBinaryTree(rootNode);
		binaryTree.preOrder(mirrorBinaryTree);
		
	}
}

package com.kkjavatutorials.client;

import com.kkjavatutorials.tree.BinaryTree;

import com.kkjavatutorials.tree.BinaryTree.Node;

/**

* Client Program to find a mirror image

* of a binary Search tree?

* @author KK JavaTutorials

public class ClientTest {

public static void main(String[] args) {

//Create an Instance of BinaryTree

BinaryTree<Integer> binaryTree = new BinaryTree<>();

//Root Node

Node<Integer> rootNode = 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

rootNode.left = secondNode;

rootNode.right = thirdNode;

rootNode.left.left = fourthNode;

rootNode.left.right = fifthNode;

rootNode.right.left = sixthNode;

rootNode.right.right = seventhNode;

//Call for preOrder processing

System.out.println("Binary Tree PreOrder Processing output....");

binaryTree.preOrder(rootNode);

System.out.println();

System.out.println("Binary Tree PreOrder Processing output after converting into it's Mirror Image....");

Node<Integer> mirrorBinaryTree = binaryTree.mirrorBinaryTree(rootNode);

binaryTree.preOrder(mirrorBinaryTree);

}

The output of This Program:

Binary Tree PreOrder Processing output….
1 2 4 5 3 6 7
Binary Tree PreOrder Processing output after converting into it’s Mirror Image….
1 3 7 6 2 5 4

Algorithm Implementation

Leave a Reply Cancel reply