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
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
# Iterative method to find height of Bianry Tree
def areIdentical(root1, root2):
# Return true if both trees are empty
if (not root1 and not root2):
return True
# Return false if one is empty and
# other is not
if (not root1 or not root2):
return False
# 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() and not q2.empty()):
# Get front nodes and compare them
n1 = q1.queue[0]
n2 = q2.queue[0]
if (n1.data != n2.data):
return False
# 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):
return False
if (n1.right and n2.right):
q1.put(n1.right)
q2.put(n2.right)
elif (n1.right or n2.right):
return False
return True
# 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")
Output:
Yes
>>>
Comments