P-7.5 Timed Practice: Linked Structures and Trees

What this is and why it exists

This is the second question area, and the one where candidates most often know the theory and still cannot write it in ten minutes.

What a screening round asks for here is narrow and predictable. Walking a linked structure. Reversing one. Finding a middle. Walking a tree in each of the three orders. Finding a height or a depth.

A product interview adds balancing and less common traversals, and those live in the data structures module rather than here. Write these by hand before you write them in an editor, because by hand is the format a live round uses.

The vocabulary

• Reversing — turning the links of a chain to point the other way.
• Three references — what you must hold at once while reversing: previous, current, next.
• Lost tail — the classic reversal mistake, losing the rest of the chain.
• Fast and slow indexes — one moving twice as fast, to find a middle in one pass.
• Traversal order — where the node is handled relative to its children.

The mental model

Reversing links is the single most asked question in this area. It turns entirely on holding three references at once: the previous node, the current one, and the next. Draw the nodes and the arrows before writing anything. That drawing is what stops the classic mistake. Reassigning a link before saving what it pointed at loses the rest of the chain.

Finding the middle in one pass is the neat one. Move one index twice as fast as the other; when the fast one reaches the end, the slow one is at the middle. It is the clearest small example of the two-index shape from the previous topic. Be able to explain *why* it lands there, not only that it does.

The three tree walks differ in exactly one thing: where the node is handled relative to its children. Before, between, or after. That is the whole distinction, and stating it that way makes all three memorable at once. Knowing which one produces sorted output from a search tree is a common follow-up, so have the answer ready.

Computing a height and checking whether a tree is a search tree are both small recursions over the same shape. Both are asked as warm-up questions in live rounds. The second one has a trap worth knowing about: checking only that each node sits correctly between its immediate parent and children is not enough. The property is about ranges across the whole subtree, and candidates who check locally get a tree that passes and is not a search tree.

Then take a timed set and record which ones you could not finish. In a screening round, finishing matters more than elegance, so the unfinished list is what decides your next session.

What you should now be able to explain or do

Walk and reverse a linked structure on paper from memory, holding three references. Find a middle in one pass and explain why it works. Write the three tree walks and state the single thing that differs. Compute a height recursively. Check the search-tree property by ranges rather than locally, and say why local checking fails. Record which timed questions you could not finish.

Check yourself