Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Algorithm
2.1.
Code in C++
3.
Frequently Asked Questions
3.1.
What is an n-ary binary tree? 
3.2.
What is a Binary Search Tree? 
3.3.
Why would you use a recursive solution over the iterative one? 
4.
Conclusion
Last Updated: Mar 27, 2024

Mirror Tree from the given Binary Tree

Author ankit mittal
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Binary Trees are popular Data Structures and have a wide range of applications throughout various fields. Binary Trees are also important when it comes to interviews with top tech companies. A mastery of Binary Trees could help us solve a lot of problems. In this article, we are going to take a look at one such problem.

Before Diving into the question, let’s first understand what a binary tree is.

A binary tree is a hierarchical data structure in which each node has at most two children, generally the left child and right child. The topmost node in the tree is called the root. Each node contains three components:

  1. Pointer to left subtree
  2. Pointer to right subtree
  3. Data element

Let us now understand the following problem on binary trees. The problem statement is as follows - Given a binary tree, you need to construct a tree that is the same as the mirror image of the given tree

 

In the image below, we have a tree in which we have created the mirror image of the same. 

 

Now, if we look at the example, we are given a tree present on the left-hand side, and we have to construct a tree like the one present on the right-hand side from scratch. Now, let’s have a look at the algorithm to understand the solution to the problem.

Algorithm

One of the approaches can be to construct a new tree that will be the mirror image of the given tree. We can write a recursive algorithm that takes the root of the original tree and the mirror tree as arguments.
The steps for the recursive approach for constructing a mirror tree:

  1. Set the root of the mirror tree equal to the root of the original tree. 
  2. Recursively call the function for creating the left and right child of the mirror tree.
    1. Set the left child of the current node in the mirror tree as the right child of the current node in the original tree.
    2. Set the right child of the current node in the mirror tree as the left child of the current node in the original tree.
    3. If the current node in the original tree is NULL, simply return.
       

Observing the above steps carefully we can say that the above steps are equivalent to swapping the left and right child of the current node in the given original tree and recursively calling the function for left and right child.

We can rewrite the simple recursive algorithm with the following steps. 

  1. For every node, swap the address for the left and right nodes. 
  2. Call recursive functions for the left and right subtree. 
  3. Repeat step 1 
  4. We will stop the recursion when we reach the leaf node. I.e when both the left and right child are null. 

 

Let us look at the code below to understand how to create a Mirror tree from the given binary tree:

Must Read Recursive Binary Search.

Code in C++

#include <iostream>
using namespace std;


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


};


// this function simply prints the inorder traversal of the given tree
void inorder(Node* root)
{
if (root == NULL)
      return;
inorder(root->left);
cout <<" "<< root->data;
inorder(root->right);
}
// Note - here we have passed the address of the mirror tree. 
void MirrorTheTree(Node* root, Node** mirror)
{
            // this is the base case when Node is null
if (root == NULL) {
mirror = NULL;
return;
}


            // we have created a new Node here for the mirror tree
            *mirror = new Node(root->data); 
    
// we are now calling the left and the right subtrees
MirrorTheTree(root->left, &((*mirror)->right));
MirrorTheTree(root->right, &((*mirror)->left));
}



int main()
{


Node* tree = new Node(1);
tree->left = new Node(2);
tree->right = new Node(3);
tree->left->right = new Node(4);
            tree->left->right->left = new Node(6);
            tree->right->right = new Node(5);
    
// Print inorder traversal of the input tree
cout <<"Inorder of the given tree: ";
inorder(tree);
Node* mirrorTree = NULL;
MirrorTheTree(tree, &mirrorTree);


// Print inorder traversal of the mirror tree
cout <<"\nInorder of the given tree: ";
inorder(mirrorTree);


return 0;
}


Output :

Inorder of the given tree:  2 6 4 1 3 5

Inorder of the given tree:  5 3 1 4 6 2

 

Time Complexity - O(N) 

Since we are traversing every node once, the time complexity to create the mirror tree from the given binary tree is of the order N, where N is the number of nodes present in the tree. 

Space Complexity - O(1) 

As we are not using any type of extra space, the space complexity for creating the mirror tree from the given binary tree is of the order of O(1).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is an n-ary binary tree? 

Likewise, in a binary tree, any particular tree will have at most 2 children. Similarly, the n-ary tree will have at most n child nodes. 

What is a Binary Search Tree? 

A tree is a binary search tree if and only if for every single node, all of the nodes in the left subtree of the node is going to be less than any given root node and all of the nodes in the right subtree is going to be greater than that node. This must be followed for every node in the whole tree.

Why would you use a recursive solution over the iterative one? 

In competitive programming, you don’t need to implement the fastest possible solution. You only need the answer to be fast enough to pass. To make the code easy and faster to implement, we can use a recursive approach.  

Conclusion

In this article, we have learned how to construct a mirror tree from the given binary tree. We can always break the problem into more minor problems and think. Likewise, in this question, the only catch is that we must construct the tree by keeping the mirror concept in mind while giving the recursive calls. When we pass the current node’s left child in the recursive function, we pass the right child of the mirror tree we are constructing and vice versa.

 

You can also refer to the courses on our platform to master tree data structure.

 

Recommended Reading: 

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Find Distance Between two Nodes of a Binary Tree
Next article
Maximum Width of a Binary Tree
Live masterclass