Divide & Conquer — choose the invariant

A range, a linked chain, and a square region have different boundaries.

What proves each recursive child is smaller and disjoint?

1 / 6

Convert Sorted Array to Binary Search Tree — predict before coding

The middle element balances the number of remaining keys on each side; sorted order simultaneously makes those two ranges valid left and right subtrees.

Decision: For sorted keys [2,5,8,11,14,17], consider midpoint roots 8 and 11. Can both work? A third construction chooses 5, with one key on the left and four balanced keys on the right. Why does sorted inorder alone fail to certify that third root?

Presenter notes

Model answer: Either midpoint yields child sizes 2 and 3, whose balanced constructions have height 2, so both are valid. Root 5 has a height-1 left child and a four-node balanced right subtree of height 3, violating the permitted difference of one. All three can preserve inorder; only a per-node height check establishes balance.

Correctness argument: For an empty range return nil. Otherwise choose its middle key, recursively build the range before it as the left subtree and after it as the right subtree. With strictly increasing input, every left key is smaller and every right key larger, so induction gives BST ordering at every node. The two range sizes differ by at most one, and recursively applying the same split bounds their resulting heights within one, yielding a height-balanced tree. Each index becomes exactly one node, so inorder recovers the entire original array with no omissions or duplicates. The input is read-only.

Debugging prompt: Test all subtree height differences, not only the root. Ensure recursive ranges exclude the chosen midpoint. Clarify that strict BST ordering needs distinct keys; sorted with duplicates alone is insufficient.

2 / 6

Sort List — predict before coding

Merge sort fits linked lists because merging advances pointers, whereas indexed partitioning would repeatedly scan. A recursive split must physically cut the list so each call owns a smaller disjoint chain.

Decision: Distinct nodes arrive as P(2)→Q(1)→R(2)→S(1). Give the stable sorted identity order. Would rewriting their values to 1,1,2,2 while retaining P→Q→R→S satisfy this exercise?

Presenter notes

Model answer: The stable order is Q→S→P→R. Equal-valued nodes retain their original relative order, and each original node keeps its own value. Rewriting values changes what a caller’s pointer to P or Q observes and violates the node-preserving contract even though the printed value sequence looks sorted. Sorting must rewire links.

Correctness argument: For zero or one node the list is already sorted. Otherwise slow/fast traversal finds a middle and cutting prev.Next splits the original nodes into two nonempty smaller lists. By induction recursive calls return sorted chains containing exactly their respective nodes. The merge repeatedly appends the smaller head; no later node in either sorted chain can be smaller, so the output prefix stays sorted. Appending the remaining suffix completes the union without allocating replacement data nodes. Choosing from the left on equality preserves original relative order of equal values. Disjoint sublists and complete rewiring prevent cycles and node loss.

Debugging prompt: Test exact node membership and cycle absence, not just sorted values. A value-only rewrite can conceal losing nodes. Include two-node and all-equal lists to expose bad split termination.

3 / 6

Merge k Sorted Lists — predict before coding

The provided reference is a heap-based k-way merge, not recursive pairwise merge. Both organize partial sorted streams, but their active state and auxiliary-space costs differ.

Decision: Four list lengths are [4,1,1,1]. Charge a merge of nonempty lengths a,b exactly a+b units and forwarding an unpaired run zero. Compare adjacent balanced rounds with left-to-right sequential merging. Why do these totals not determine actual pointer comparison counts?

Presenter notes

Model answer: Balanced rounds cost (4+1)+(1+1)=7, followed by 5+2=7, for 14 units. Sequential merging costs 5+6+7=18 units. The model charges all tail nodes; a pointer merge can attach a remaining tail without one comparison per node. Values and implementation determine actual comparisons, so these accounting totals are not timing measurements.

Correctness argument: The heap contains the current smallest unconsumed node of each nonempty input stream. The smallest among those heads is globally smallest because every other node in each stream is at least its head. Removing that head, appending it, and inserting its successor preserves this frontier invariant. Each input node enters and leaves the heap once, so all nodes appear exactly once in sorted order. Input lists must be disjoint acyclic chains; shared tails would cause the same node identity to be scheduled multiple times and invalidate this argument. Equal values may be merged in any cross-list order.

Debugging prompt: Capture/push a node’s successor before rewiring its output link. Verify every original pointer occurs once and the final tail is nil. Do not require a stable ordering across equal-valued nodes from different lists.

4 / 6

Construct Quad Tree — predict before coding

A recursive call owns one square region. It may compress that region into one leaf only after proving all its cells equal; otherwise the four child regions partition it exactly.

Decision: A quad tree represents [[0,1],[0,0]] correctly. A learner swaps its TopRight and BottomLeft child pointers while keeping the same leaf values and node count. What grid does it represent afterward, and which validation detects the defect?

Presenter notes

Model answer: It now represents [[0,0],[1,0]]. Quadrant positions are semantic, so the multiset of leaf values and total node count are insufficient. Expand leaves into their owned grid coordinates and compare every cell. Uniformity compression is a separate check: a correct image represented by unnecessary subdivisions can still violate the canonical leaf contract.

Correctness argument: A size-one binary square is necessarily uniform and becomes a leaf with its cell value. For a larger region, the uniformity scan is exact: a leaf is emitted only when no different cell exists. If a difference is found, four half-size quadrants are disjoint and cover the region. By induction each child exactly represents its quadrant, so their ordered combination represents the whole square. Recursion terminates because a positive power-of-two size halves until one. Leaf children are nil, and nonleaf quadrant positions are semantically distinct; swapping them changes the represented image.

Debugging prompt: Check reconstruction of every original cell and whether each uniform region is compressed. The nonleaf Val field is not the region’s majority; the reference keeps it true as an existing representation convention.

5 / 6

Reconstruct and transfer

Explain the split, combine invariant, identity contract, and recurrence for each problem.

Contrast the actual heap reference with pairwise merging.

6 / 6