Balanced Binary Tree

Problem: Balanced Binary Tree

To check a binary tree is balanced or not, we use recursion to implement depth-first search.

Code in Python:

class Solution(object):

    def heightCheck(self, root):
        heightL = heightR = 0
        if root.left:
            heightL = self.heightCheck(root.left)
        if root.right:
            heightR = self.heightCheck(root.right)
        if heightL != None and heightR != None and abs(heightL-heightR) <= 1:
            return 1 + max(heightL, heightR)
        else:
            return None

    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return bool(self.heightCheck(root))

Note: We need to return once we get an unbalanced node. Since the root can be balanced while its subtree not.