Decision Trees: CART, Splitting Criteria, and Pruning

A decision tree is a piecewise-constant function on a hierarchical partition of feature space. At each internal node, the data is split on a single-feature threshold; at each leaf, predictions are the majority class (classification) or mean (regression) of the training samples routed there. The reason trees matter in 2026 is not because they win alone — they don't, a single tree is beaten by a linear model on most real datasets — but because they are the atomic unit of every dominant tabular learner: Random Forest, XGBoost, LightGBM, CatBoost. Understanding a single tree's failure modes (variance, bias toward high-cardinality features, axis-aligned splits) is what separates a candidate who can tune an ensemble from one who parrots defaults.

The algorithm you need to know in an interview is CART (Classification and Regression Trees), introduced by Breiman et al. in 1984. CART is a greedy, top-down, recursive binary splitter: at each node, it exhaustively tries every feature-threshold combination, picks the one that most reduces impurity, and recurses. Greedy because it never backtracks — finding the globally optimal tree is NP-hard (Hyafil & Rivest, 1976). Binary because multi-way splits fragment the data too quickly (a 10-way categorical split at depth 3 leaves 1000× less data per leaf than binary). Top-down because bottom-up agglomeration has no obvious stopping rule.

At each node, CART solves: find the feature j and threshold t that maximize impurity reduction on the data routed to this node. For n samples and d features, the naive cost is O(n · d) per split if you test every unique value. Sorting the feature once per node reduces the sweep to O(n log n) per feature per level, and reusing the sort (as LightGBM does with presorted indices) gets the per-level cost down to O(n · d) amortized.

Why binary splits, not multi-way? Multi-way splits on a k-valued categorical create k children per node. At depth 3, binary gives you 8 leaves; 10-way multi-way gives you 1000. Each leaf has 1/1000 the data, so variance explodes. CART always does binary — for a k-category feature, it finds the optimal binary partition of the k categories into two groups.

Why greedy, not optimal? Finding the globally optimal binary tree of bounded depth is NP-hard (Hyafil & Rivest 1976). Greedy top-down is a heuristic that works well in practice because most useful signal is additive: the best split at the root is usually close to the best feature overall, and subsequent splits refine. The failure mode: XOR-like interactions where no single-feature split at the root reveals signal. A depth-2 tree can represent XOR (split on x₁, then on x₂ under each branch), but the greedy root split sees zero gain and may never grow. In practice, this is why ensembles help — different bootstrap samples surface the interaction differently.

There are two philosophies for preventing overfitting. Pre-pruning stops tree growth early using thresholds: max_depth (hard depth cap), min_samples_split (refuse to split a node with fewer samples), min_samples_leaf (refuse splits that create small leaves), min_impurity_decrease (refuse splits with gain below threshold). Pre-pruning is fast (less work) but myopic — it may stop at a node whose children would have been very useful (the XOR trap again: zero gain at root, huge gain at depth 2).

Post-pruning grows a full tree, then collapses subtrees that don't improve validation performance. The canonical algorithm is cost-complexity pruning (Breiman 1984), also called weakest-link pruning. Each subtree T is scored as R_α(T) = R(T) + α|T|, where R(T) is the training error and |T| is the number of leaves. As α increases from 0 to ∞, subtrees are collapsed in a nested sequence from the fully-grown tree to the root. You then pick α via k-fold cross-validation. Sklearn exposes this as ccp_alpha — clf.cost_complexity_pruning_path(X, y) returns the candidate α values.

Why ensembles skip pruning entirely. In Random Forest, you want each tree to overfit — averaging many overfit trees is exactly how bagging reduces variance. Pruning would reduce the variance of each tree but also reduce ensemble diversity, leaving you with fewer, more correlated trees. The net effect is worse than no pruning. Same logic applies to XGBoost: shallow trees (depth 3–6) are the regularizer; pruning is redundant and would destroy the sequential residual-fitting.

For a k-valued categorical feature, CART must find the best binary partition of the k categories into two groups. Brute force: 2^(k-1) − 1 non-trivial partitions. For k = 20, that's 500K — infeasible at every split.

Fisher 1958's insight: for binary classification or regression, sort the categories by their target mean (mean of y within each category). The optimal binary partition is always a prefix split on this sorted order, reducing the search to k − 1 candidates — O(k) instead of O(2^k). This is a rare case where greedy-with-sorting is provably optimal.

LightGBM and CatBoost exploit this trick natively for categoricals; XGBoost and sklearn do not — they require one-hot encoding. And here is the interview trap: one-hot encoding destroys decision tree performance on high-cardinality categoricals. Each one-hot dummy is a binary feature that can only isolate 1 category at a time. A split on dummy = city_paris peels off Paris versus everyone else, then the next split peels off London, and so on. Depth is wasted, leaves become imbalanced (one category versus the union of all others), and the model fails to learn groupings of similar categories. The correct approach with sklearn/XGBoost is target encoding with smoothing (replace each category with its target mean, regularized by a prior), which recovers most of Fisher's advantage.

