#110EasyTrees & BST

Balanced Binary Tree

The tell: A property that fails fast — once unbalanced, the answer is fixed.

How you get there

1Compute depth and balance in one pass by returning a sentinel for 'unbalanced'.
2Any subtree returning the sentinel propagates it straight up.
3This avoids the O(n²) of calling a separate depth function at every node.

Solution

Python

def is_balanced(root) -> bool:
    def depth(node) -> int:
        if not node:
            return 0
        left = depth(node.left)
        if left == -1:
            return -1
        right = depth(node.right)
        if right == -1 or abs(left - right) > 1:
            return -1                        # sentinel: unbalanced
        return 1 + max(left, right)

    return depth(root) != -1

Time: O(n)
Space: O(h)

What goes wrong

Calling a separate max_depth at every node is correct but quadratic on a skewed tree.

Test yourself on DSA Next: Binary Tree Maximum Path Sum →