Why does DFS postorder, not preorder, give the correct order for releasing nested resources?

## Two clocks, not one A depth-first search naturally stamps every vertex twice. Keep one counter that ticks on every event; when the traversal enters vertex `u` record `d[u]` (discovery), and when `u`'s neighbour loop finishes record `f[u]` (finish). Over `V` vertices the counter runs to `2V`, and each vertex owns the half-open interval `[d[u], f[u]]`. - **Preorder** = the vertices listed by increasing discovery time — recorded on the way in. - **Postorder** = the vertices listed by increasing finish time — recorded on the way out. Both orders contain exactly the same vertices. That is the trap: because the *sets* match, people assume one sequence is the reverse of the other. ## Postorder is not reversed preorder Take a root `r` with two children `a` and `b`, explored in that order. - Preorder: `r, a, b`. - Postorder: `a, b, r`. - Reversed postorder: `r, b, a`. `r, a, b` is not `r, b, a`. Reversing postorder does restore the property "ancestors before descendants", but it flips the order among sibling subtrees, so it is a different sequence from preorder as soon as any vertex has two children. Only on a path — one child everywhere — do the two coincide. ## The nesting property The structural result that makes postorder useful: for any two vertices `u` and `v` explored in the same depth-first search, their intervals `[d[u], f[u]]` and `[d[v], f[v]]` are either **completely disjoint** or **completely nested**. They can never partially overlap. `d[u] < d[v] < f[u] < f[v]` is impossible. The reason is mechanical. Suppose `v` is discovered while `u` is in progress. Then `v` was entered from inside `u`'s neighbour loop, directly or through a chain of entries, and every one of those entries must return before `u`'s loop can continue. So `f[v] < f[u]`, and the interval of `v` sits wholly inside the interval of `u`. Write each discovery as an opening parenthesis and each finish as a closing one, and the whole traversal reads as a balanced parenthesis string — which is why this is usually called the parenthesis structure. Two consequences fall straight out: - `v` is a descendant of `u` in the search exactly when `d[u] < d[v]` and `f[v] < f[u]`. Two integer comparisons answer a containment query in constant time once the traversal has run. - Ordering by increasing finish time puts every descendant strictly before its ancestor. ## Why release wants the second consequence Model a nested resource arrangement as a graph: an edge from a holder to a thing it holds. A buffer holds views into it; a session holds open handles; an outer scope holds inner ones. The rule for teardown is that you may release something only once nothing that lives inside it is still alive. That is exactly "all descendants first, then the vertex", which is exactly increasing finish time. So you run the search, record finishes, and release in that order — the innermost items come out first and the outermost last, without any extra sorting pass. Preorder gives you the mirror rule: a vertex before everything under it. That is the correct order for **acquisition** — you must open the session before you can open a handle inside it — which is why the same traversal, with the emit moved from the entry to the exit, serves both phases of a lifecycle. The practical failure mode when someone reaches for preorder here is silent: on a shallow structure, or one where each holder has a single child, preorder and reversed postorder look the same and the code appears to work. The teardown only misfires when a holder has several children, or when the nesting is deeper than the test fixture. ## Cost, and one caution Recording both timestamps changes nothing asymptotically: the traversal is O(V+E) and the two integer arrays are Θ(V). Emitting on the way out costs nothing extra either — postorder is one line moved. The caution: this reasoning is about the search's own nesting relation, the ancestor-descendant structure the traversal builds. Discovery and finish times describe *that* structure faithfully; when a vertex is reachable from several unrelated places, which of them becomes its ancestor depends on the traversal order, so "finished before" is a statement about the search tree, not an intrinsic property of the graph.