Binary Tree: Create a mirror - Iterative approach


Write a program to create a mirror of a given binary tree.

Properties of Mirror of a Binary Tree
  • All nodes of the Binary Tree are present in its mirror
  • The left and right children of each node are swapped
 
Diagram

Mirror Binary Tree:

 
How to create a mirror of a binary tree?

To create a mirror of the Binary Tree we will be using the Breadth First Traversal[BFS] of the binary tree
in which we go level by level and create nodes of left and right children and swap them

 
Algorithm
  1. Get the root of the Binary Tree as input
  2. Check if root, if the root is null then its mirror will be null, so return null
  3. Create a variable mirrorRoot with the same values as the data of the root
  4. Create two Queues nodesQueue and newNodesQueue for BFS
  5. Push the root and mirrorRoot to the nodesQueue and newNodesQueue respectively
  6. While nodesQueue is not Empty do
    • Pop the nodesQueue and store it in current
    • Pop the newNodesQueue and store it in newCurrent
    • If the current of the left is valid then
      • Create a node to the right of newCurrent and set data as data of current left
      • Push left of current in nodesQueue
      • Push right of newCurrent in newNodesQueue
    • If the current of the right is valid then
      • Create a node to the left of newCurrent and set data as data of the current right
      • Push right of current in nodesQueue
      • Push left of newCurrent in newNodesQueue
  7. Return the mirrorRoot
 
Complexity

Time Complexity : O(n) , where n is the number of nodes in binary tree
Space Complexity : O(n)

The Time Complexity of the Algorithm is O(N) as we have to visit every node in the binary tree
and the Space Complexity is O(N) as we are creating a new mirror tree having the same number of Nodes

 
Java Code
import java.util.ArrayDeque;
import java.util.Queue;

class CreateMirrorBTIterative{

	// Node Class to represent the each node of BinaryTree
    static class Node {
        int data;
        Node left, right;

        // Constructor to set the value of the node
        Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    // Function to create mirror of a BinaryTree and return it
    static Node createMirrorOfTreeIterative(Node root) {
        // If the root is null simply return null, as no tree is present
        if (root == null) {
            return null;
        }

        // Create a node made mirrorRoot and assign it value of the root
        Node mirrorRoot = new Node(root.data);

        // We will be using Array deque to implement queue
        // Create two queue to store the current node and its mirrored version
        Queue nodesQueue = new ArrayDeque();
        Queue newNodesQueue = new ArrayDeque();

        // Enqueue the root and mirrored root in their respective queue
        nodesQueue.offer(root);
        newNodesQueue.offer(mirrorRoot);

        // Run the code till all the queue is empty, means all the nodes are checked
        while (!nodesQueue.isEmpty()) {
            
            // Remove the first node from the queue and store it in a variable
            Node current = nodesQueue.poll();
            Node newCurrent = newNodesQueue.poll();

            // If current left is present, then make the right of newCurrent as same value as current.left
            if (current.left != null) {
                
                newCurrent.right = new Node(current.left.data);

                // Store the node and its mirrored version simultaneously
                nodesQueue.offer(current.left);
                newNodesQueue.offer(newCurrent.right);
            }

            // If current right is present, then make the left node of newCurrent as same value as current.right
            if (current.right != null) {
                
                newCurrent.left = new Node(current.right.data);

                // Store the node and its mirrored version simultaneously
                nodesQueue.offer(current.right);
                newNodesQueue.offer(newCurrent.left);
            }
        }

        // Return the new mirrored Tree root
        return mirrorRoot;
    }
 
    // A function which prints the level order traversal representation of the Binary Tree
    static void printTree(Node root) {
        // Queue to store the current level of the binary tree
        Queue currentLevelQueue = new ArrayDeque();
        currentLevelQueue.offer(root); // Insert the root to the queue

        while (!currentLevelQueue.isEmpty()) {
            
            // Create a temporary queue to store the nodes of next level
            Queue tempQueue = new ArrayDeque();
            
            while (!currentLevelQueue.isEmpty()) {
                
                // Get the node from the queue and print it
                Node current = currentLevelQueue.poll();
                
                System.out.print(current.data);

                // If current node has left then insert it to the tempQueue
                if (current.left != null) {
                    tempQueue.offer(current.left);
                }

                // If current node has right then insert it to the tempQueue
                if (current.right != null) {
                    tempQueue.offer(current.right);
                }
            }
            
            // Printing a new line at each level end
            System.out.println();

            // copy the contents of the tempQueue to the currentLevelQueue
            currentLevelQueue = tempQueue;
        }
    }
 
    public static void main(String[] args) {
        // Creating a simple binary tree using the node class
        Node tree1 = new Node(1);
        tree1.left = new Node(2);
        tree1.right = new Node(3);
        tree1.left.left = new Node(4);
        tree1.left.right = new Node(5);
        tree1.right.left = new Node(6);
        tree1.right.right = new Node(7);

        // Creating a mirror of the tree using Iterative function
        Node mirrorTree1 = createMirrorOfTreeIterative(tree1);

        // Printing the original Binary Tree
        System.out.println("Original Tree: ");
        printTree(tree1);
        System.out.println();

        // Printing the mirrored Binary Tree
        System.out.println("Mirror Tree: ");
        printTree(mirrorTree1);
        System.out.println();
    }

}
 
Output

Original Tree:
1
23
4567

Mirror Tree:
1
32
7654



Thanks for feedback.



Read More....
Check if a binary tree is a min heap
Check if a binary tree is symmetric or mirror of itself
Check if a binary tree is symmetric or mirror of itself - iterative
Create a mirror of binary tree - Recursive approach
Find the height of binary tree - Iterative approach