Balanced Binary Tree

Intuition

A naive solution recomputes the height of every subtree while separately checking balance, which repeats work and drifts toward O(n log n) or worse. Instead, we fold the balance test into the height computation: a single post-order function returns the height of a balanced subtree, or a sentinel value of -1 if imbalance was detected anywhere below. Because a child already reports -1 when it is unbalanced, the parent can bail out immediately without finishing its work. This propagation means the answer for the entire tree is decided in one linear sweep. If the root call returns anything other than -1, the tree is balanced.

Algorithm walkthrough

1. 1Define check(node) returning the subtree height, or -1 if the subtree is unbalanced.
2. 2A null node has height 0.
3. 3Recurse left; if it returns -1, immediately propagate -1 upward.
4. 4Recurse right; if it returns -1, propagate -1 as well.
5. 5If |leftHeight - rightHeight| > 1 return -1, otherwise return 1 + max(leftHeight, rightHeight).
6. 6The tree is balanced exactly when check(root) is not -1.

Implementation

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def check(node):
            if not node:
                return 0
            left = check(node.left)
            if left == -1:
                return -1
            right = check(node.right)
            if right == -1:
                return -1
            if abs(left - right) > 1:
                return -1
            return 1 + max(left, right)

        return check(root) != -1