Find the mirror image of a binary tree

Unlike a Python dictionary, a list, or a set, elements of a binary tree are represented in a hierarchical manner. Having hierarchy in a binary tree allows one to find its mirror image as each element in a binary tree has a fixed position . In this article, we will study  the algorithm to find the mirror image of a binary tree. We will also implement the algorithm in Python and will execute it on an example binary tree.

What is the mirror image of a binary tree?

Mirror image of a binary tree is another binary tree which can be created by swapping left child and right child at each node of a tree. So, to find the mirror image of a binary tree, we just have to swap the left child and right child of each node in the binary tree. Let us try to find the mirror image of the following tree.

To find the mirror image of the above tree, we will start from the root and swap children of each node.

At root , we will swap the left and right children of the binary tree. In this way, 20,11, and 22 will come into the right subtree of the binary tree and 53,52, and 78 will come to the left of the binary tree as follows.

Then we will move to the next level and swap the children of 53. Here, 78 will become the left child of 53 while 52 will become the right child of 53. Similarly we will swap the left child and right child of 20. In this way, 22 will become the left child of 20 while 11 will become the right child of 20. The output binary tree after swapping nodes at this level will be as follows.

Now we will move to the next level. At this level, all the nodes are leaf nodes and have no children. Due to this there will be no swapping at this level and the above image is the final output.

Algorithm to find mirror image of a binary tree

As we have seen above, We can find the mirror image of a binary tree by swapping the left child and right child of each node. Let us try to formulate the algorithm in a systematic way. 

In the last example, At the second level, each node has only leaf nodes as their children. To find the mirror image at a node at this level, we have just swapped the left and right child at each node at this level. At the root node, we have swapped its both subtrees. As we are swapping each subtree (leaf nodes are also subtree), we can implement this algorithm using recursion.

The algorithm for finding a mirror image of a binary tree can be formulated as follows.

1. Start from the root node.
2. Recursively find the mirror image of the left subtree.
3. Recursively find the mirror image of the right subtree.
4. Swap the left and right subtree.

Implementation of Algorithm in Python

Now we will implement the algorithm to find the mirror image of a binary tree in Python.

from queue import Queue


class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None


def mirror(node):
    if node is None:
        return None
    mirror(node.leftChild)
    mirror(node.rightChild)
    temp = node.leftChild
    node.leftChild = node.rightChild
    node.rightChild = temp


def insert(root, newValue):
    # if binary search tree is empty, create a new node and declare it as root
    if root is None:
        root = BinaryTreeNode(newValue)
        return root
    # if newValue is less than value of data in root, add it to left subtree and proceed recursively
    if newValue < root.data:
        root.leftChild = insert(root.leftChild, newValue)
    else:
        # if newValue is greater than value of data in root, add it to right subtree and proceed recursively
        root.rightChild = insert(root.rightChild, newValue)
    return root


def inorder(root):
    if root:
        inorder(root.leftChild)
        print(root.data, end=" ")
        inorder(root.rightChild)


root = insert(None, 50)
insert(root, 20)
insert(root, 53)
insert(root, 11)
insert(root, 22)
insert(root, 52)
insert(root, 78)
print("Inorder Traversal of tree before mirroring:")
inorder(root)
mirror(root)
print("\nInorder Traversal of tree after mirroring:")
inorder(root)

Output:

Inorder Traversal of tree before mirroring:
11 20 22 50 52 53 78 
Inorder Traversal of tree after mirroring:
78 53 52 50 22 20 11 

Here, we have created a binary tree node. After that, we defined functions to insert elements to the binary tree. We have also used the in-order tree traversal algorithm to print the elements of the tree before and after finding the mirror image.

Conclusion

In this article, we have implemented an algorithm to find the mirror image of a binary tree. To learn more about other data structures, you can read this article on Linked List in Python. Stay tuned for more articles on implementation of different algorithms in Python.