Balanced Binary Tree

easyTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(H)
TreesOriginal Statement (leetcode).md

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

Bottom-up sentinel avoids O(N^2) top-down `height()` recomputations and short-circuits on the first unbalanced subtree.

3. Minimal Idiomatic Code

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

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.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Maximum Depth of Binary Tree (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.