Iterative method to check if two trees are mirror of each other in Python
By Vedant VachharajaniIn 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 = NoneNow, 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