Pruning (pre-pruning, post-pruning)

The problem, from first principles

Growing every positive-gain split can create branches that memorize a few training examples. Pre-pruning rejects suspiciously small children while building; post-pruning removes branches that do not earn their complexity on held-out data. This exercise implements both controls around the tree from 03-best-split-minimal-tree.

From theory to code

Implement build_tree_pre_pruned and prune_tree. Theory explains the extra child-size condition and the bottom-up comparison between a recursively pruned subtree and one fallback leaf.

Constraints

• build_tree_pre_pruned follows the previous tree's depth, sample-count, purity, and no-split stop rules.
• Reject a candidate split when either child has fewer than min_samples_leaf samples.
• Every returned node stores the training-label majority class in default.
• prune_tree returns a new tree and never mutates its tree argument.
• Route validation data by each node's stored feature and inclusive threshold before recursing.
• Replace a subtree when the fallback leaf's validation error is less than or equal to the subtree error; use default if no validation label reaches a node.

Hints

Open one at a time. Each gives away a little more than the last.