Python program to check if two trees are identical without using recursion
Description:
Two trees are identical if they have the same data and same arrangements of data.To identify, if two trees are identical we need to traverse both trees simultaneously, and while traversing we need to compare data and children of trees.
Example:
It will return false as their data are not same.
It will return True as their data and structures both are same.
Program:
from queue import Queue
classnewNode:def__init__(self, data):
self.data = data
self.left = self.right = None# Iterative method to find height of Bianry Tree defareIdentical(root1, root2):# Return true if both trees are empty if (not root1 andnot root2):
returnTrue# Return false if one is empty and # other is not if (not root1 ornot root2):
returnFalse# Create an empty queues for simultaneous traversals
q1 = Queue()
q2 = Queue()
# Enqueue Roots of trees in respective queues
q1.put(root1)
q2.put(root2)
while (not q1.empty() andnot q2.empty()):
# Get front nodes and compare them
n1 = q1.queue[0]
n2 = q2.queue[0]
if (n1.data != n2.data):
returnFalse# Remove front nodes from queues
q1.get()
q2.get()
# Enqueue left children of both nodes if (n1.left and n2.left):
q1.put(n1.left)
q2.put(n2.left)
elif (n1.left or n2.left):
returnFalseif (n1.right and n2.right):
q1.put(n1.right)
q2.put(n2.right)
elif (n1.right or n2.right):
returnFalsereturnTrue# Driver Code if __name__ == '__main__':
root1 = newNode(1)
root1.left = newNode(2)
root1.right = newNode(3)
root1.left.left = newNode(4)
root1.left.right = newNode(5)
root2 = newNode(1)
root2.left = newNode(2)
root2.right = newNode(3)
root2.left.left = newNode(4)
root2.left.right = newNode(5)
if areIdentical(root1, root2):
print("Yes")
else:
print("No")
Comments