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.
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.
- 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
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))
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.