Getting an adequate knowledge of all the data structures and their related operations is very crucial for any programmer. Generally, the data structures in coding are classified as linear and non-linear data structures.
Where arrays, structure, or a queue are considered linear data structures, a binary tree is considered to be a non-linear data structure.
A binary tree stores data in the hierarchical format and is, therefore, mostly used in searching and sorting processes. Because binary trees are significantly used, one must be aware of all the operations related to a binary tree.
One such question which is generally asked related to binary trees is to create a mirror tree of the given binary tree.
But how do you create a mirror tree of a binary tree?
This post will answer this question in detail. Check out the detailed explanation of all the methods that you can use to convert a binary tree into its mirror tree.
What Is A Binary Tree?
A binary tree is a tree with each node having a maximum of two child nodes. In a binary tree, the uppermost node is known as the parent or root node of the tree whereas, the other nodes are called the child nodes.
In the tree, the node comprises the pointer and data of the child nodes on both sides. You can easily calculate the height of the tree by counting the edges present between the root and the deepest leaf of the tree. In case the tree does not have any child, the height of the tree will be zero.
Hopefully, now you are aware of what is a binary tree. Let’s now get back to how to convert the binary tree into its mirror tree.
The Problem Statement
A binary tree will be given to you. You need to create a program to create a mirror tree of the given binary tree. The mirror tree of a binary tree interchanges all the nodes with no leaf of the given binary tree.
The right side nodes and their children will be interchanged with nodes and their children on the left side.
Methods To Convert A Binary Tree Into Its Mirror Tree
There are two methods that you can use to convert a binary tree into its mirror tree. The methods include:
- Iterative Approach
- Recursive Approach
Here, we have discussed both methods in detail.
Method 1: Using Recursive Approach
The recursive method is the basic method that you can use to solve the problem. This method is used to resolve some common problems like the longest common prefix and finding a unique path in a grid.
In this method, we will have to first create an additional function to mirror the given binary tree. This method performs the complete process recursively.
Now when the tree will be mirrored, the binary tree is then visited in an inorder pattern. This means that the right one will be followed by the root of the tree and will be traversed in the end.
The algorithm follows the following steps:
- For each subtree beginning from the source node:
- Swap the right and left subtrees.
Here is the pseudocode for the recursive method.
- Call Mirror for the left subtree
- Call mirror for the right subtree
- Swap the right and left subtrees
- temporary= left subtree
- Left subtree= right subtree
- Right subtree= temporary
Complexity Analysis
Time Complexity: The time complexity of this algorithm is O(n). This is because the algorithm uses a recursive approach because of which the time complexity is calculated the same as the order of traversal.
Space Complexity: The space complexity of this algorithm is O(n). This complexity is considering the size of the stack function. The recursive algorithm will not occupy any additional space than the stack calls.
Method 2: Iterative Approach
The next approach that you can use to create a mirror tree for the binary tree is iterative. In this approach, a queue is used based on traversal order. At the time of the traversal, the nodes on both sides are interchanged.
This approach uses a queue to keep all the nodes. It then swaps those nodes every time. It then pushes all the exchanged places back. In this method as well, you need to employ the mirror function that we have used in the previous method. However, this time the difference is that we will use a queue to do this.
This method follows the following algorithm:
- You will first have to perform the order traversal. It then swaps the children on both sides.
- Initialize a queue.
- Now, you will have to insert the root node in the queue.
- In case the queue contains elements, you will have to deque the node from your queue.
- Now, simply swap the right and left side nodes.
- When done, push the child into the queue.
- Go back to the 4 steps.
The pseudocode of the method is written in the following way:
- Define the Queue Qu
- Add the root to the queue
- While Qu is not null, do
- present-node= Qu.front()
- Dequeue the present node
- Swap present-node.left and present-node.right
- Push the left and right nodes back into the queue
Complexity Analysis
Time Complexity: The time complexity of this approach is O(n). here, n represents the n number of nodes.
Space Complexity: The space complexity of this approach is O(n). here, n represents the n number of nodes.
Conclusion
A binary tree is one of the most crucial data structures in coding. This linear data structure is beneficial for sorting the given array or any other data structure.
Converting a binary tree into its mirror tree is one common function performed on binary trees. You can perform the conversion using two methods. One of them is the recursive method and the other is the iterative method.
Generally, the iterative method is preferred because it takes less space and time on the system. However, you must still be aware of both approaches.
0
