Invert Binary Tree

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

1. Core Invariant / The Trick

At every node, swap `left` and `right` children, then recursively invert both subtrees (pre-order, post-order, or BFS queue all preserve the mirror invariant).

2. Complexity Bounds & Proof

Visits every tree node once; recursion stack depth equals tree height H (O(log N) balanced, O(N) skewed).

3. Minimal Idiomatic Code

def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return None
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

4. Failure Modes & Interview Follow-ups

Pitfalls:- Sequentially writing `root.left = invert(root.right); root.right = invert(root.left);` mutates `root.left` before the second line reads it unless assigned simultaneously or via temps.
Follow-ups:- Iterative BFS queue avoids recursion stack overflow on extremely skewed trees of depth 10^5.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

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

Related Invariants

Same Tree (O(min(P, Q)))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.