# 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

- Pass the root of the Binary Tree as input to the function
- If the node is null then return null
- Recursively call the function passing left of the node to it and store the value returned from the function in the leftNode
- Recursively call the function passing right of the node to it and store the value returned from the function in the rightNode
- Create a node called mirrorNode having data same as the node
- Assign left of mirrorNode as rightNode
- Assign right of mirrorNode as leftNode
- 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

Thanks for feedback.