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..

example binary mirror tree — Fig 1: Example of binary trees (one or two children)

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.

mirror binary tree left subtree — Fig 2: Binary tree with left child node

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.

symmetric binary tree right subtree — Fig 3: Binary tree with right child node

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.

mirror image binary tree — Fig 4: Symmetric tree having left & right node

Algorithm: convert binary tree into mirror binary tree in java

examples symmetric image — Fig 5: Binary Tree & Mirror (Symmetric) Tree

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

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

Example 1: Mirror binary tree having right child in java

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

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

Algorithm: convert binary tree into mirror binary tree in java

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

1.) MirrorTree Class:

2.) Node Class:

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

You may also like: