Balanced Binary Tree
Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is one where the depth of the two subtrees of every node never differs by more than 1. **Core Insight:** A naive approach checks balance at every node by calling `height()` separately — this is O(n²). The optimal approach combines the height calculation with the balance check in a single post-order DFS. The helper returns the height of the subtree if it is balanced, or -1 as a sentinel if any subtree is unbalanced. **Algorithm:** Define `checkHeight(node)`: if node is null return 0. Recursively get `leftH = checkHeight(left)` and `rightH = checkHeight(right)`. If either is -1, or `|leftH - rightH| > 1`, return -1. Otherwise return `1 + max(leftH, rightH)`. The tree is balanced if `checkHeight(root) != -1`. **Why the sentinel works:** Once we detect an imbalance anywhere, -1 propagates up through all recursive calls without extra checks. **Complexity:** Time O(n) — each node visited once. Space O(h) — recursion stack.
Constraints
- •
The number of nodes is in the range [0, 5000]
def isBalanced(root) -> bool:
def height(node):
if not node: return 0
left = height(node.left)
if left == -1: return -1
right = height(node.right)
if right == -1: return -1
if abs(left - right) > 1: return -1
return 1 + max(left, right)
return height(root) != -1