m2skills

balanced BT python

Jun 3rd, 2018
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.56 KB | None | 0 0
  1. # http://code2begin.blogspot.com
  2. # program to check if a given binary tree is balanced or not
  3. # node class
  4. class node:
  5.     def __init__(self, element):
  6.         self.data = element
  7.         self.hd = -1
  8.         self.left = None
  9.         self.right = None
  10.  
  11. # function to find the height of a binary tree
  12. def height(root):
  13.     if root is None:
  14.         return 0
  15.  
  16.     return 1 + max(height(root.left), height(root.right))
  17.  
  18.  
  19. # function to check if the tree is a height balanced tree or not
  20. def isBalanced(root):
  21.     if root is None:
  22.         return True
  23.  
  24.     # get the heights of the left and the right subtrees
  25.     left_height = height(root.left)
  26.     right_height = height(root.right)
  27.     # if the difference between heights of the left and right subtrees is less than 2
  28.     # and left and right subtrees are also balanced then return True
  29.     return abs(left_height - right_height) <= 1 and isBalanced(root.left) and isBalanced(root.right)
  30.  
  31.  
  32.  
  33. head = node(1)
  34. head.left = node(2)
  35. head.right = node(3)
  36. head.left.left = node(4)
  37. head.left.right = node(5)
  38. head.right.right = node(6)
  39. head.left.left.right = node(7)
  40. head.right.right.left = node(8)
  41. head.left.left.right.left = node(9)
  42. head.left.left.right.left.left = node(10)
  43. head.right.right.left.right = node(11)
  44.  
  45.  
  46. head2 = node(5)
  47. head2.left = node(2)
  48. head2.right = node(12)
  49. head2.left.left = node(-4)
  50. head2.left.right = node(3)
  51. head2.right.left = node(9)
  52. head2.right.right = node(21)
  53. head2.right.right.left = node(19)
  54. head2.right.right.right = node(25)
  55.  
  56. print("Tree #1 is Balanced : " + str(isBalanced(head)))
  57. print("Tree #2 is Balanced : " + str(isBalanced(head2)))
Add Comment
Please, Sign In to add comment