Why can a decision tree's pre-pruning rules reject a split that post-pruning would keep?

## Greedy growth has a one-split horizon A decision tree is built by recursive greedy search. At each node the algorithm scores every candidate cut by the impurity it removes *immediately*, takes the best one, and recurses. It never asks what would become possible two splits later. That is what makes tree fitting fast, and it is also its structural weakness. Now layer a stopping rule on top. A minimum-impurity-decrease threshold, a depth cap, or a minimum node size all ask the same kind of question: is this split, on its own, worth making? For most nodes the answer is a fair proxy for whether the branch is worth growing. But not always. ## The failure case Suppose at depth 3 the best available split moves Gini by almost nothing — it separates the rows into two halves that are just as mixed as the parent. Under a minimum-impurity-decrease threshold, the split is refused and the node becomes a leaf. But suppose that split, useless as it is by itself, isolates a region in which a *fourth* feature suddenly separates the classes cleanly. The depth-4 split would have been excellent. It is never evaluated, because its parent was never made. This is the **horizon effect**: the payoff lies just beyond the depth the stopping rule can see. The canonical structure behind it is an interaction. With an XOR-shaped relationship — the target is positive when exactly one of two binary features is on — neither feature alone reduces impurity at all, because each leaves both classes evenly mixed on both sides. Only the *combination* is informative. A greedy scorer sees two useless features; a stopping rule then confirms that verdict and closes the branch. Real data shows softer versions of this constantly: a segment flag that is uninformative overall but changes what a price threshold means inside one segment. ## Why post-pruning does not have this problem Cost-complexity pruning grows the tree first, then decides what to remove. When it evaluates the depth-3 node, the quantity that matters is the error of the *entire subtree rooted there* versus the error of collapsing it to a leaf. The strong depth-4 split is inside that subtree, so the saving is large, the break-even price per removed leaf is high, and the node is not a weak link. It survives — along with the useless split that made it reachable. Put in one line: pre-pruning evaluates a split in isolation before its children exist; post-pruning evaluates a node together with everything it enabled. ## The tradeoff, honestly stated Post-pruning is not free. - **Compute and memory.** You grow a tree to purity and then discard most of it. On tens of millions of rows, or on data where a fully grown tree does not fit in memory, that is not a reasonable bill to pay. Pre-pruning saves exactly the work that post-pruning wastes, because a refused split removes an entire subtree's worth of candidate scanning. - **Simplicity of tuning.** Pre-pruning limits are direct and interpretable ("no leaf below 50 patients"), and can be dictated by domain requirements rather than tuned at all. Cost-complexity alpha has to be selected on held-out data and is measured on the error scale of the specific problem. - **Statistical honesty.** Post-pruning's later comparison is made on the same training data unless you cross-validate it, which is why alpha selection needs held-out folds. A leaf-size floor needs no such machinery. Could pre-pruning be given lookahead? In principle yes — evaluate the best two-level combination at each node instead of the best single split. In practice the candidate count multiplies, the cost becomes prohibitive on wide data, and it only pushes the horizon out by one level; a three-deep interaction defeats it again. That is why the standard answer to the horizon effect is post-pruning rather than deeper lookahead. ## How they combine The two are not mutually exclusive, and production practice often mixes them: keep loose pre-pruning limits so the full tree remains buildable and no leaf is absurdly small, then apply cost-complexity pruning on top and choose alpha by cross-validation. The discipline is to keep the pre-pruning limits loose enough that they are not silently making the pruner's decisions for it. If your depth cap is 4 and the pruner never removes anything, the depth cap is your model-selection procedure and alpha is decoration. ## What interviewers are listening for The insight to voice is that greedy search and greedy stopping compound: the split scorer is myopic, and a stopping rule built on that same myopic score inherits the blind spot. Candidates who can name the interaction case, say why the subtree comparison fixes it, and then concede the compute cost of growing first have given the complete answer.