by A tree is a data structure similar to Linked list in which each node points to multiple nodes instead of simply pointing to the next node. A tree is called Binary tree if each node in a tree has maximum of two nodes.
An empty tree is also a Binary tree. We can call the two children of each node as Left and Right child of a node. The node of the tree which has no parent is called the Root of the tree. Perhaps Binary tree is the most used tree data structure in the programming world. Before going ahead have a look into Binary Tree basics and Binary Tree implementation.
Let’s have a look on basic class definition for Binary Tree.
class BinaryTree
{
public:
int m_data;
BinaryTree* m_left;
BinaryTree* m_right;
BinaryTree (int data);
BinaryTree (int data, BinaryTree* left, BinaryTree* right);
~BinaryTree ();
};
void print_binary_tree (BinaryTree* root)
{
cout << " " << root -> m_data;
if (root -> m_left)
print_binary_tree (root -> m_left);
if (root -> m_right)
print_binary_tree (root -> m_right);
}
void print_tree (BinaryTree* root)
{
cout << "Binary tree contents: ";
print_binary_tree (root);
cout << endl;
}
Mirror image of a Binary Tree
A Mirror image of a Binary Tree is another Binary Tree in which left and right children of any non-leaf nodes are interchanged. In this article, we will discuss about creating mirror image of a Binary Tree.
Note that Mirror image of a Binary Tree’s Mirror image is the Binary Tree itself.
Let’s look into an example to understand it better.
For the Binary tree mentioned in above image, left tree is mirror image of right side binary tree and vice-versa.
Mirror image of a Binary Tree using iteration
In this method, we will create the mirror image of a Binary tree using iteration. Let’s look into an algorithm to create mirror image.
Algorithm
- If Binary Tree is empty return.
- Push root node into a Queue.
- While Queue is not empty
- dequeue the node from Queue.
- Swap the left and right child of the dequeued node.
- Enqueue the left and right child of dequeued node into the Queue if they are present.
Few of the functions used below are explained in Generic Queue implementation. Refer those before going ahead.
Let’s look into the sample code for creating mirror image of a binary tree using iteration.
void get_mirror_using_iteration (BinaryTree * root)
{
if (!root)
return;
BinaryTree* temp = NULL;
Queue q (10);
q.enqueue (root);
while (!q.isEmpty ())
{
temp = q.dequeue ();
BinaryTree* t = temp -> m_left;
temp -> m_left = temp -> m_right;
temp -> m_right = t;
if (temp -> m_left)
q.enqueue (temp -> m_left);
if (temp -> m_right)
q.enqueue (temp -> m_right);
}
}
Mirror image of a Binary Tree using Recursion
In this method, we will create the mirror image of a Binary tree using recursion. Let’s look into an algorithm to create mirror image.
Algorithm
- If Binary Tree is empty return
- Swap the left and right child of the root node.
- Call the recursive function with root left child.
- Call the recursive function with root right child.
- At the end Binary Tree will become mirror image of its own.
Let’s look into the sample code for creating mirror image of a binary tree using recursion.
void get_mirror (BinaryTree * root)
{
if (!root)
return;
BinaryTree* temp = root -> m_left;
root -> m_left = root -> m_right;
root -> m_right = temp;
get_mirror (root -> m_left);
get_mirror (root -> m_right);
}
Few of the functions used below are explained in Binary Tree Implementation. Refer those before going ahead.
Let’s define a main function to use above functions.
int main ()
{
BinaryTree* node1 = new BinaryTree (1);
BinaryTree* node2 = new BinaryTree (2);
BinaryTree* node3 = new BinaryTree (3);
BinaryTree* node4 = new BinaryTree (4);
BinaryTree* node5 = new BinaryTree (5);
BinaryTree* node6 = new BinaryTree (6);
BinaryTree* node7 = new BinaryTree (7);
BinaryTree* node8 = new BinaryTree (8);
BinaryTree* node9 = new BinaryTree (9);
BinaryTree* node10 = new BinaryTree (10);
/* Set node5 as root node */
BinaryTree* root = node5;
node5 -> m_left = node3;
node3 -> m_left = node2;
node3 -> m_right = node4;
node2 -> m_left = node1;
node5 -> m_right = node7;
node7 -> m_left = node6;
node7 -> m_right = node9;
node9 -> m_right = node10;
node9 -> m_left = node8;
print_tree (root);
/* Mirror image of a Binary Tree's mirror image
* is the original binary tree */
get_mirror (root);
print_tree (root);
get_mirror (root);
print_tree (root);
get_mirror_using_iteration (root);
print_tree (root);
get_mirror_using_iteration (root);
print_tree (root);
delete_all_nodes (root);
}
Let’s analyze the output of this main function.
Binary tree contents: 5 3 2 1 4 7 6 9 8 10
Binary tree contents: 5 7 9 10 8 6 3 4 2 1
Binary tree contents: 5 3 2 1 4 7 6 9 8 10
Binary tree contents: 5 7 9 10 8 6 3 4 2 1
Binary tree contents: 5 3 2 1 4 7 6 9 8 10
