Did you that the problem of encoding and decoding data are solved by the tree structures in DSA? Trees are certainly one of the most important data structures that are used for solving major real time problems.
Which is why, for the freshers in programming, learning the basics of implementing the Binary Tree structures will certainly give you an advantage in your technical or coding interviews.
You will find a separate section of the tree data structure questions in your coding interviews which will mainly be based on traversing and navigating the tree structure.
Today, we are discussing a similar problem in regards to the Binary Trees. We will be navigating the periphery of the Binary Tree Traversal for the mirroring trees.
In order to solve problems based on Mirror Binary Tree, Learn how to approach the in-order traversal method in the blog.
What is a Binary Tree?
Did you know that there are many different terms used for describing a Binary Tree?
From Ordered Trees to Plane Trees, we have all sorts of names for this Data Structure in programming yet the function remains the same!
A Binary Tree Structure as the name suggests, is essentially a tree data structure that consists of nodes that are used for storing data elements.
Now, each of the nodes within a Binary Tree are allowed to have children nodes but only two at a maximum.
Hence conclusively, the nodes of a Binary Tree can have either one child node, two children nodes or no nodes at all!
Also, the node that further extends or branches out within a Binary Tree is known as the parent node.
Essentially, the structure of Binary Tree holds the following major components:
- Nodes: The node of a Binary Tree usually consists of the left reference, the right reference and the data element.
- Pointers: A pointer in a Binary Tree is used for pointing towards that succeeding node of the tree.
- Left Subtree: The subtree basically refers to the left part of the Binary Tree. An important quality of the Left Subtree is that the value of its nodes is always lesser than the right subtree.
- Right Subtree: As mentioned above, the right subtree essentially refers to the right part of the subtree which is always greater in value than the left subtree of the Binary Tree.
- Parent Node: All the nodes of the Binary Tree that branch further into two other nodes is known as the Parent Node
- Children Node: These are basically the branched out nodes that are also used for storing values of the elements from the Binary Tree.
Within a tree’s structure, you can mainly find the left child and the right child in different parts of the tree.
Those were all the practical information that are central to the Binary Tree Structure that are important to be understood by every programmer.
Now that we have our basics cleared, let’s continue with the problem statement that we are here to discuss in the blog.
How to tell if two Binary Trees are mirroring each other?
Before we look into the problem statement to justify mirror Binary Trees, let us consider the requirements that are to be fulfilled for the mirroring of two Binary Trees.
What are the conditions for the mirroring of two Binary Trees?
Essentially, the following conditions must prove to be correct:
- The key value of their root nodes must be identical.
- The root of the left subtree from the first Binary Tree (let us consider this as “a”) and the root of the right subtree from the second Binary Tree must resemble each other.
- Finally, the Right subtree from tree “a” should mirror the Left Subtree from tree “b”.
In order to test whether the above mentioned criterias are fulfilled by a given set of Binary Trees, let us have a look at the problem statement first!
Problem Statement:
You have been given two different Binary Trees. You are required to write a function that would return the value as true if the trees are found to be mirroring each other, or else you may return false.
Before we get into details for solving this problem statement, did you know that two Binary Trees are said to mirror each other when the values of both their subsequent left and right nodes remain interchanged.
That is why, we consider that using the iterative approach would be ideal for solving this problem statement.
Method 1: Using the Iterative In-Order Tree Traversal by implementing Stack
You may follow the steps for approaching the in-order traversal method:
- We will start by performing an iterative inorder traversal on the first Binary Tree and an iterative reverse in-order traversal on the parallel Binary Tree.
- While performing these traversals, make sure to find the values of the tree that essentially match with each other.
- Also check whether the root of the first tree has a NULL value and check for the same in the second tree.
- If these conditions are found to be fulfilled, you may conclude that both the trees are mirroring each other.
Time Complexity for this approach:O(n)
Method 2: Using the Recursive Algorithm for finding Mirror Binary Trees
We will check for the following conditions in the recursive algorithm:
- The root nodes of both the Binary Tree must be the same.
- The left subtree of the first BST and the right subtree of the parallel BST must be identical and vice versa.
- If both conditions are found to be fulfilled, you can return the statement as true, otherwise you may return false.
Final Thoughts
Did you know?
From the segment databases to spreadsheets, the uses of the Binary Trees are simply endless!
That said, the other Data Structures in DSA are no less important for the developers such as linked lists, strings and arrays.
If you are interested in learning about the important problem statements in these data structures, we would recommend you to check out these blogs- Merging two sorted arrays, second largest element in array and fattening a linked list.
