Trace recursion and dynamic structures

Make progress toward the base case

A recursive solution defines a stopping case and reduces every other case toward it. The call stack stores work waiting for a smaller call to return. Trace both the descent and the returns to explain a recursive result.

Binary search reduces a sorted candidate range, while merge sort divides data and combines sorted results. Compare the amount of work and extra storage required. An algorithm's typical behavior does not automatically describe its worst case.

Choose behavior before representation

A stack supports last-in-first-out access, a queue supports first-in-first-out access, and a binary search tree supports ordered navigation. Arrays and linked nodes are implementation choices. Explain empty and full conditions for any bounded implementation.

For a linked insertion, preserve the next reference before changing it. For a tree traversal, define when the node is visited relative to its children. Use a small hand-worked example to verify that every required value is visited exactly once.

Check yourself