Why must a directory-size rollup over a file tree use postorder rather than preorder?

## The question behind the question Interviewers ask this because the tempting wrong answer is "any order works, since every traversal visits every node". That is true about *coverage* and false about *dependency*. Traversal order decides when a node's own computation happens relative to its children's, and an aggregate that reads child results has a hard ordering constraint that coverage alone does not satisfy. ## The dependency, stated precisely For a directory tree, define `total(d)` = the bytes stored directly at `d` plus `total(c)` summed over every entry `c` of `d`. The right-hand side mentions `total(c)`. Any evaluation strategy that computes `total(d)` before all of its `total(c)` values exist is computing with holes. Postorder is the traversal defined by "visit a node only after all of its children have been visited", so it is the traversal that satisfies the dependency by construction. In an n-ary shape, postorder means: loop over the whole children list, recursing into each, and only then combine — the generalization of "left, right, node" to "all children in order, then node". Notice what does *not* matter: the order among siblings. Addition is associative and commutative, so any order over the children list gives the same sum. What matters is only that the parent comes last. If the aggregate were order-sensitive — concatenating child names into a path string, say — sibling order would matter too, but the parent-after-children constraint is the same either way. ## The mirror image: quantities that want preorder Preorder is not "the wrong traversal"; it is the right traversal for the opposite data flow. Top-down quantities are defined in terms of the *parent's* value: - a node's depth = parent's depth + 1 - a node's full path = parent's path plus the node's own name - an inherited permission or an inherited style = the parent's, unless the node overrides it Each of those is computed on the way *in*, so preorder — node first, then descend — is the natural fit, and computing them in postorder would ask the child for a value the parent has not produced. A useful way to say this in an interview: **postorder for aggregation, preorder for propagation.** Many real tree passes need both, which is why you see one walk that carries a value down as a parameter and returns an aggregate up as a result. ## Cost, and what the ordering does not buy you Both orders visit `n` nodes and follow `n - 1` child links, so the walk is O(n) either way, with O(1) work per node when the combine step is a sum. Choosing postorder is not a performance decision — it is a correctness decision. The performance decision hiding nearby is a different one: if you need the total for *every* directory, one postorder pass gives you all `n` of them in linear time, whereas computing each directory's total independently by re-walking its subtree is O(n · h) in the worst case and quadratic on a deep chain. That is the actual efficiency trap in this problem, and the one worth volunteering. ## Doing it without recursion An iterative version must reproduce the dependency explicitly. Two standard shapes: - **Two passes.** Walk the tree once in any order, recording each node's parent and pushing nodes onto a list; then process that list in reverse, so every node is handled after all of its descendants. A level-order walk processed in reverse works for the same reason: a child never appears before its parent going down, so it never appears after it coming back up. - **Unresolved-child counters.** Give each node a counter set to its number of children. Start from the leaves (counter zero), add each finished node's total into its parent, decrement the parent's counter, and when a counter reaches zero that parent is itself ready. This is the same dependency order expressed as a readiness queue rather than a call order. Both are O(n). Neither escapes the dependency; they just make it visible. ## Incremental rollups A senior-flavoured extension the interviewer may reach for: one file changes size — what has to be recomputed? Only the totals of that file's ancestors, because no other node's aggregate mentions it. That is O(h) work rather than a fresh O(n) pass, and it is a direct consequence of the same dependency structure that forced postorder in the first place. It is also why cached subtree aggregates are worth keeping on the nodes: the invalidation set is exactly the ancestor chain. ## Failure modes to name Saying "traversal order doesn't matter, we visit everything"; computing the parent's sum before the loop over children rather than after; assuming each directory already stores its own total (it stores only its own bytes — the total is what you are deriving); and confusing aggregation with propagation, which produces code that tries to push totals downward.