""" p11 — Invert Binary Tree ========================= LeetCode 226 · Easy · Topics: Tree, DFS, BFS, Binary Tree Sections: 1. TreeNode (with __slots__) 2. invert_recursive — classic 4-liner, base case first 3. invert_iterative_bfs — collections.deque, level by level 4. invert_iterative_dfs — explicit list as stack 5. invert_pure — non-mutating variant; builds a new tree 6. helpers (build, serialize) + stress_test + edge_cases The four invert variants are cross-checked on 1000 random trees via canonical level-order serialization with None markers. """ import random import sys from collections import deque from copy import deepcopy from typing import List, Optional sys.setrecursionlimit(10_000) # ---------------------------------------------------------------------- # 1. TreeNode # ---------------------------------------------------------------------- class TreeNode: __slots__ = ("val", "left", "right") def __init__( self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None, ) -> None: self.val = val self.left = left self.right = right # ---------------------------------------------------------------------- # 2. RECURSIVE — the canonical 4-liner # ---------------------------------------------------------------------- def invert_recursive(node: Optional[TreeNode]) -> Optional[TreeNode]: # BASE CASE first — every tree recursion's line 1. if node is None: return None # CONTRACT: invert_recursive returns the inverted subtree root. # Tuple-swap is atomic: both RHS calls finish before assignment. node.left, node.right = invert_recursive(node.right), invert_recursive(node.left) return node # ---------------------------------------------------------------------- # 3. ITERATIVE BFS — level by level via deque # ---------------------------------------------------------------------- def invert_iterative_bfs(node: Optional[TreeNode]) -> Optional[TreeNode]: if node is None: return None q: deque = deque([node]) while q: cur = q.popleft() cur.left, cur.right = cur.right, cur.left if cur.left is not None: q.append(cur.left) if cur.right is not None: q.append(cur.right) return node # ---------------------------------------------------------------------- # 4. ITERATIVE DFS — explicit stack # ---------------------------------------------------------------------- def invert_iterative_dfs(node: Optional[TreeNode]) -> Optional[TreeNode]: if node is None: return None stack: List[TreeNode] = [node] while stack: cur = stack.pop() cur.left, cur.right = cur.right, cur.left if cur.left is not None: stack.append(cur.left) if cur.right is not None: stack.append(cur.right) return node # ---------------------------------------------------------------------- # 5. NON-MUTATING — return a new inverted tree, leave input untouched # ---------------------------------------------------------------------- def invert_pure(node: Optional[TreeNode]) -> Optional[TreeNode]: if node is None: return None # Swap subtrees AT CONSTRUCTION — left of new node is invert of OLD RIGHT. return TreeNode(node.val, invert_pure(node.right), invert_pure(node.left)) # ---------------------------------------------------------------------- # Helpers: build from level-order list with None markers; serialize back. # ---------------------------------------------------------------------- def build_tree(values: List[Optional[int]]) -> Optional[TreeNode]: if not values or values[0] is None: return None root = TreeNode(values[0]) q: deque = deque([root]) i = 1 n = len(values) while q and i < n: cur = q.popleft() if i < n and values[i] is not None: cur.left = TreeNode(values[i]) q.append(cur.left) i += 1 if i < n and values[i] is not None: cur.right = TreeNode(values[i]) q.append(cur.right) i += 1 return root def serialize(root: Optional[TreeNode]) -> List[Optional[int]]: """Level-order serialization with None markers; trailing Nones stripped.""" if root is None: return [] out: List[Optional[int]] = [] q: deque = deque([root]) while q: cur = q.popleft() if cur is None: out.append(None) continue out.append(cur.val) q.append(cur.left) q.append(cur.right) while out and out[-1] is None: out.pop() return out def random_tree(rng: random.Random, max_nodes: int = 20) -> Optional[TreeNode]: n = rng.randint(0, max_nodes) if n == 0: return None values: List[Optional[int]] = [rng.randint(-100, 100)] for _ in range(n - 1): # Each slot may be None to make the tree shape varied if rng.random() < 0.3: values.append(None) else: values.append(rng.randint(-100, 100)) return build_tree(values) # ---------------------------------------------------------------------- # STRESS TEST — all four implementations must produce same serialization # ---------------------------------------------------------------------- def stress_test(iterations: int = 1000) -> None: rng = random.Random(42) for it in range(iterations): t = random_tree(rng) # Deep-copy because mutating variants share input t1 = deepcopy(t) t2 = deepcopy(t) t3 = deepcopy(t) t4 = deepcopy(t) r1 = serialize(invert_recursive(t1)) r2 = serialize(invert_iterative_bfs(t2)) r3 = serialize(invert_iterative_dfs(t3)) r4 = serialize(invert_pure(t4)) assert r1 == r2 == r3 == r4, ( f"disagreement on input={serialize(t)}\n" f" recursive={r1}\n bfs={r2}\n dfs={r3}\n pure={r4}" ) # Invariant: invert(invert(x)) == x again = serialize(invert_recursive(invert_recursive(deepcopy(t)))) assert again == serialize(t), f"double-invert mismatch on {serialize(t)}" print(f"stress_test PASSED — {iterations} iterations (4 variants agree + involution)") # ---------------------------------------------------------------------- # EDGE CASES # ---------------------------------------------------------------------- def edge_cases() -> None: cases = [ ([], [], "empty"), ([1], [1], "single node"), ([1, 2], [1, None, 2], "left-only → right-only"), ([1, None, 2], [1, 2], "right-only → left-only"), ( [4, 2, 7, 1, 3, 6, 9], [4, 7, 2, 9, 6, 3, 1], "canonical LC example", ), ([1, 2, 3, 4, 5, 6, 7], [1, 3, 2, 7, 6, 5, 4], "perfect tree depth 3"), ] for vals, expected, label in cases: tree = build_tree(vals) got = serialize(invert_recursive(tree)) status = "PASS" if got == expected else "FAIL" print(f" [{status}] {label}: expected={expected} got={got}") if __name__ == "__main__": print("=== Edge cases ===") edge_cases() print("\n=== Stress test ===") stress_test()