Balanced Binary Tree

A Balanced Binary Tree is a Tree in which the left and right subtrees of every node differ in height by no more than 1.

The algorithm is recursive and check if left subtree is balanced and then if right subtree is balanced.

The function returns two informations:

a) a boolean that specify if left and right subtrees are balances

b) the depth of the current subtree in order to compare it to its neighbor depth

def isBalanced(root: Optional[TreeNode]) -> bool:
    def helper(root):
        # if root is None hence the depth is 0 and it is balanced
        if not root:
            return(True, 0)
        else:
            balanced_left, depth_left = helper(root.left) # first check left subtree
            
            # if left subtree is not balanced, no need to check right subtree
            if not balanced_left:
                return(False, depth_left + 1)
            
            balanced_right, depth_right = helper(root.right) # check right subtree
            
            # current tree is balanced if right (and left) subtree are balanced and their depth are not different by more than 1
            return(balanced_right and (abs(depth_left-depth_right)<=1), max(depth_left, depth_right) + 1)
        
    return(helper(root)[0])