How do mirror trees work?


There are a few times in programming interviews when the problem statements are given only to test the knowledge of the candidates.


One such common interview problem is the mirror binary tree problem. 


So, now you might be wondering what mirror binary trees are, right!


Well, a mirror tree can be defined as the exact replica of a regular binary tree with the positions of the left and the right subtrees interchanged.


This is because the mirror binary tree is an exact reflection of the original binary tree as you would see through a mirror.


Now, there are basically no uses of a mirror binary tree except for the fact that they are an exact copy of the regular binary tree.


That is why, the problem statements related to mirror trees are often discussed in the interviews to test the coding skills of the candidates.


In order to solve this problem, we usually implement the recursive algorithm. If you are interested in learning how, then keep reading the blog to know more about this approach.




What is a Mirror Tree?



Have you ever observed the structure of a binary tree? 


If yes, then you would have certainly noticed how the tree branches out in two different directions i.e left and right which are commonly known as the left subtree and the right subtree.


The values in the left subtree are always lesser than the values contained in the right subtree of a Binary Tree.


Now, based on this information, we will be discussing the concept of Mirror Tree in a Binary Tree.


So, what exactly is a Mirror Tree? 


Well, as suggested by the name, a Mirror Tree is essentially the exact copy of the Binary Tree with a few nodes interchanged.


Let us understand this concept in depth with an example:


Assume that we have two Binary Trees that mirror each other. Let's name them 'm' and 'n'.


Now, the 'm' tree is the original Binary Tree while 'n' is the mirror image of 'm'.


This would directly imply that the nodes from the left subtree of 'm' are present in the right subtree of 'n'.


Hence, in the context of mirror trees, since the 'n' tree is mirroring 'm' it would be exactly the same as the original but reversed in structure.



We have discussed more about mirroring trees in the next section. Learn about the features of the mirror trees in detail.



What are the features of a Mirror Tree?



When we look at the structure of a regular Binary Tree, right from the start we can observe that it contains a node, a left subtree and a right subtree as well.


Now, a mirror tree of a Binary Tree would represent a similar structure. But, since this is a mirror replica, the values of the left and the right subtrees will be interchanged in the mirror image.


Check out three important conditions for a tree to be a mirror image of a Binary Tree:



  • The root node of both the trees must be the same 


  • The left subtree of the original tree and the right subtree of the mirror tree should be copies of each other


  • Similarly, the right subtree of the original tree and the left subtree of the mirror tree should replicate each other as well



This is essentially how the mirror trees work in a software program. If you are interested in learning more about the functioning of a mirror binary tree, then have a look at the next section of our blog.



How to form a Mirror Binary Tree?



For this part of the blog, we are going to be focusing on the functioning of mirror trees in a program.


The mirror binary Trees are basically formed using the same components of a regular Binary Tree with the only exception that it is reversed in order and structure.


These mirror binary trees are created to reflect the original binary tree hence, the algorithm to form them is extremely straightforward.



Here are the steps for creating a mirror binary tree:



  • You will have to begin with writing a structure node for the mirror tree that we will be creating later on in the program


  • Now, the next step is to form the Binary Tree using the dummy data from the original input of the binary tree


  • Next up, you will have to implement a recursive function in order to locate the mirror of the input binary tree in the program


  • This step requires you to call the function recursively for the right and the left nodes of the input binary tree


  • Finally, you can swap the data of the right node with the left node from the original Binary Tree to the duplicate one


Check out the implementation of this algorithm in a program:



  • Start by forming a struct node for the left and right parts of the mirror binary tree



  • The struct node will now be used to create new nodes within the mirror tree


Currently, both of the nodes will have no data until the tree has been completely mirrored


  • Next up, use the void function to convert the input tree to its mirror 


  • This will revoke the struct function and the program will get the message to swap the left node with the right node in the mirror binary tree from the original 


  • Once all the nodes from both the trees have been swapped, you can append the values of the swapped nodes into the new tree


  • Finally, we will append the value of the root node as it is for the mirror tree


  • Print the mirror tree as the result or the output 



Wrapping Up



Creating a mirror binary tree in a program is one of the most common coding problems discussed in the technical interviews.


This problem requires constant use of the recursive algorithm. This approach comprehensively test the skills of a candidate for solving other technical problems as well such as finding the minimum window substring.

Comments

Post a Comment

Popular posts from this blog

What are the 5 types of inheritance?

Image
  The concept of inheritance is considered among the most crucial concepts of object-oriented programming. Inheritance in Java is considered as a process where one class inherits the property of its parent class. When we simply define inheritance, we call it the capability of a class that derives the properties or features of other classes. The new class will be created as the ‘ derived class’ and the existing class will be known as base or parent class. Talking about the types of inheritance, it is generally of five types. Here, in this blog we are going to discuss all these inheritance types in detail with the help of examples. Without any ado, let’s get started! Types of inheritance In case of inheritance, one class derives the properties from its parent class. Here, any new class will be derived from its existing class. This new class is the derived class and our current class will be termed as the base class. When we talk about inheritance in Java, there are mainly five types ...
Read more

Remove duplicates from a sorted linked list

Image
Introduction Before reading this article, It is recommended to have an understanding of the linked list and its implementation and some basic operations on the linked list. Problem Description Create a function that takes a non-descending list and removes any duplicate nodes. Only one traversal of the list is necessary. Eg. Consider the given linked list: 1->1->1->2->2->3, the function is expected to convert the linked list into 1->2->3. In this article, we will extensively discuss the Label Control in C# & how to  remove duplicates from sorted doubly linked list .  Important:  We are supposed to delete only the duplicates i.e. only one copy of nodes should be there. Intuition:  The biggest hint given is that the list is sorted or non-decreasing in nature. From this, we can deduce that if duplicates are present, then it has to be the next one in the chain. The ideal way to approach this problem is to simply loop through the first value i...
Read more

How often can you Buy and Sell the same stock?

Image
The stock market is notoriously unpredictable. It can be hard enough to guess whether or not a particular investment will pay off or not. We know that understanding all the nuances of rules and regulations involved when buying and selling stocks is difficult. One big question many people have is, “How often can you buy and sell the same stock with transaction fee ?”  Before you start trading, you are unaware of the steps to follow to start trading and what would be the best time to buy and sell stock with transaction fee.  No matter if this is your first time investing or if you’ve been around the block a few times before, we hope that our guide will help you understand briefly on how to sell and buy stocks with in same time. Let's start with understanding stock trading and the types of traders in detail. What is Stock trading? The term "stock trading" describes the purchasing and selling of equities on a stock market. Investors that purchase and sell stocks with the inte...
Read more