Solutions

# DFS recursive returning a [boolean, height], or returning a special number (eg 9999) in case the tree is not balanced.
# trees

# Recursive DFS - O(n) time, O(h) space
def is_balanced(root: TreeNode) -> bool:
    def dfs(root):
        if not root:
            return [True, 0]
        
        left, right = dfs(root.left), dfs(root.right)
        balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
        return [balanced, max(left[1], right[1]) + 1]
    return dfs(root)[0]


# Recursive DFS - returning special value if not balanced
def is_balanced(root) -> bool:
    return rec(root) != 99999
    
def rec(node):
    if node is None:
        return 0
    
    lh = rec(node.left)
    rh = rec(node.right)
    if lh == 99999 or rh == 99999 or abs(lh -rh) > 1:
        return 99999
    else:
        return max(lh, rh) +1


# Iterative DFS - O(n) time, O(n) space
def is_balanced(root: TreeNode) -> bool:
    pass # complicated


# Brute force - O(n^2) time, O(n) space
def is_balanced(self, root: Optional[TreeNode]) -> bool:
    if not root:
        return True

    left = self.height(root.left)
    right = self.height(root.right)
    if abs(left - right) > 1:
        return False
    return self.isBalanced(root.left) and self.isBalanced(root.right)

def height(self, root: Optional[TreeNode]) -> int:
    if not root:
        return 0

    return 1 + max(self.height(root.left), self.height(root.right))