Convert Binary Tree to its Mirror Tree

by · January 24, 2021

“Convert Binary Tree to its Mirror Tree” is a basic problem of tree data structure. Here, we are given a binary tree and our task is to write a program to convert given binary tree to its mirror tree.

Check if two trees are mirror tree of each other
Mirror Trees

This is a simple problem and can be solved using various traversal algorithm. Here, we are going to solve the given problem using postorder traversal and level order traversal. In both the traversal, we only need to swap the left and right child.

Method 1: Using Postorder Traversal

C++ Program to convert binary tree to its mirror tree is as follows:

/* C++ Program to Convert Binary Tree to its Mirror Tree */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to Convert Binary Tree to its Mirror Tree */
void convertMirror(Node *root)
{
    /* Base Condition: Empty Tree */
    if(root == NULL)
    return;
    
    convertMirror(root -> left);
    convertMirror(root -> right);
    
    swap(root -> left, root -> right);
}

/* Inorder Traversal */
void inorder(Node *root)
{
    if(root == NULL)
    return;
    
    inorder(root -> left);
    cout<<root -> data<<" ";
    inorder(root -> right);
}

int main()
{
    /* Creating a Binary trees and inserting some nodes in it */
    Node *root = NULL;
    
    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);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Printing Inorder Traversal before converting to Mirror Tree */
    cout<<"Inorder Traversal of Original Tree:\n";
    inorder(root);
    
    /* Calling function to Convert Binary Tree to its Mirror Tree */
    convertMirror(root);
    
    /* Printing Inorder Traversal after converting to Mirror Tree */
    cout<<"\nInorder Traversal of Mirror Tree:\n";
    inorder(root);
}

OUTPUT:

Inorder Traversal of Original Tree:
4 2 8 5 1 6 9 3 7 
Inorder Traversal of Mirror Tree:
7 3 9 6 1 5 8 2 4

Method 2: Using Level Order Traversal

C++ Program to convert binary tree to its mirror tree is as follows:

/* C++ Program to Convert Binary Tree to its Mirror Tree */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to Convert Binary Tree to its Mirror Tree */
void convertMirror(Node *root)
{
    /* Base Condition: Empty Tree */
    if(root == NULL)
    return;
    
    queue<Node *> qu;
    qu.push(root);
    
    while(!qu.empty())
    {
        Node *curr = qu.front();
        qu.pop();
        
        swap(curr -> left, curr -> right);
        
        if(curr -> left)
        qu.push(curr -> left);
        
        if(curr -> right)
        qu.push(curr -> right);
    }
}

/* Inorder Traversal */
void inorder(Node *root)
{
    if(root == NULL)
    return;
    
    inorder(root -> left);
    cout<<root -> data<<" ";
    inorder(root -> right);
}

int main()
{
    /* Creating a Binary trees and inserting some nodes in it */
    Node *root = NULL;
    
    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);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Printing Inorder Traversal before converting to Mirror Tree */
    cout<<"Inorder Traversal of Original Tree:\n";
    inorder(root);
    
    /* Calling function to Convert Binary Tree to its Mirror Tree */
    convertMirror(root);
    
    /* Printing Inorder Traversal after converting to Mirror Tree */
    cout<<"\nInorder Traversal of Mirror Tree:\n";
    inorder(root);
}

OUTPUT:

Inorder Traversal of Original Tree:
4 2 8 5 1 6 9 3 7 
Inorder Traversal of Mirror Tree:
7 3 9 6 1 5 8 2 4

Related Posts:

  1. Check if Binary Tree is Symmetric or Not
  2. Print All Root to Leaf Paths in a Binary Tree
  3. Introduction to Tree Data Structure
  4. Binary Tree Traversals
  5. Print All Leaf Nodes of a Binary Tree
  6. Count Number of Nodes in a Binary Tree
  7. Print Alternate Levels of Binary Tree
  8. Maximum Width of Binary Tree
  9. Level Order Tree Traversal
  10. Left View of Binary Tree
  11. Right View of Binary Tree
  12. Compute Height of Binary Tree
  13. Inorder Tree Traversal Using Stack
  14. Preorder Tree Trasversal Using Stack
  15. Postorder Tree Traversal Using Stack
  16. Vertical Order Tree Traversal
  17. Top View of Binary Tree
  18. Bottom View of Binary Tree
  19. Delete Complete Binary Tree
  20. Check if two trees are mirror Trees of Each Other

You may also like...