Why does releasing a binary decision tree node by node require postorder, when every traversal is O(n)?

## The trap in the question Every traversal of an n-node tree is O(n). That is true, and it is the reason the mistake is so common: a candidate hears "which traversal" as a performance question, answers "they're the same cost," and misses that the orders are not *interchangeable*. Cost tells you what the walk will price; the **direction of the data dependency** tells you which walk is correct. Only one of them usually is. ## Why teardown is child-first Consider a fraud-triage decision tree: internal nodes hold rule records (a feature, a threshold, some counters) and each has up to two children. You want to release every node's storage explicitly. A node is the *only* reference to its two subtrees. Release it first and the addresses of its children are gone with it — the subtrees are still allocated, still occupying memory, and now unreachable. So the correct order is: release the left subtree, release the right subtree, then release the node. That is postorder, precisely. The same shape appears any time "finish the children before the parent can be finished" holds: - computing how many rules a subtree contains, or the worst-case evaluation depth of a branch — the parent's number is a function of its children's numbers, - collapsing a subtree into a summary record for a report, - checking a structural invariant bottom-up, where a parent's verdict depends on both children's verdicts, - any "unwind and clean up" pass at all. ## Why some work is parent-first Invert the dependency and you get preorder. If each node must be handed something the parent computed — the path taken from the root to reach it, an accumulated set of conditions, a depth stamp, an inherited routing prefix — the parent has to be processed before the descent, so the value is in hand when the children are visited. Preorder is also the natural serialization order: emit the node, then its left subtree, then its right, using an explicit sentinel token where a child is missing, and a rebuilder can consume that stream front to back, creating each node before its children. A nuance worth stating honestly, because interviewers probe it: **copying** a tree is not rigidly preorder. The familiar top-down copy (create the copied node, then recurse and attach each copied child) is preorder, but a bottom-up copy that builds both child copies first and then constructs the parent from them is postorder and equally correct. Copying works either way because the copy has no ordering constraint of its own. Releasing does not have that freedom, which is exactly why teardown is the sharper example. ## Why some work is tier-defined And sometimes the task's shape is neither up nor down but *across*. Rendering the routing rule set to an operations dashboard one tier at a time — every depth-1 rule, then every depth-2 rule — cannot be produced by any placement of the visit inside a recursive left/right descent, because a depth-first walk finishes one whole branch before touching the sibling branch's second level. That job needs the queue-driven level-order walk. ## Reconstruction: another place order carries information The orders also differ in how much information their *output* preserves. With distinct values, a preorder sequence plus an inorder sequence reconstructs the original binary tree uniquely: preorder names the root, inorder splits the remaining values into the left and right groups, and you recurse. Preorder plus postorder does **not** determine the tree in general — for a node with exactly one child, nothing in either sequence says which side it was on; the pair is only sufficient when every node has zero or two children. A single preorder sequence with explicit empty-child markers is enough on its own, because the markers restore the shape the plain sequence loses. ## How to answer it out loud Name the dependency direction first, then the order it forces, then the cost as an aside: > "Freeing a node destroys the links to its children, so children first — that's postorder. The choice isn't about speed; all four are linear. It's that the dependency runs upward, and postorder is the order that respects it. If the dependency ran downward — stamping each node with its path from the root — I'd want preorder instead." ## What people get wrong - "All O(n), so pick any." Conflates cost with correctness. - "Preorder frees the parent first, which detaches the children so they get cleaned up." Detaching is what makes them unreachable, not what reclaims them. - "Use level-order, it touches each node once too." It does, but it releases parents before their children — the same bug with an extra queue. - "Postorder is only for arithmetic on trees." Aggregation is one instance of the child-first dependency, not the whole category.