Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # http://code2begin.blogspot.com
- # Program to check if 2 given trees are identical to each other
- # node class
- class node:
- def __init__(self, element):
- self.data = element
- self.left = None
- self.right = None
- # function to check if 2 given trees are identical to each other
- def isIdentical(root1, root2):
- # if both the nodes are null then return True
- if root1 is None and root2 is None:
- return True
- # if the node are not null then check
- # 1. do nodes have same data
- # 2. do the have identical left subtrees
- # 3. do the have identical right subtrees
- if root1 is not None and root2 is not None:
- return (
- root1.data == root2.data and
- isIdentical(root1.left, root2.left) and
- isIdentical(root1.right, root2.right)
- )
- return False
- head = node(1)
- head.left = node(2)
- head.right = node(3)
- head.left.left = node(4)
- head.left.right = node(5)
- head.right.right = node(6)
- head.left.left.right = node(7)
- head.right.right.left = node(8)
- head.left.left.right.left = node(9)
- head.left.left.right.left.left = node(10)
- head.right.right.left.right = node(11)
- head2 = node(5)
- head2.left = node(2)
- head2.right = node(12)
- head2.left.left = node(-4)
- head2.left.right = node(3)
- head2.right.left = node(9)
- head2.right.right = node(21)
- head2.right.right.left = node(19)
- head2.right.right.right = node(25)
- head3 = node(1)
- head3.left = node(2)
- head3.right = node(3)
- head3.left.left = node(4)
- head3.left.right = node(5)
- head3.right.right = node(6)
- head3.left.left.right = node(7)
- head3.right.right.left = node(8)
- head3.left.left.right.left = node(9)
- head3.left.left.right.left.left = node(10)
- head3.right.right.left.right = node(11)
- print("TREE #1 and TREE #2 are identical : " + str(isIdentical(head, head2)))
- print("TREE #1 and TREE #3 are identical : " + str(isIdentical(head, head3)))
Add Comment
Please, Sign In to add comment