m2skills

identical python

Jun 4th, 2018
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.81 KB | None | 0 0
  1. # http://code2begin.blogspot.com
  2. # Program to check if 2 given trees are identical to each other
  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 identical to each other
  12. def isIdentical(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 the node are not null then check
  18.     # 1. do nodes have same data
  19.     # 2. do the have identical left subtrees
  20.     # 3. do the have identical right subtrees
  21.     if root1 is not None and root2 is not None:
  22.         return (
  23.             root1.data == root2.data and
  24.             isIdentical(root1.left, root2.left) and
  25.             isIdentical(root1.right, root2.right)
  26.         )
  27.     return False
  28.  
  29.  
  30. head = node(1)
  31. head.left = node(2)
  32. head.right = node(3)
  33. head.left.left = node(4)
  34. head.left.right = node(5)
  35. head.right.right = node(6)
  36. head.left.left.right = node(7)
  37. head.right.right.left = node(8)
  38. head.left.left.right.left = node(9)
  39. head.left.left.right.left.left = node(10)
  40. head.right.right.left.right = node(11)
  41.  
  42. head2 = node(5)
  43. head2.left = node(2)
  44. head2.right = node(12)
  45. head2.left.left = node(-4)
  46. head2.left.right = node(3)
  47. head2.right.left = node(9)
  48. head2.right.right = node(21)
  49. head2.right.right.left = node(19)
  50. head2.right.right.right = node(25)
  51.  
  52. head3 = node(1)
  53. head3.left = node(2)
  54. head3.right = node(3)
  55. head3.left.left = node(4)
  56. head3.left.right = node(5)
  57. head3.right.right = node(6)
  58. head3.left.left.right = node(7)
  59. head3.right.right.left = node(8)
  60. head3.left.left.right.left = node(9)
  61. head3.left.left.right.left.left = node(10)
  62. head3.right.right.left.right = node(11)
  63.  
  64. print("TREE #1 and TREE #2 are identical : " + str(isIdentical(head, head2)))
  65. print("TREE #1 and TREE #3 are identical : " + str(isIdentical(head, head3)))
Add Comment
Please, Sign In to add comment