• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar
PythonForBeginners.com

PythonForBeginners.com

Learn By Example

  • Home
  • Learn Python
    • Python Tutorial
  • Categories
    • Basics
    • Lists
    • Dictionary
    • Code Snippets
    • Comments
    • Modules
    • API
    • Beautiful Soup
    • Cheatsheet
    • Games
    • Loops
  • Python Courses
    • Python 3 For Beginners
You are here: Home / Data Structures / Find the mirror image of a binary tree

Find the mirror image of a binary tree

Author: Aditya Raj
Last Updated: September 21, 2021

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.

mirror image of a binary tree
a binary 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.

Related

Recommended Python Training

Course: Python 3 For Beginners

Over 15 hours of video content with guided instruction for beginners. Learn how to create real world applications and master the basics.

Enroll Now

Filed Under: Data Structures Author: Aditya Raj

More Python Topics

API Argv Basics Beautiful Soup Cheatsheet Code Code Snippets Command Line Comments Concatenation crawler Data Structures Data Types deque Development Dictionary Dictionary Data Structure In Python Error Handling Exceptions Filehandling Files Functions Games GUI Json Lists Loops Mechanzie Modules Modules In Python Mysql OS pip Pyspark Python Python On The Web Python Strings Queue Requests Scraping Scripts Split Strings System & OS urllib2

Primary Sidebar

Menu

  • Basics
  • Cheatsheet
  • Code Snippets
  • Development
  • Dictionary
  • Error Handling
  • Lists
  • Loops
  • Modules
  • Scripts
  • Strings
  • System & OS
  • Web

Get Our Free Guide To Learning Python

Most Popular Content

  • Reading and Writing Files in Python
  • Python Dictionary โ€“ How To Create Dictionaries In Python
  • How to use Split in Python
  • Python String Concatenation and Formatting
  • List Comprehension in Python
  • How to Use sys.argv in Python?
  • How to use comments in Python
  • Try and Except in Python

Recent Posts

  • Count Rows With Null Values in PySpark
  • PySpark OrderBy One or Multiple Columns
  • Select Rows with Null values in PySpark
  • PySpark Count Distinct Values in One or Multiple Columns
  • PySpark Filter Rows in a DataFrame by Condition

Copyright © 2012–2025 ยท PythonForBeginners.com

  • Home
  • Contact Us
  • Privacy Policy
  • Write For Us