2018-01-19 09:32:00 UTC
Given a binary tree, determine if it is height-balanced.
Height-balanced binary tree : is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Return 0 / 1 ( 0 for false, 1 for true ) for this problem
Return : True or 1
Input 2 :
Return : False or 0
Because for the root node, left subtree has depth 2 and right subtree has depth 0.
Difference = 2 > 1.
This problem builds on the problem of finding the maximum depth of the tree.
So, we can break down the problem into two parts:
1. Find the depth of left and right subtree
2. If the depth differs by less than 2 and left subtree is balanced and right subtree is balanced -> return true (1)
3. Return False (0)
def isBalanced(a) return 1 if !a if ((height_of_balanced_tree(a.left) - height_of_balanced_tree(a.right)).abs < 2) and isBalanced(a.left) == 1 and isBalanced(a.right) == 1 return 1 else return 0 end end def height_of_balanced_tree(a) return 0 if !a return [height_of_balanced_tree(a.left), height_of_balanced_tree(a.right)].max + 1 end
Owned & Maintained by Saurav Prakash
If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)