Week 4 — BST & Tree Traversal Discipline

Theme: Binary Search Trees aren’t just “sorted trees” — they’re the smallest data structure where the invariant (left < node < right) drives both correctness and complexity. This week drills the invariant-first mindset alongside the four canonical traversal templates (preorder, inorder, postorder, level-order). Time budget: ~7 hours focused work; ~12 hours including the LC bank. Hard rule: every BST problem solved twice — once exploiting the BST property, once without (pretending it’s a general binary tree). State out loud which version you’d ship in interview vs production.

Why this week

Week 3 trained “recursion as the default tool.” This week applies that to a richer setting:

1. BST property = correctness lever. Validating a BST looks trivial (“check left < node < right at each node”) but every interviewer’s favorite gotcha is exactly that wrong solution. The right solution requires either passing bounds down or inorder traversal monotonicity — both are reusable patterns.
2. Inorder traversal = sorted iteration over BST. This single fact converts a class of “find the k-th smallest / closest / range query” problems into linear scans. Knowing when this applies separates Senior from Mid.
3. Construction problems (sorted-array → balanced BST) train the divide-and-conquer template that recurs in segment trees, merge sort, and parallel algorithms.
4. Level-order BFS is the bridge to Week 5 (graphs). Same data structure (deque), same for _ in range(len(q)) level-snapshot trick.

By Friday you should: distinguish BST-specific O(H) shortcuts from general-tree O(N) walks, write inorder iteratively without looking it up, and articulate why a balanced BST is O(log N) but an arbitrary BST can degrade to O(N).

Flagship problems (the 5 you OWN this week)

LC bank (~25 problems for spaced repetition)

BST validation / construction:

• LC 98 (p16), LC 108 (p19), LC 109 Sorted List to BST, LC 1008 Construct BST from Preorder, LC 449 Serialize BST

BST search / mutation:

• LC 700 Search in BST, LC 701 Insert into BST, LC 450 Delete Node in BST, LC 235 (p17), LC 270 Closest BST Value, LC 272 Closest BST Value II

BST inorder:

• LC 230 (p18), LC 94 Inorder Iterative, LC 173 BST Iterator, LC 285 Inorder Successor, LC 426 Convert BST to DLL, LC 538 Greater Tree

Level-order BFS:

• LC 102 (p20), LC 103 Zigzag, LC 107 Bottom-Up, LC 199 Right Side View, LC 515 Largest in Each Row, LC 314 Vertical Order, LC 637 Average of Levels

Readiness gate (binary; must all be YES before Week 5)

• I can articulate the BST invariant in one sentence: “for every node, EVERY value in the left subtree is < node.val AND EVERY value in the right subtree is > node.val.” (Not just immediate children — the entire subtree.)
• I can show the “wrong” Validate BST that only checks immediate children and explain the failing test case [5,1,4,null,null,3,6].
• I solved p16 BOTH via bounds-passing AND via inorder-monotonicity, and can argue which generalizes better (bounds → general predicate; inorder → “any monotone property”).
• I can write an iterative inorder traversal from memory using an explicit stack.
• I can explain why LC 235 (LCA of BST) is O(H) but LC 236 (LCA of binary tree) is O(N) — and write both.
• I know len(q) snapshot trick for level-order BFS and why omitting it merges levels.
• I can describe the average-case vs worst-case complexity of operations on an unbalanced BST (O(log N) avg, O(N) worst) and name two self-balancing variants (AVL, Red-Black).
• My stress_test() for each problem cross-checks 2+ variants on 1000 random BSTs (built with random.Random(42)).

If ANY unchecked: do not start Week 5. Re-drill the missing pieces.

Recurring traps

1. “Just check node.left.val < node.val < node.right.val.” This is the #1 wrong answer. It accepts [5,1,4,null,null,3,6] which is NOT a BST. The correct check is bounds-based or inorder-based.
2. Using <= instead of <. LC’s BST is strict — duplicates are not allowed. Inorder must produce strictly increasing values.
3. Inorder recursion stack overflow. A skewed BST of depth 10^4 blows Python’s default 1000 limit. Iterative inorder uses heap memory, not stack.
4. Early termination forgotten in p18. Walking the entire inorder is O(N); proper solution stops after the k-th pop and is O(H + k).
5. for _ in range(len(q)) omitted in BFS. Without it you get flat order, not level order. The len(q) must be captured BEFORE the inner loop starts because the queue grows during the loop.
6. Confusing height vs depth in BST complexity. Average BST height for random insertions is O(log N), but adversarial sorted insertions degrade to O(N) — this is the entire motivation for AVL/RB trees.

Stretch (only if you finish all 5 + LC bank with time left)

• LC 99 Recover Binary Search Tree — find the two swapped nodes via inorder. Classic Medium that’s almost a Hard if you don’t see the inorder pattern.
• LC 124 Binary Tree Maximum Path Sum (Hard) — promised from Week 3; the two-channel pattern with negative-pruning.
• LC 297 Serialize and Deserialize Binary Tree (Hard) — preorder + null markers; Meta loves this.
• LC 314 Binary Tree Vertical Order Traversal — level-order + column tracking; common at Meta/LinkedIn.

Begin with p16 — Validate BST.