Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # http://code2begin.blogspot.com
- # Program to check if 2 given binary trees are isomorphic or not
- # 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 isomorphic to each other
- def isomorphic_tree(root1, root2):
- # if both the nodes are null then return True
- if root1 is None and root2 is None:
- return True
- # if any one of them is null then return False
- if root1 is None or root2 is None:
- return False
- # if the data fields are not equal then return False
- if root1.data != root2.data:
- return False
- # else check if the left and the right subtrees are isomorphic recursively
- return (
- (isomorphic_tree(root1.left, root2.left) and isomorphic_tree(root1.right, root2.right)) or
- (isomorphic_tree(root1.left, root2.right) and isomorphic_tree(root1.right, root2.left))
- )
- 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)
- i1 = node(1)
- i1.left = node(2)
- i1.right = node(3)
- i1.left.left = node(4)
- i1.left.right = node(5)
- i1.right.left = node(6)
- i1.left.right.left = node(7)
- i1.left.right.right = node(8)
- i2 = node(1)
- i2.left = node(3)
- i2.right = node(2)
- i2.right.left = node(4)
- i2.right.right = node(5)
- i2.left.right = node(6)
- i2.right.right.right = node(7)
- i2.right.right.left = node(8)
- print("TREE #1 and TREE #2 are isomorphic : " + str(isomorphic_tree(head, head2)))
- print("TREE #3 and TREE #4 are isomorphic : " + str(isomorphic_tree(i1, i2)))
Add Comment
Please, Sign In to add comment