# 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:**

- Given two trees, perform in-order traversal of tree 1 and reverse in-order traversal of tree 2
- Check if the values of both the traversals are same through the iteration
- If the values are uniform throughout the iteration, then the trees are mirror of each other
- 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