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
- Get the root of the Binary Tree as input
- Check if root, if the root is null then its mirror will be null, so return null
- Create a variable mirrorRoot with the same values as the data of the root
- Create two Queues nodesQueue and newNodesQueue for BFS
- Push the root and mirrorRoot to the nodesQueue and newNodesQueue respectively
- 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
- 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.