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)