CART's original treatment of missing values is the surrogate split: at each internal node, CART computes not only the primary split but a ranked list of backup (surrogate) splits that mimic the primary split's routing as closely as possible. At inference, if a sample's primary-split feature is missing, the first available surrogate is used. This handles missingness without any imputation and preserves any information encoded in missingness patterns.

What sklearn does not implement. Sklearn's DecisionTreeClassifier does not support surrogate splits. You must impute (mean/median for numerics, mode for categoricals) or encode missingness as a separate feature. Rpart (R's CART implementation) does implement surrogates — the tree package in R gives you the original Breiman algorithm. In practice, for sklearn pipelines, the common fix is adding an is_missing_<feature> binary indicator alongside an imputed value, letting the tree learn to split on missingness if it's informative.

XGBoost's learned default direction is a modern alternative: at each split, try routing missing values left vs right, pick the direction that maximizes gain, store as the default. This is simpler than surrogate splits (one default per node vs a full ranked list) but achieves similar effect. LightGBM and CatBoost do the same.

A fully-grown decision tree (no pruning, no depth cap, one sample per leaf) has zero training error by construction — every sample is its own leaf. This is maximum variance, near-zero bias. A tiny change in training data (flip one label, add one sample) can completely restructure the tree, because the greedy split at the root cascades into different downstream splits. This instability is both the weakness (generalization is poor) and the strength (it's exactly what bagging exploits: average many unstable, uncorrelated estimators to get a low-variance estimate).

The opposite extreme — a tree of depth 1 (a 'stump', one split) — has high bias, low variance. This is what AdaBoost and gradient boosting use as the weak learner: many high-bias stumps combined to reduce bias sequentially. The depth parameter is the bias-variance knob.

Extrapolation failure. A tree predicts only within the range of training targets. For regression, every leaf predicts the mean of its training samples — so the model's output range is bounded by [min(y_train), max(y_train)]. A tree trained on house prices from 2020 will never predict a 2026 price higher than the highest 2020 price. This is critical in time series, physical systems, or any extrapolation setting — use linear models or Gaussian processes instead.

The default feature_importances_ in sklearn (and importance_type='gain' in XGBoost) is Mean Decrease in Impurity (MDI): sum the impurity reduction a feature causes across all splits in all trees, normalize. It's fast — computed for free during training — but statistically biased (Strobl et al. 2007). The bias has two sources: (1) high-cardinality features have more potential split points, so they appear more often as 'best split' even when they carry no signal; (2) correlated features 'share credit' — one gets inflated importance, the other gets near-zero.

Permutation importance (Breiman 2001) fixes the cardinality bias: after training, shuffle one feature across the test set and measure the increase in error. A feature with no predictive value shows no error increase under permutation. Works for any model, costs O(d · n_repeats · inference_time). Still has a weakness: correlated features both show low permutation importance (shuffling one still leaves the other to carry the signal).

TreeSHAP (Lundberg et al. 2020, NeurIPS paper 'From local explanations to global understanding with explainable AI for trees') is the gold standard. It computes exact Shapley values for tree models in polynomial time O(T · L · D²) where T = trees, L = max leaves, D = max depth. Without the tree structure trick, exact Shapley is O(2^d) — exponential. TreeSHAP satisfies three axioms MDI violates: efficiency (feature attributions sum exactly to prediction − baseline), symmetry (features with identical contribution get identical SHAP), dummy (non-contributing features get exactly zero). For any production use — regulatory audits, debugging, feature selection — use TreeSHAP. Reserve MDI for quick sanity checks during model development.

Standard CART / XGBoost / LightGBM trees have a different split at every internal node — the structure is irregular, which means inference requires a per-sample traversal with branch mispredictions on every level. On modern CPUs, this limits throughput to ~100K predictions/sec/core for a depth-6 tree.

Oblivious trees (used by CatBoost, also in Microsoft's MatrixNet since 2009) are symmetric: at every node of level d, the same feature-threshold split is used. A depth-6 oblivious tree is fully described by 6 (feature, threshold) pairs and 64 leaf values. Inference becomes a branchless 6-bit lookup: compute 6 comparisons, pack them into a 6-bit index, index into a 64-element lookup table. This vectorizes trivially with SIMD — achievable throughput is ~10M predictions/sec/core, a roughly 100× speedup.

The tradeoff: oblivious trees are less expressive per tree (symmetric structure can't adapt branches differently), so you need more trees to match the accuracy of a standard ensemble. For latency-critical inference (ad serving, fraud scoring at hundreds of thousands of QPS), the 100× inference speedup is worth the 2× more trees. This is why CatBoost is preferred at Yandex, Uber, and other companies with strict latency SLAs on tree-based models.

Interview signal: mentioning oblivious trees and the symmetric-structure → vectorized-inference argument is an instant staff-level marker. Almost no prep content covers this.