# Balanced Binary Tree

- **Canonical ID**: `balanced-binary-tree`
- **Canonical URL**: https://dsacheatsheet.com/problems/balanced-binary-tree
- **Difficulty**: easy
- **Patterns**: Trees
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/balanced-binary-tree/

## 1. Core Invariant / The Trick

Encode imbalance with sentinel `-1` in a bottom-up height DFS: if either subtree returns `-1` or `abs(lh - rh) > 1`, immediately bubble `-1` upward without extra top-down scans.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(H)`
- **Proof**: Bottom-up sentinel avoids O(N^2) top-down `height()` recomputations and short-circuits on the first unbalanced subtree.

## 3. Minimal Idiomatic Code

### Python
```python
def isBalanced(root: Optional[TreeNode]) -> bool:
    def dfs(node: Optional[TreeNode]) -> int:
        if not node:
            return 0
        lh = dfs(node.left)
        if lh == -1:
            return -1
        rh = dfs(node.right)
        if rh == -1 or abs(lh - rh) > 1:
            return -1
        return 1 + max(lh, rh)
    return dfs(root) != -1
```

### TypeScript
```typescript
export function isBalanced(root: TreeNode | null): boolean {
  const dfs = (node: TreeNode | null): number => {
    if (!node) return 0;
    const lh = dfs(node.left);
    if (lh === -1) return -1;
    const rh = dfs(node.right);
    if (rh === -1 || Math.abs(lh - rh) > 1) return -1;
    return 1 + Math.max(lh, rh);
  };
  return dfs(root) !== -1;
}
```

### C++
```cpp
int checkH(TreeNode* n) {
    if (!n) return 0;
    int l = checkH(n->left); if (l == -1) return -1;
    int r = checkH(n->right); if (r == -1 || abs(l - r) > 1) return -1;
    return 1 + max(l, r);
}
bool isBalanced(TreeNode* root) { return checkH(root) != -1; }
```

### Java
```java
int check(TreeNode n) {
    if (n == null) return 0;
    int l = check(n.left); if (l == -1) return -1;
    int r = check(n.right); if (r == -1 || Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
}
boolean isBalanced(TreeNode root) { return check(root) != -1; }
```

### Go
```go
func isBalanced(root *TreeNode) bool {
    var dfs func(*TreeNode) int
    dfs = func(n *TreeNode) int {
        if n == nil { return 0 }
        l := dfs(n.Left); if l == -1 { return -1 }
        r := dfs(n.Right); if r == -1 || l-r > 1 || r-l > 1 { return -1 }
        return 1 + max(l, r)
    }
    return dfs(root) != -1
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Checking only root `abs(height(left) - height(right)) <= 1` ignores deeply unbalanced subtrees.

### Follow-ups
- AVL trees preserve this exact invariant using rotations during insertions/deletions.