Iterative method to check if two trees are mirror of each other in Python

In this article, we are going to look at the algorithm and a Python program to check if two trees are mirror of each other. Consider a binary tree T. Interchanging its left and right non-leaf nodes would give us the mirror to T, that is, M(T).

Let’s look at the algorithm first. Followed by the Python implementation of the algorithm.

ALGORITHM


Firstly, we need to define In-order Traversal and Reverse In-order Traversal of a binary tree:

  • In-order Traversal: Traverse the left sub-tree -> Visit the root node -> Traverse the right sub-tree
  • Reverse In-order Traversal: Traverse the right sub-tree -> Visit the root node -> Traverse the right sub-tree

So, it can be said that, as the name suggests, reverse in-order traversal is exactly the reverse of in-order traversal.

Algorithm:

  1. Given two trees, perform in-order traversal of tree 1 and reverse in-order traversal of tree 2
  2. Check if the values of both the traversals are same through the iteration
  3. If the values are uniform throughout the iteration, then the trees are mirror of each other
  4. Otherwise, the trees are not mirror of each other

PYTHON IMPLEMENTATION


Firstly, we define the class of initiating a tree.

class newNode: 
    def __init__(self, value):  
        self.value = value
        self.left = self.right = None

Now, we implement our algorithm in the function areMirrors(node1, node2).

def areMirrors(node1, node2): 
    st1 = [] 
    #nodes visited in tree 1
    st2 = [] 
    #nodes visited in tree 2
    while (1): 
      while(node1 and node2):
        #if the data of both the trees don't match
        #the trees are not mirror to each other
        if(node1.data != node2.data):
          return "No, the trees are not mirror of each other"
        st1.append(node1)
        st2.append(node2)
        node1 = node1.left
        node2 = node2.right
      #if any node becomes none
      if (not(node1 == None and node2 == None)):
        return "No, the trees are not mirror of each other"
      
      if (not len(st1) == 0 and not len(st2) == 0):
        node1 = st1[-1]
        node2 = st2[-1]
        st1.pop(-1)
        st2.pop(-1)
        #Moving on to right and left subtrees
        #of first and second trees respectively
        node1 = node1.right
        node2 = node2.left

      else:
        break
    
    return "Yes, the trees are mirror of each other"

Let’s create two trees, which will be our last step of Python implementation.

if __name__ == "__main__":
  tree1 = newNode(5)
  tree1.left = newNode(4)
  tree1.right = newNode(3)
  tree1.right.left = newNode(2)
  tree1.right.right = newNode(1)

  tree2 = newNode(5)
  tree2.left = newNode(3)      
  tree2.right = newNode(4)
  tree2.left.left = newNode(1)          
  tree2.left.right = newNode(2)

  print(areMirrors(tree1, tree2))

Output:

Yes, the trees are mirror of each other

The traversals of our trees are:

  • Tree 1: 4 -> 5 -> 2 -> 3 -> 1
  • Tree 2: 4 -> 5 -> 2 -> 3 -> 1

So, from the mental traversal as well as our implementation, we can say that both the trees are mirror of each other.

Further reading:

Leave a Reply

Your email address will not be published.