Problem Statement in English

You’re given the root of a binary tree. You need to determine if it is height-balanced.

A binary tree is height-balanced if:

  • The left and right subtrees of every node differ in height by no more than 1

Return true if the tree is height-balanced, otherwise return false.

Approach

We can use a depth-first search (DFS) approach to check if the tree is balanced. We need to propagate the height of the tree up the recursive calls. If we find any subtree that is not balanced, we can return -1 to indicate that the tree is not balanced.

And we’re done!

Solution in Python


class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        def dfs(node):
            left = right = 0

            if node.left:
                left = dfs(node.left)
            if node.right:
                right = dfs(node.right)

            if left == -1 or right == -1 or abs(right - left) > 1:
                return -1

            return 1 + max(left, right)

        if dfs(root) == -1:
            return False
        return True

Complexity

  • Time: $O(n)$

  • Space: $O(n)$
    Since we are using recursion, the space complexity is O(n) in the worst case when the tree is skewed.

And we are done.