Check if two trees are mirror in Python

In this tutorial, we will learn how to check if two trees are mirror or not in Python.

For checking the trees are mirror or not, the following conditions must be true:-
1. The root node key of both the trees must be the same.
2. The left subtree of the first tree and the right subtree of the second tree must be the same.
3. Similarly, the right subtree of the first tree and the left subtree of the second tree must be the same.

-> It can also be concluded that the in-order traversal of the first tree must be reversed of the in-order traversal of the second tree.

Program to check if two trees are mirror in Python

#Let's create a Node
class Node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

#This will return True if the given two trees testes are a mirror of each other.
def check_mirror(x,y):

    #First check if the nodes we testing are base nodes i.e. they are empty or not.
    if x is None and y is None:
        return True

    #It checks if only one of both is empty.
    if x is None or y is None:
        return False

#Now, if both the tree's node is non-empty then we
#go for a further process where we check equality of
#left node of one's parent node with the right node
#of other's parent node.
#For this, we call the function recursively to check
#further child nodes of the tree.

    return (x.data == y.data and
            check_mirror(x.left,y.right) and
            check_mirror(x.right,y.left))

#Making two trees & checking the code.
tree1 = Node(9)
tree2 = Node(9)

tree1.left = Node(8)
tree1.right = Node(7)
tree1.left.left = Node(6)
tree1.left.right = Node(5)

tree2.left = Node(7)
tree2.right = Node(8)
tree2.right.left = Node(5)
tree2.right.right = Node(6)

if check_mirror(tree1,tree2):
    print("Yes, trees are mirror.")
else:
    print("They are not mirrors.")

OUTPUT:-

Yes, trees are mirror.

Also read:

Leave a Reply

Your email address will not be published. Required fields are marked *