Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # http://code2begin.blogspot.com
- # program to check if a given binary tree is balanced or not
- # node class
- class node:
- def __init__(self, element):
- self.data = element
- self.hd = -1
- self.left = None
- self.right = None
- # function to find the height of a binary tree
- def height(root):
- if root is None:
- return 0
- return 1 + max(height(root.left), height(root.right))
- # function to check if the tree is a height balanced tree or not
- def isBalanced(root):
- if root is None:
- return True
- # get the heights of the left and the right subtrees
- left_height = height(root.left)
- right_height = height(root.right)
- # if the difference between heights of the left and right subtrees is less than 2
- # and left and right subtrees are also balanced then return True
- return abs(left_height - right_height) <= 1 and isBalanced(root.left) and isBalanced(root.right)
- 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)
- print("Tree #1 is Balanced : " + str(isBalanced(head)))
- print("Tree #2 is Balanced : " + str(isBalanced(head2)))
Add Comment
Please, Sign In to add comment