Convert binary tree to mirror/symmetric tree in java (recursive /example)

• Given a binary tree, convert a tree into mirror binary tree using depth first search or recursive algorithm.
• Create symmetric (or mirror image) binary tree using post order traversal..

Examples – Convert binary tree to mirror or symmetric tree (recursive)

Example 1: Mirror binary tree having right child in java

• Given a binary tree having left child node only (refer Fig 2).
  • Node C is left child of Node A.
• Mirror binary tree, will have right child node only.
  • Node C become right child of Node A.

Example 2: Symmetric binary tree having left child (recursive)

• Given a binary tree having right child node only (refer Fig 3).
  • Node C is right child of Node A.
• Symmetric binary tree, will have left child node only.
  • Node C become left child of Node A.

Example 3: image binary tree having left & right child (recursive).

• Given a binary tree having left & right child node (refer Fig 4).
  • Node B is left child of Node A.
  • Node C is right child of Node A.
• Mirror binary tree, will have left & right nodes swapped.
  • Node B becomes right child of Node A.
  • Node C becomes left child of Node A.

Algorithm: convert binary tree into mirror binary tree in java

• Perform post order traversal of given binary tree (Root node A).
• Traverse left subtree i.e. Node B
  • Traverse left subtree i.e. Node D
    • Swap left (null) & right child (null) node.
    • Swap will have no impact & return from here.
  • Traverse right subtree i.e Node E
    • Swap child nodes & return
  • Swap left child (D) & right child (E)
• Traverse right subtree i.e. Node C
  • Traverse left subtree left i.e. Node F
    • Swap child nodes & return
  • Post order traversal for right child G
    • Swap child nodes & return
  • Swap left child (F) and right child (G)
• Swap left (B) and right child (C)
• We have successfully generated the mirror binary tree.

Time complexity of algorithm will be O(n).

Program – convert binary tree to mirror or image or symmetric tree in java

1.) MirrorTree Class:

• MirrorTree class is responsible for converting binary tree to symmetric binary tree.
• Traverse the binary trees using depth first search recursive algorithm.

  package org.learn.Question;

import java.util.LinkedList;
import java.util.Queue;

public class MirrorTree {
	public static void mirrorTree(Node root) {
		if(null == root) {
			return;
		}
		mirrorTree(root.left);
		mirrorTree(root.right);
		Node swapNode = root.left;
		root.left = root.right;
		root.right = swapNode;
		return;
	}
	
	public static void printTree(Node root) {
		if (root == null) {
			System.out.println("Tree is empty");
			return ;
		}
		Queue queue = new LinkedList();
		queue.offer(root);
		while (!queue.isEmpty()) {
			Node node = queue.poll();			
			System.out.printf(" %d",node.data);		
			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
		}
		System.out.println("");	
		return;
	}
}

2.) Node Class:

• Node class is representing the nodes of  a binary tree.

package org.learn.Question;

public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int num) {
		this.data = num;
		this.left = null;
		this.right = null;
	}

	public Node() {
		this.left = null;
		this.right = null;
	}
	
	public static Node createNode(int number) {
		return new Node(number);
	}
}

3.) App Class: 

• We are creating a binary tree in main method.
• We are calling method of MirrorTree  class to convert binary tree into mirror binary tree.
• We will print the binary trees using level order traversal.

package org.learn.Client;

import org.learn.Question.MirrorTree;
import org.learn.Question.Node;

public class App {
	public static void main(String[] args) {
		// root level 0
		Node A = Node.createNode(55);
		// Level 1
		Node B = Node.createNode(50);
		Node C = Node.createNode(40);
		// Level 2
		Node D = Node.createNode(25);
		Node E = Node.createNode(80);
		Node F = Node.createNode(45);
		Node G = Node.createNode(90);

		// connect Level 0 and 1
		A.left = B;
		A.right = C;
		// connect level 1 and level 2
		B.left = D;
		B.right = E;
		C.left = F;
		C.right = G;
		
		System.out.println("Binary Tree");
		MirrorTree.printTree(A);
		MirrorTree.mirrorTree(A);
		System.out.println("Mirror Binary Tree");
		MirrorTree.printTree(A);
	}
}

Output – mirror or Symmetric binary tree in java (Fig 5):

Binary Tree : 
55 50 40 25 80 45 90 
Mirror Binary Tree : 
55 40 50 90 45 80 25 

Download code – convert mirror image of binary tree (recursive)