m2skills

isomorphic bt python

Jun 4th, 2018
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.00 KB | None | 0 0
  1. # http://code2begin.blogspot.com
  2. # Program to check if 2 given binary trees are isomorphic or not
  3. # node class
  4. class node:
  5.     def __init__(self, element):
  6.         self.data = element
  7.         self.left = None
  8.         self.right = None
  9.  
  10.  
  11. # function to check if 2 given trees are isomorphic to each other
  12. def isomorphic_tree(root1, root2):
  13.     # if both the nodes are null then return True
  14.     if root1 is None and root2 is None:
  15.         return True
  16.  
  17.     # if any one of them is null then return False
  18.     if root1 is None or root2 is None:
  19.         return False
  20.  
  21.     # if the data fields are not equal then return False
  22.     if root1.data != root2.data:
  23.         return False
  24.  
  25.     # else check if the left and the right subtrees are isomorphic recursively
  26.     return (
  27.         (isomorphic_tree(root1.left, root2.left) and isomorphic_tree(root1.right, root2.right)) or
  28.         (isomorphic_tree(root1.left, root2.right) and isomorphic_tree(root1.right, root2.left))
  29.     )
  30.  
  31.  
  32. head = node(1)
  33. head.left = node(2)
  34. head.right = node(3)
  35. head.left.left = node(4)
  36. head.left.right = node(5)
  37. head.right.right = node(6)
  38. head.left.left.right = node(7)
  39. head.right.right.left = node(8)
  40. head.left.left.right.left = node(9)
  41. head.left.left.right.left.left = node(10)
  42. head.right.right.left.right = node(11)
  43.  
  44.  
  45. head2 = node(5)
  46. head2.left = node(2)
  47. head2.right = node(12)
  48. head2.left.left = node(-4)
  49. head2.left.right = node(3)
  50. head2.right.left = node(9)
  51. head2.right.right = node(21)
  52. head2.right.right.left = node(19)
  53. head2.right.right.right = node(25)
  54.  
  55. i1 = node(1)
  56. i1.left = node(2)
  57. i1.right = node(3)
  58. i1.left.left = node(4)
  59. i1.left.right = node(5)
  60. i1.right.left = node(6)
  61. i1.left.right.left = node(7)
  62. i1.left.right.right = node(8)
  63.  
  64. i2 = node(1)
  65. i2.left = node(3)
  66. i2.right = node(2)
  67. i2.right.left = node(4)
  68. i2.right.right = node(5)
  69. i2.left.right = node(6)
  70. i2.right.right.right = node(7)
  71. i2.right.right.left = node(8)
  72.  
  73. print("TREE #1 and TREE #2 are isomorphic : " + str(isomorphic_tree(head, head2)))
  74. print("TREE #3 and TREE #4 are isomorphic : " + str(isomorphic_tree(i1, i2)))
Add Comment
Please, Sign In to add comment