Convert a Binary Tree into its Mirror Tree (Invert Binary Tree)
Last Updated :
04 Sep, 2023
Given a binary tree, the task is to convert the binary tree into its Mirror tree. Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged.
Mirror Tree
The idea is to traverse recursively and swap the right and left subtrees after traversing the subtrees.
Follow the steps below to solve the problem:
- Call Mirror for left-subtree i.e., Mirror(left-subtree)
- Call Mirror for right-subtree i.e., Mirror(right-subtree)
- Swap left and right subtrees.
- temp = left-subtree
- left-subtree = right-subtree
- right-subtree = temp
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data)
{
struct Node* node
= (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
void mirror(struct Node* node)
{
if (node == NULL)
return;
else {
struct Node* temp;
mirror(node->left);
mirror(node->right);
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
void inOrder(struct Node* node)
{
if (node == NULL)
return;
inOrder(node->left);
cout << node->data << " ";
inOrder(node->right);
}
int main()
{
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "Inorder traversal of the constructed"
<< " tree is" << endl;
inOrder(root);
mirror(root);
cout << "\nInorder traversal of the mirror tree"
<< " is \n";
inOrder(root);
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data)
{
struct Node* node
= (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
void mirror(struct Node* node)
{
if (node == NULL)
return;
else {
struct Node* temp;
mirror(node->left);
mirror(node->right);
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
void inOrder(struct Node* node)
{
if (node == NULL)
return;
inOrder(node->left);
printf("%d ", node->data);
inOrder(node->right);
}
int main()
{
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Inorder traversal of the constructed"
" tree is \n");
inOrder(root);
mirror(root);
printf("\nInorder traversal of the mirror tree"
" is \n");
inOrder(root);
return 0;
}
|
Java
class Node {
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
void mirror() { root = mirror(root); }
Node mirror(Node node)
{
if (node == null)
return node;
Node left = mirror(node.left);
Node right = mirror(node.right);
node.left = right;
node.right = left;
return node;
}
void inOrder() { inOrder(root); }
void inOrder(Node node)
{
if (node == null)
return;
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println(
"Inorder traversal of the constructed tree is");
tree.inOrder();
System.out.println("");
tree.mirror();
System.out.println(
"Inorder traversal of the mirror tree is");
tree.inOrder();
}
}
|
Python3
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
def mirror(node):
if (node == None):
return
else:
temp = node
mirror(node.left)
mirror(node.right)
temp = node.left
node.left = node.right
node.right = temp
def inOrder(node):
if (node == None):
return
inOrder(node.left)
print(node.data, end=" ")
inOrder(node.right)
if __name__ == "__main__":
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
print("Inorder traversal of the",
"constructed tree is")
inOrder(root)
mirror(root)
print("\nInorder traversal of",
"the mirror tree is ")
inOrder(root)
|
C#
using System;
public class Node {
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
class GFG {
public Node root;
public virtual void mirror() { root = mirror(root); }
public virtual Node mirror(Node node)
{
if (node == null) {
return node;
}
Node left = mirror(node.left);
Node right = mirror(node.right);
node.left = right;
node.right = left;
return node;
}
public virtual void inOrder() { inOrder(root); }
public virtual void inOrder(Node node)
{
if (node == null) {
return;
}
inOrder(node.left);
Console.Write(node.data + " ");
inOrder(node.right);
}
public static void Main(string[] args)
{
GFG tree = new GFG();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
Console.WriteLine("Inorder traversal "
+ "of the constructed tree is");
tree.inOrder();
Console.WriteLine("");
tree.mirror();
Console.WriteLine("Inorder traversal "
+ "of the mirror tree is");
tree.inOrder();
}
}
|
Javascript
<script>
class Node
{
constructor(item)
{
this.data=item;
this.left=this.right=null;
}
}
let root;
function mirror(node)
{
if (node == null)
return node;
let left = mirror(node.left);
let right = mirror(node.right);
node.left = right;
node.right = left;
return node;
}
function inOrder(node)
{
if (node == null)
return;
inOrder(node.left);
document.write(node.data + " ");
inOrder(node.right);
}
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
document.write("Inorder traversal of input tree is :<br>");
inOrder(root);
document.write("<br>");
mirror(root);
document.write(
"Inorder traversal of binary tree is : <br>"
);
inOrder(root);
</script>
|
Output
Inorder traversal of the constructed tree is
4 2 5 1 3
Inorder traversal of the mirror tree is
3 1 5 2 4
Time Complexity: O(N), Visiting all the nodes of the tree of size N
Auxiliary Space: O(N), For function call stack space
Convert a Binary Tree into its Mirror Tree using Level Order Traversal:
The idea is to do queue-based level order traversal. While doing traversal, swap left and right children of every node.
Follow the steps below to solve the problem:
- Perform the level order traversal
- While traversing over the tree swap the left and right child of current node
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
void mirror(Node* root)
{
if (root == NULL)
return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* curr = q.front();
q.pop();
swap(curr->left, curr->right);
if (curr->left)
q.push(curr->left);
if (curr->right)
q.push(curr->right);
}
}
void inOrder(struct Node* node)
{
if (node == NULL)
return;
inOrder(node->left);
cout << node->data << " ";
inOrder(node->right);
}
int main()
{
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "Inorder traversal of the"
" constructed tree is \n";
inOrder(root);
mirror(root);
cout << "\nInorder traversal of the "
"mirror tree is \n";
inOrder(root);
return 0;
}
|
Java
import java.util.*;
class GFG {
static class Node {
int data;
Node left;
Node right;
};
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
static void mirror(Node root)
{
if (root == null)
return;
Queue<Node> q = new LinkedList<>();
q.add(root);
while (q.size() > 0) {
Node curr = q.peek();
q.remove();
Node temp = curr.left;
curr.left = curr.right;
curr.right = temp;
if (curr.left != null)
q.add(curr.left);
if (curr.right != null)
q.add(curr.right);
}
}
static void inOrder(Node node)
{
if (node == null)
return;
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
public static void main(String args[])
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
System.out.print("Inorder traversal of the"
+ " constructed tree is \n");
inOrder(root);
mirror(root);
System.out.print("\nInorder traversal of the "
+ "mirror tree is \n");
inOrder(root);
}
}
|
Python3
class newNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def mirror(root):
if (root == None):
return
q = []
q.append(root)
while (len(q)):
curr = q[0]
q.pop(0)
curr.left, curr.right = curr.right, curr.left
if (curr.left):
q.append(curr.left)
if (curr.right):
q.append(curr.right)
def inOrder(node):
if (node == None):
return
inOrder(node.left)
print(node.data, end=" ")
inOrder(node.right)
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
print("Inorder traversal of the constructed tree is")
inOrder(root)
mirror(root)
print("\nInorder traversal of the mirror tree is")
inOrder(root)
|
C#
using System.Collections.Generic;
using System;
class GFG {
public class Node {
public int data;
public Node left;
public Node right;
};
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
static void mirror(Node root)
{
if (root == null)
return;
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
while (q.Count > 0) {
Node curr = q.Peek();
q.Dequeue();
Node temp = curr.left;
curr.left = curr.right;
curr.right = temp;
;
if (curr.left != null)
q.Enqueue(curr.left);
if (curr.right != null)
q.Enqueue(curr.right);
}
}
static void inOrder(Node node)
{
if (node == null)
return;
inOrder(node.left);
Console.Write(node.data + " ");
inOrder(node.right);
}
public static void Main(String[] args)
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
Console.Write("Inorder traversal of the"
+ " constructed tree is \n");
inOrder(root);
mirror(root);
Console.Write("\nInorder traversal of the "
+ "mirror tree is \n");
inOrder(root);
}
}
|
Javascript
<script>
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
function newNode(data)
{
let node = new Node(data);
return(node);
}
function mirror(root)
{
if (root == null)
return;
let q = [];
q.push(root);
while (q.length > 0)
{
let curr = q[0];
q.shift();
let temp = curr.left;
curr.left = curr.right;
curr.right = temp;;
if (curr.left != null)
q.push(curr.left);
if (curr.right != null)
q.push(curr.right);
}
}
function inOrder(node)
{
if (node == null)
return;
inOrder(node.left);
document.write( node.data + " ");
inOrder(node.right);
}
let root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
document.write(" Inorder traversal of the"
+" constructed tree is " + "</br>");
inOrder(root);
mirror(root);
document.write("</br>" + " Inorder traversal of the "+
"mirror tree is " + "</br>");
inOrder(root);
</script>
|
Output
Inorder traversal of the constructed tree is
4 2 5 1 3
Inorder traversal of the mirror tree is
3 1 5 2 4
Time Complexity: O(N), Traversing over the tree of size N
Auxiliary Space: O(N), Using queue to store the nodes of the tree
Please Login to comment...