Binary Tree: Create a mirror - Recursive approach

Write a program to create a mirror of a given binary tree using recursive approach

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

How to create a mirror of a binary tree recursively?

To create a mirror of the binary tree we traverse the binary tree recursively and
swap left and right children of each node in the binary tree

Algorithm

1. Pass the root of the Binary Tree as input to the function
2. If the node is null then return null
3. Recursively call the function passing left of the node to it and store the value returned from the function in the leftNode
4. Recursively call the function passing right of the node to it and store the value returned from the function in the rightNode
5. Create a node called mirrorNode having data same as the node
6. Assign left of mirrorNode as rightNode
7. Assign right of mirrorNode as leftNode
8. Return the mirrorRoot

Diagram

Complexity

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

The Time Complexity of the Algorithm is O(N) as we have to visit every node in the binary tree
The Space Complexity is O(N + LogN) as we are creating a new mirror tree having the same number of nodes and
LogN part is because of the stack memory consumed by the recursive calls

Java Code

import java.util.ArrayDeque;
    import java.util.Queue;
    
    class CreateMirrorBTRecursive{
    
    // 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;
            }
        }
     
         // A Recursive Function which returns the mirrored version of the given tree
        public static Node createMirrorOfTreeRecursive(Node node) {
            // If node is null, then return null
            if (node == null) {
                return null;
            }
     
            // Call the function recursively for both left and right node of the tree
            Node leftNode = createMirrorOfTreeRecursive(node.left);
            Node rightNode = createMirrorOfTreeRecursive(node.right);
    
            // Create a mirrorNode variable having the same value as node
            Node mirrorNode = new Node(node.data);
    
            // Mirror the value of left and right in the mirrorNode
            // Make left as right and right as left
            mirrorNode.left = rightNode;
            mirrorNode.right = leftNode;
     
               // Return the mirrored node node
               return mirrorNode;
         }
     
        // 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 Recursive function
            Node mirrorTree1 = createMirrorOfTreeRecursive(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