69 Decision Trees Interview Questions and Answers (2026)

A decision tree is a supervised model that predicts by asking a sequence of simple questions about the features (e.g. "is age < 30?"). Each answer routes a sample down a branch until it reaches a leaf that outputs a class or a value. It works for both classification and regression.

• Structure:

  • Root and internal nodes hold a test on one feature (threshold for numeric, category membership for categorical).

  • Leaves hold the prediction: majority class (or class proportions) for classification, mean target for regression.

• How it learns:

  • Greedily picks the split that most reduces impurity (Gini, entropy) or error (MSE), then recurses on each child.

  • Stops on criteria like max_depth, min_samples_leaf, or pure nodes; may be pruned afterwards.

• Strengths: Interpretable (rules can be read off a path), no feature scaling needed, captures non-linearities and interactions, fast inference.

• Weaknesses:

  • High variance: overfits easily and small data changes can produce a very different tree.

  • Piecewise-constant, axis-aligned boundaries; usually outperformed by ensembles (random forests, gradient boosting) built from many trees.

An internal node makes a decision (tests a feature and routes the sample to a child); a leaf node makes the prediction (it has no children and outputs a class or value).

• Internal node (including the root):

  • Stores a split rule: feature + threshold (e.g. x3 <= 2.5) or a category subset.

  • Has two or more children (exactly two in CART / scikit-learn).

  • Chosen to maximize impurity reduction on the samples reaching it.

• Leaf (terminal) node:

  • No split; holds the output: majority class or class probabilities (classification), mean of targets (regression).

  • Created when a stopping rule fires: node is pure, max_depth reached, too few samples, or no split improves impurity.

• Relationship:

  • Each root-to-leaf path is a conjunction of rules; leaves partition the feature space into disjoint regions.

  • Pruning turns internal nodes back into leaves to reduce overfitting.

Because each standard split tests a single feature against a threshold (x_j <= t), every boundary is perpendicular to one feature axis. The tree carves feature space into axis-parallel rectangles (hyper-rectangles), each mapped to a leaf prediction.

• Geometry: In 2D, splits are vertical or horizontal lines; combined, they form a staircase-shaped decision boundary.

• Consequence: diagonal boundaries are expensive:

  • A simple boundary like x1 > x2 needs many splits to approximate as a staircase, leading to deeper trees and overfitting.

  • Trees are sensitive to rotation of the feature space, unlike linear models or kNN.

• Mitigations:

  • Feature engineering (add x1 - x2, ratios) or PCA rotation.

  • Oblique trees split on linear combinations of features.

  • Ensembles average many staircases into smoother boundaries.

• Upside: Single-feature splits keep rules interpretable and make trees invariant to monotonic feature scaling.

It is a top-down, greedy, divide-and-conquer procedure: find the single best binary split of the current data, divide it into two children, and repeat on each child until a stopping rule halts growth.

• Algorithm (CART):

  1. Start with all training samples at the root.

  2. For every feature and every candidate threshold (midpoints between sorted unique values), compute the weighted impurity of the two children.

  3. Pick the split with the largest impurity decrease (Gini/entropy for classification, MSE for regression).

  4. Send samples left (x_j <= t) or right, and recurse on each subset independently.

  5. Make a node a leaf when it is pure, hits max_depth, has fewer than min_samples_split, or no split helps; assign majority class or mean.

• Why greedy: Finding the globally optimal tree is NP-hard, so each split is locally optimal with no look-ahead (can miss splits that only pay off later, e.g. XOR).

• Cost: Roughly O(n_features · n log n) per level using sorted values.

• Controlling overfitting: Pre-pruning via stopping rules, or grow fully then post-prune (cost-complexity pruning).

Trees need no one-vs-rest decomposition: the impurity measures and leaf predictions are defined over any number of classes, so a single tree handles K classes directly.

• Splitting criteria generalize to K classes:

  • Gini: 1 − Σ p_k² over all K classes.

  • Entropy: −Σ p_k log p_k; a split is good if children are dominated by fewer classes.

• Leaves store a class distribution: Prediction is the majority class; predict_proba returns class fractions in the leaf.

• Different branches can isolate different classes: One split might separate class A from {B, C}, a later one B from C; the tree learns this hierarchy itself.

• Contrast: Binary models like SVMs or standard logistic regression need one-vs-rest/one-vs-one or softmax. Gradient-boosted trees, however, usually fit one tree per class per round.

• Caveat: Rare classes may be swamped; use class_weight or resampling.

Each split is a simple threshold, but stacking them creates a piecewise-constant function whose regions and outputs depend on conditional combinations of features. The overall mapping from inputs to output is therefore not a weighted sum of features, i.e. non-linear.

• Piecewise-constant output: A tree is f(x) = Σ c_m · 1[x ∈ R_m]: step functions, not a line or hyperplane.

• Conditional splits create interactions: A split on x2 below a split on x1 applies only in that x1 region, so the effect of x2 depends on x1.

• Non-linear decision boundaries: Union of rectangles can form any shape (staircases, islands, XOR-like regions), approximating arbitrary boundaries with enough depth.

• Contrast with linear models: A linear classifier yields one hyperplane; even a depth-1 tree (stump) is a step function, already non-linear in the feature.

• Side effect: Trees can't extrapolate trends: outside the training range they predict a constant leaf value.

Decision trees are easy to interpret, need little data preparation, and capture non-linear relationships and feature interactions without you having to specify them, which makes them a strong baseline and the building block of top ensembles.

• Interpretability:

  • A prediction is a readable path of if/else rules, so it is easy to explain to stakeholders and to audit.

  • Shallow trees can be drawn and checked by domain experts.

• Minimal preprocessing:

  • No feature scaling or normalization: splits depend only on the ordering of values.

  • Monotonic transforms (log, etc.) don't change the tree, and outliers in input features have little effect.

  • Handles numeric and categorical features; some implementations handle missing values natively (C4.5, CART surrogate splits, sklearn ≥ 1.3).

• Non-linear and interaction effects for free: Nested splits model interactions (e.g. "age > 60 AND smoker") without manual feature engineering.

• Built-in feature selection: Irrelevant features are simply never chosen; impurity-based importances (feature_importances_) come for free.

• Efficiency and versatility:

  • Prediction is O(depth); training is roughly O(n·d·log n).

  • Works for classification, regression, and multi-output problems.

  • Base learner for Random Forests and gradient boosting (XGBoost, LightGBM), which fix most single-tree weaknesses.

A single tree is a high-variance learner: it overfits easily, changes drastically with small data changes, and its axis-aligned, piecewise-constant structure limits accuracy, which is why trees are usually used inside ensembles.

• Overfitting / high variance:

  • Grown fully, a tree can memorize the training set (pure leaves with one sample).

  • Needs regularization: max_depth, min_samples_leaf, or cost-complexity pruning (ccp_alpha).

• Instability: A small change in data can change the root split, and every split below it, giving a very different tree.

• Greedy construction: Each split is locally optimal; finding the globally optimal tree is NP-hard, so the result can be suboptimal (e.g. XOR patterns where no single first split looks useful).

• Axis-aligned, piecewise-constant boundaries:

  • Diagonal or smooth boundaries are approximated by many "staircase" splits.

  • Regression trees cannot extrapolate: predictions outside the training range are just leaf means.

• Biases:

  • Impurity-based criteria favor high-cardinality features, and impurity importances inherit that bias.

  • Imbalanced classes can produce trees dominated by the majority class unless weighted (class_weight).

• Lower accuracy than ensembles: bagging (Random Forest) reduces variance and boosting reduces bias, usually beating a single tree.

Gini impurity measures how mixed the classes in a node are: it is the probability that a randomly chosen sample would be misclassified if it were labeled randomly according to the node's class distribution. It is 0 for a pure node and largest when classes are evenly mixed.

• Formula: G = 1 − Σ p_k²:

  • p_k is the fraction of samples of class k in the node.

  • Equivalent to Σ p_k(1 − p_k): the chance of picking class k times the chance of mislabeling it.

• Range:

  • 0 (pure) to 1 − 1/K for K classes; 0.5 maximum for binary.

  • Examples: 50/50 gives 0.5; 90/10 gives 1 − (0.81 + 0.01) = 0.18.

• How it drives splits:

  1. For each candidate split, compute Gini of each child.

  2. Weight by child size: (n_L/n)·G_L + (n_R/n)·G_R.

  3. Choose the split with the lowest weighted Gini (largest impurity decrease).

• Used by CART and is the default in scikit-learn (criterion="gini"); cheaper than entropy because it needs no logarithm.

Entropy measures the uncertainty (disorder) of the class distribution in a node: how many bits on average you'd need to encode a sample's label. A pure node has entropy 0; an evenly mixed node has maximum entropy. Trees split to reduce it.

• Formula: H = − Σ p_k · log2(p_k):

  • With 0·log 0 defined as 0.

  • Range: 0 to log2(K); binary maximum is 1 bit at 50/50.

  • Example: 90/10 gives −(0.9·log2 0.9 + 0.1·log2 0.1) ≈ 0.469.

• Role in tree building:

  • Used to compute information gain: parent entropy minus weighted child entropy. The split with the highest gain wins.

  • Core criterion in ID3 and C4.5 (which uses gain ratio); available in scikit-learn as criterion="entropy" or "log_loss".

• Intuition:

  • Rare classes carry more "surprise" (−log p); entropy is the expected surprise.

  • Behaves very similarly to Gini, but costs a log per class to compute.

Information gain is the reduction in entropy produced by a split: parent entropy minus the size-weighted average entropy of the children. The tree evaluates every candidate split and picks the one with the largest gain.

• Formula: IG = H(parent) − Σ (n_i / n) · H(child_i): Weighting by n_i / n prevents a tiny pure child from dominating.

• Steps:

  1. Compute entropy of the parent node.

  2. Partition samples by the candidate split; compute each child's entropy.

  3. Take the weighted average of child entropies and subtract from the parent.

  4. Repeat for all features and thresholds; for numeric features, candidates are midpoints between consecutive sorted distinct values.

• Worked example:

  • Parent 5+/5−: H = 1.0.

  • Children 4+/1− and 1+/4− (5 each): each H ≈ 0.722.

  • IG = 1.0 − (0.5·0.722 + 0.5·0.722) ≈ 0.278 bits.

• Same idea with Gini is called Gini gain / impurity decrease.

Standard (CART) regression trees split to maximize variance reduction: they choose the feature and threshold that minimize the weighted sum of squared errors (MSE) of the two children, with each leaf predicting the mean of its targets.

• The objective:

  • Node impurity = MSE = (1/n) Σ (yᵢ − ȳ)², which is just the variance of the targets in the node.

  • Pick the split maximizing Var(parent) − [ (n_L/n)·Var(L) + (n_R/n)·Var(R) ].

• Why the mean in the leaf: The mean is the constant that minimizes squared error, so the criterion and the leaf prediction are consistent.

• Why it's the default: Cheap to evaluate: running sums of y and y² give each candidate threshold's SSE in O(1) after sorting.

• In scikit-learn: DecisionTreeRegressor(criterion="squared_error") is the default; alternatives are "friedman_mse", "absolute_error" (median leaves, robust) and "poisson" (count targets).

The maximum is 0.5, reached when the two classes are perfectly balanced (p = 0.5).

• Derivation:

  1. Gini = 1 − p² − (1 − p)² = 2p(1 − p).

  2. The derivative 2 − 4p equals 0 at p = 0.5, giving 2·0.5·0.5 = 0.5.

• Interpretation: Two random draws disagree in label half the time. This is the most mixed a binary node can be.

• Generalization:

  • For K classes the maximum is 1 − 1/K (uniform distribution), so it approaches 1 as K grows.

  • Compare with binary entropy, whose maximum is 1 bit at the same point.

scikit-learn implements an optimized version of CART: binary splits chosen by impurity reduction, used by both DecisionTreeClassifier and DecisionTreeRegressor.

• CART traits you'll see:

  • Always binary splits (threshold on a feature).

  • criterion options: "gini", "entropy", "log_loss" for classification; "squared_error" etc. for regression.

  • Cost-complexity pruning via ccp_alpha and cost_complexity_pruning_path().

• Differences from textbook CART:

  • Historically required numeric input (categoricals had to be encoded); no surrogate splits.

  • Missing-value support was added natively in recent versions (1.3+), by learning which child NaNs go to rather than surrogates.

• Choosing criterion="entropy" does not make it ID3/C4.5: splits stay binary and there is no gain ratio.

A tree split only asks "is x ≤ t?", which depends on the ordering of values, not their magnitude; any monotonic rescaling preserves the order, so the same partitions and impurity reductions are available and the tree is equivalent.

• Splits are rank-based:

  • Standardizing x maps threshold t to (t − μ)/σ; the same samples go left and right.

  • Impurity is computed from target labels in each child, never from feature values.

• Features are evaluated one at a time: No distances or dot products combine features, unlike k-NN, SVMs, or gradient-descent models where scale dominates.

• Caveats:

  • Also robust to monotonic transforms like log, but non-monotonic transforms change splits.

  • Scaling still matters if the tree sits in a pipeline with scale-sensitive steps (PCA, oblique trees, k-NN imputation).

A new instance is routed from the root to a single leaf by answering one feature test per internal node. The prediction is the majority class of the training samples that ended up in that leaf.

• Traversal:

  1. Start at the root, which holds a test such as petal_length <= 2.45.

  2. Go left if the test is true and right if it is false (or follow a category branch for categorical splits).

  3. Repeat at each internal node until a leaf is reached.

• Leaf output:

  • During training, each leaf stores the class counts of the samples that fell into it.

  • The predicted label is the class with the highest (optionally weighted) count.

  • Those same counts give the class probabilities (predict_proba).

• Geometric view:

  • The splits partition feature space into axis-aligned rectangles, one per leaf.

  • Every point inside a given rectangle receives the same label.

• Cost:

  • Prediction takes O(depth) comparisons, which is very fast.

  • Only the features on the instance's path are ever examined.

Traversal is the same as in classification: route the instance down the tree to one leaf. The difference is the output. The leaf returns a single number summarizing the training targets that landed there, usually their mean.

• Leaf value depends on the split criterion:

  • With squared error (MSE), the leaf predicts the mean of its training targets, because the mean minimizes squared error.

  • With absolute error (MAE), the leaf predicts the median.

• Consequences:

  • The prediction is piecewise constant: every point in a leaf's region gets the same value.

  • Outputs can never fall outside the range of the training targets, so the tree cannot extrapolate.

  • Small leaves average only a few targets, so their predictions are noisy. Tuning min_samples_leaf smooths this.

The instance is routed to its leaf, and the tree returns the fraction of training samples of each class in that leaf. For example, a leaf holding 8 positives and 2 negatives outputs [0.2, 0.8].

• Mechanics:

  • Each leaf stores per-class counts, weighted by sample_weight or class_weight if those are set.

  • The probability for class k is count_k divided by the total count in the leaf. In scikit-learn this is predict_proba.

• Caveats:

  • Fully grown trees have pure leaves, so they output hard 0/1 probabilities that are overconfident.

  • Small leaves give coarse, high-variance estimates: a leaf with 1/1 positives still says 100%.

  • There are only as many distinct probability values as there are leaves, which hurts ranking metrics like AUC.

• Fixes:

  • Constrain growth with min_samples_leaf or max_depth.

  • Apply Laplace smoothing: (count_k + 1) / (n + K).

  • Calibrate afterwards with CalibratedClassifierCV.

  • Average probabilities across an ensemble such as a random forest.

An unconstrained tree keeps splitting until its leaves are pure or nearly empty. That lets it memorize the training set, including noise and outliers: training error approaches zero while variance is very high, so predictions generalize poorly.

• Capacity grows with depth: A depth-d tree can carve the feature space into up to 2^d regions. With enough depth, every training point can get its own leaf.

• Deep leaves rest on tiny samples:

  • Each split partitions the data, so deep nodes decide splits from a handful of points. Impurity reductions there are often just chance.

  • Leaf predictions based on 1–2 samples are extremely noisy estimates.

• High variance and instability: Greedy, hierarchical splitting means a small change in the data can change an early split and the entire subtree below it.

• Remedies:

  • Pre-pruning: limit growth with max_depth, min_samples_leaf, or min_impurity_decrease.

  • Post-pruning: remove weak subtrees afterwards, e.g. cost-complexity pruning with ccp_alpha.

  • Ensembles: bagging and random forests average many deep trees to reduce variance.

Pre-pruning (early stopping) stops tree growth during construction once a stopping criterion is met. Post-pruning grows a full tree first and then removes subtrees that don't improve generalization. Pre-pruning is cheaper; post-pruning is usually more accurate because it judges splits with full hindsight.

• Pre-pruning:

  • Typical criteria: max_depth, min_samples_split, min_samples_leaf, max_leaf_nodes, min_impurity_decrease.

  • Pros: fast, low memory, and simple.

  • Cons: short-sighted (the horizon effect), because it may reject a weak split that leads to strong splits below it. It also has several thresholds to tune.

• Post-pruning:

  • Methods: cost-complexity pruning (CART, ccp_alpha), reduced-error pruning (validation set), and pessimistic error pruning (C4.5).

  • Pros: evaluates whole subtrees, so it captures interactions and usually generalizes better.

  • Cons: growing the full tree first is more expensive.

• Shared goal: Both reduce variance and overfitting by limiting tree complexity. The hyperparameters for either should be chosen by cross-validation.

Each root-to-leaf path is one rule. The rule is the AND of the split conditions along the path, and it predicts that leaf's class or value. You can print the rules with a built-in exporter or walk the tree's node arrays yourself.

• Quick option: sklearn.tree.export_text(clf, feature_names=...) prints an indented if/else view of the tree.

• Manual traversal of clf.tree_:

  • Use the arrays children_left, children_right, feature, threshold and value.

  • A node is a leaf when children_left == -1.

  • The left branch means x[f] <= threshold; the right branch means >.

• Make the rules readable:

  • Merge repeated conditions on the same feature into an interval (e.g. 3 < age <= 40).

  • Attach the leaf's sample count and class purity, so readers can see each rule's support and confidence.

  • Drop or merge rules from tiny, low-support leaves. Prune the tree first so the rule count stays small.

Prediction is O(H). The sample does one threshold comparison per level from the root to a leaf, regardless of the number of features or training rows.

• Why: Each internal node checks a single feature against a threshold. That is O(1) work, and it picks exactly one child.

• Depth in terms of n training samples:

  • A balanced tree has H ≈ log₂ n, so prediction is O(log n).

  • A degenerate, chain-like tree has H up to n − 1, so prediction is O(n). Depth limits prevent this.

• Related costs:

  • An ensemble of T trees costs O(T·H) per prediction.

  • Training is much costlier: roughly O(m · n log n) for m features with presorting.

Choose a single tree when interpretability, auditability, or tight latency and resource limits matter more than the last few points of accuracy, and when a shallow tree already performs close to an ensemble.

• Explainability and regulation:

  • Credit, insurance, healthcare: each prediction is a readable rule path that can be justified to customers or regulators.

  • Domain experts can review, sanity-check, or hand-edit the logic.

• Deployment constraints: Inference is a few comparisons: tiny memory, microsecond latency, suits edge devices or embedding as SQL/if-else rules.

• Small accuracy gap: Simple, low-noise problems or small datasets where a pruned tree matches the ensemble on validation.

• Rule extraction and prototyping: Quick baseline, or a surrogate tree to explain a black-box model.

• Trade-off to acknowledge: A single tree has high variance; control it with depth limits, min_samples_leaf, or cost-complexity pruning (ccp_alpha), and monitor stability on retraining.

XOR's classes sit in opposite quadrants, so no single line separates them. A tree uses nested splits: first on x1, then on x2 within each branch, carving the space into four quadrants and labeling each correctly with depth 2.

• The tree:

  • Root: x1 <= 0.5.

  • Each child: x2 <= 0.5, with leaf labels flipped between the left and right subtree.

  • Result: (0,0)→0, (0,1)→1, (1,0)→1, (1,1)→0.

• Why it works: Hierarchical splits model the interaction: the meaning of x2 depends on x1's branch.

• The greedy catch:

  • On balanced XOR, the root split on either feature gives zero impurity reduction (each child stays 50/50), so a greedy learner sees no gain.

  • It still works in practice because ties are broken (e.g. random feature choice in scikit-learn) and growth continues as long as the node isn't pure; with min_impurity_decrease > 0 or noisy data it can stop early.

• Linear alternative: A linear model needs an engineered feature like x1·x2 to solve XOR.

A feature with many distinct values splits the data into many small groups, and small groups are likely to be pure by chance. Their entropy is near zero, so information gain looks large even when the feature has no real predictive power.

• Extreme case: an ID column:

  • Each row gets its own child, every child is pure, so IG equals the full parent entropy: the maximum possible.

  • The split is useless for new data: pure memorization.

• Why it happens statistically:

  • Entropy estimated from few samples is biased downward; more branches mean smaller children and more optimistic estimates.

  • In binary-split trees (CART) the bias persists because high-cardinality features offer more candidate thresholds/groupings, so more chances to find a spuriously good one.

• Mitigations:

  • Gain ratio (C4.5): divide IG by split information −Σ (n_i/n) log2(n_i/n), which grows with the number of branches.

  • Regularize: min_samples_leaf, depth limits, pruning.

  • Unbiased split selection via significance tests (conditional inference trees), or grouping rare categories.

  • Drop identifier-like columns before training.

• Related pitfall: impurity-based feature importance inherits this bias; prefer permutation importance on held-out data.

Gain ratio (used in C4.5) divides information gain by the split information, the entropy of the partition itself. Attributes that shatter the data into many small branches have large split information, so their inflated gain gets normalized down.

• The bias in information gain:

  • More branches means smaller, purer children, so IG rises with cardinality even if the attribute is meaningless.

  • Extreme case: a unique ID gives one pure leaf per row, so maximal IG and zero generalization.

• The correction:

  1. SplitInfo(A) = −Σᵥ (|Sᵥ|/|S|) log₂(|Sᵥ|/|S|).

  2. GainRatio(A) = IG(A) / SplitInfo(A).

  3. An ID column over n rows has SplitInfo = log₂ n, which grows with n and heavily penalizes it.

• Its own weakness:

  • When SplitInfo is near 0 (very unbalanced splits), the ratio blows up and can favor useless splits.

  • C4.5's fix: only consider attributes whose IG is at least the average IG, then choose by gain ratio.

• Other ways around it: Use binary splits only (CART), or conditional-inference/permutation-based tests that correct for multiple comparisons.

Both measure node impurity from class proportions pₖ. Gini is 1 − Σ pₖ² = Σ pₖ(1 − pₖ), while entropy is −Σ pₖ log pₖ. Gini is essentially entropy with the logarithm replaced by its first-order approximation, so the two are very similar but differ in scale and in how hard they penalize rare classes.

• The approximation link: Near p = 1, −log p ≈ 1 − p. Substituting into −Σ pₖ log pₖ gives Σ pₖ(1 − pₖ), which is Gini.

• Shared properties: Both are 0 for pure nodes, maximal at the uniform distribution, symmetric and strictly concave. Concavity guarantees that a split never increases weighted impurity.

• Differences:

  • Scale: the binary maximum is 0.5 for Gini and 1 bit for entropy (log K for K classes vs 1 − 1/K).

  • Shape: Gini is a quadratic polynomial. Entropy has an infinite slope at p → 0, so it is more sensitive to small changes in minority classes and slightly favors more balanced splits.

  • Loss connection: entropy corresponds to log loss / KL divergence; Gini corresponds to squared loss (Brier score).

  • Cost: Gini needs no logarithms, so it is marginally cheaper to compute.

• Practical effect: the two choose different splits only rarely (empirical studies report a few percent of cases), so accuracy is usually indistinguishable.

There is no accuracy reason. Gini and entropy almost always choose the same splits. Gini is the default because it is slightly cheaper (no logarithms) and is the criterion of the original CART algorithm that scikit-learn's trees implement.

• CART heritage: scikit-learn uses an optimized CART (binary splits). Breiman et al. used the Gini index, while entropy comes from the ID3/C4.5 lineage.

• Computation:

  • Gini is just sums of squared proportions, while entropy needs a log per class per candidate split.

  • The saving is modest, but it adds up across many thresholds, features and trees in ensembles.

• Nearly identical results: Gini is a first-order approximation of entropy. Both are concave, zero at purity and maximal at uniform, so they rank splits almost the same way.

• Switching is trivial: Use criterion="entropy" or "log_loss". Treat the criterion as a hyperparameter if you like, but expect small differences: depth and leaf-size limits matter far more.

MSE splits minimize squared error around each child's mean. MAE splits minimize absolute error around each child's median. MSE is fast but sensitive to outliers; MAE is robust to outliers but much slower to compute.

• MSE (criterion="squared_error"):

  • Impurity is the variance of the node; the leaf predicts the mean.

  • Squaring makes large residuals dominate, so a few outliers can drive split choices and pull leaf values.

  • Efficient: running sums of y and y² update each candidate threshold in O(1).

• MAE (criterion="absolute_error"):

  • Impurity is the mean absolute deviation from the median; the leaf predicts the median.

  • Errors count linearly, so it is robust to outliers and heavy-tailed targets.

  • Slow: medians cannot be updated from running sums, so each threshold needs order-statistic bookkeeping. This is noticeably slower in scikit-learn on large data.

• When to choose which:

  • MSE is the default for clean data, or when you care about the conditional mean.

  • MAE suits noisy targets with outliers, or when the evaluation metric is MAE.

  • Common middle ground: clip or log-transform the target, or use a Huber loss in gradient boosting.

C4.5 is Quinlan's successor to ID3: the key change is splitting on gain ratio instead of raw information gain, plus native handling of continuous features, missing values, and post-pruning.

• Split criterion:

  • ID3 uses information gain, which is biased toward attributes with many distinct values (e.g. an ID column gives near-perfect gain but no generalization).

  • C4.5 divides gain by split information (the entropy of the partition itself), penalizing high-cardinality splits.

• Continuous features:

  • ID3 handles only categorical attributes (continuous ones must be pre-binned).

  • C4.5 finds a binary threshold split (x ≤ t) on numeric attributes.

• Missing values: C4.5 computes gain on known values and sends instances with missing values down all branches with fractional weights.

• Pruning:

  • ID3 grows the tree until leaves are pure, so it overfits easily.

  • C4.5 applies error-based (pessimistic) post-pruning and can convert trees to rule sets.

Both grow trees greedily, but C4.5 uses entropy-based gain ratio with multiway splits on categoricals, while CART uses Gini (or MSE for regression) with strictly binary splits and cost-complexity pruning.

• Split criterion:

  • C4.5: gain ratio (information gain normalized by split information).

  • CART: Gini impurity for classification, squared error (variance reduction) for regression.

• Split shape:

  • C4.5: one branch per category value (multiway); binary thresholds for numerics.

  • CART: always binary, including grouping categories into two subsets.

• Task support: C4.5 is classification only; CART (Classification And Regression Trees) does both.

• Pruning:

  • C4.5: error-based pessimistic pruning estimated from training data.

  • CART: cost-complexity pruning (penalty α × number of leaves), with α chosen by cross-validation.

• Missing values: C4.5: fractional instance weights across branches; CART: surrogate splits that mimic the primary split.

It sorts the feature's values, treats midpoints between consecutive distinct values as candidate thresholds, and picks the one with the largest impurity reduction: a single sweep with running class counts makes this O(n log n) per feature.

• Algorithm (per feature, per node):

  1. Sort samples by the feature value.

  2. Sweep left to right, moving one sample at a time from the right child to the left, updating class counts (or sums and sums of squares for regression) incrementally.

  3. At each boundary between distinct values, compute weighted child impurity (Gini, entropy, or MSE) in O(1).

  4. Keep the threshold with the best gain; scikit-learn uses the midpoint between the two values.

• Shortcuts:

  • Only boundaries where the class label changes can be optimal for entropy/Gini (Fayyad & Irani), so others can be skipped.

  • Histogram-based methods (LightGBM, HistGradientBoosting) bin values into ~255 buckets and test only bin edges, giving O(bins) per feature.

• The best threshold across all features is chosen greedily; the process recurses on each child.

Each split tests a single feature, so every boundary segment is parallel to an axis; a diagonal boundary like x₁ > x₂ can only be approximated by a staircase of many small splits, requiring deep trees and lots of data.

• Why the staircase is costly:

  • Approximation error shrinks only as the number of steps (leaves) grows, so accuracy needs depth.

  • Each step needs enough samples nearby to be placed correctly; deeper splits see fewer samples, raising variance and overfitting.

  • Greedy splitting may find little gain from any single axis split, since a diagonal boundary is a joint function of features.

• Remedies:

  • Feature engineering: add x₁ − x₂ or ratios so one split captures the boundary.

  • Rotate the space (PCA) or use oblique trees that split on linear combinations.

  • Ensembles (random forests, boosting) average many staircases into a smoother boundary.

  • Or use a linear model if the boundary is genuinely linear.

With severe imbalance, impurity is already low at the root, so splits that isolate the minority class yield only tiny impurity reductions. The greedy search then tends to favor splits that tidy up the majority class, and leaves end up predicting the majority almost everywhere.

• Impurity is dominated by the majority class:

  • Binary Gini is 2p(1−p). At p = 0.01 the parent Gini is about 0.02, so even a perfect minority split has little absolute gain to offer.

  • Weighted child impurity is driven by large majority-heavy children, so gains mostly reflect majority-class reshuffling.

• Consequences for the tree:

  • Minority-rich regions are small, so stopping rules (min_samples_leaf, max_depth) often stop before they are carved out.

  • Most leaves have a majority-class plurality, so hard predictions look accurate but recall on the minority class is poor.

  • Entropy is slightly more sensitive to rare classes than Gini, but neither fixes the problem.

• Remedies:

  1. Class weights (class_weight='balanced'): sample weights enter the impurity calculation, so minority samples count more when choosing splits.

  2. Resampling: oversample the minority class (e.g. SMOTE) or undersample the majority class.

  3. Skew-insensitive criteria such as Hellinger distance.

  4. Tune the decision threshold on predict_proba and evaluate with PR-AUC or recall rather than accuracy.

With splitter='best', each candidate feature is searched exhaustively for its optimal threshold. With splitter='random', one random threshold is drawn per candidate feature, and the best of those random splits is chosen. The random version is faster and gives higher-variance trees that individually overfit less.

• splitter='best':

  • For each feature considered (limited by max_features), it sorts the values and evaluates every midpoint threshold, then picks the split with the highest impurity decrease.

  • This is the classic greedy CART behavior and the default.

• splitter='random':

  • For each considered feature, it draws a threshold uniformly between that feature's min and max in the node.

  • It still selects the best among these random candidates, so the split is not chosen purely at random.

  • It skips the exhaustive threshold scan, which makes training faster.

• Bias–variance effect:

  • Random thresholds add bias but decorrelate trees, which is ideal for averaging.

  • This is the mechanism behind ExtraTreeClassifier and ExtraTreesClassifier (Extremely Randomized Trees).

• Note: even with 'best', features are visited in random order, so ties can depend on random_state.

Splits depend only on the ordering of feature values, not their magnitude. An extreme value simply lands on one side of a threshold, just like any other large value, so it cannot drag the model the way it would in a distance-based or linear model.

• Threshold logic:

  • The rule x <= 50 treats 100 and 1,000,000 identically, so the outlier's distance from the rest is irrelevant.

  • Candidate thresholds are midpoints between sorted neighbors. An outlier adds at most one extra candidate, and that split rarely wins on impurity.

• No magnitude-sensitive computation:

  • Trees compute no coefficients, gradients, or distances on features, so an outlier exerts no leverage.

  • Trees are invariant to monotonic transformations (log, rank, scaling), so no feature scaling is needed.

• Caveats:

  • Outliers in the target are not harmless. Under MSE, a single extreme y shifts leaf means and can attract splits that isolate it. Consider criterion='absolute_error' or a Huber loss in boosting.

  • Deep trees can still carve a tiny leaf around an anomalous point. min_samples_leaf or pruning limits this.

A regression tree is a piecewise-constant function, and each leaf predicts the mean of its training targets. Any input beyond the training range falls into an edge leaf and gets that leaf's constant. Predictions can therefore never exceed the minimum or maximum target seen in training.

• Mechanism:

  • The outermost split (e.g. x > 9.5) has an open-ended region. Whether x = 10 or x = 1000, the prediction is the same.

  • Each leaf value is an average of observed y values, so outputs are bounded by [min(y), max(y)].

• Where it bites:

  • Trending time series (sales, prices) forecast as a flat line beyond the last observed level.

  • Random forests and gradient boosting share the limitation, since sums or averages of bounded constants stay bounded.

• Remedies:

  • Detrend or difference the target and model the residuals or changes with the tree.

  • Use linear models in the leaves: M5 model trees or LightGBM linear_tree=True.

  • Combine a linear model for the trend with a tree for the nonlinear residual.

The surface is piecewise constant, like a staircase. Feature space is divided into axis-aligned hyperrectangles, one per leaf, and each region predicts one flat value.

• Structure:

  • With one feature, the surface is a step function with at most (leaves − 1) jumps.

  • With two features, it looks like a set of flat "plateaus" on rectangular bases.

  • Region boundaries are always perpendicular to a feature axis, because each split tests a single feature.

• Implications:

  • The surface is discontinuous at split thresholds and has zero gradient everywhere else.

  • Smooth or linear trends get approximated by many small steps, so a deep tree is needed and overfitting risk rises.

  • Diagonal relationships produce jagged, staircase-shaped boundaries.

  • Beyond the range of the training data, the prediction stays flat at the edge leaf's value, so there is no extrapolation.

• Ensembles (random forests, boosting) average many step functions. The result is smoother, but still piecewise constant.

The two parameters constrain different nodes. min_samples_split sets the minimum number of samples a node needs before a split is even considered. min_samples_leaf sets the minimum number of samples each resulting child must contain, so a split is rejected if either side would be too small.

• min_samples_split acts on the parent:

  • A node with fewer samples than the threshold automatically becomes a leaf.

  • It says nothing about the children: with a value of 10, a node of 10 samples can still split 9/1.

• min_samples_leaf acts on the children:

  • It guarantees that every leaf rests on at least that many samples.

  • This blocks lopsided splits that peel off a handful of outliers.

  • It implicitly requires a node to have at least 2 × min_samples_leaf samples before it can split, so it usually subsumes min_samples_split.

• Practical notes:

  • Both accept an int (a count) or a float (a fraction of the training set).

  • min_samples_leaf is generally the more effective regularizer: it smooths regression outputs and makes probability estimates more reliable.

Trees are built greedily and hierarchically. A tiny change in the data can flip which split is "best" at a node, and because every later split depends on that choice, the whole subtree below it can change. This makes trees high-variance models.

• Near-ties at split selection:

  • Several feature/threshold pairs often have almost identical impurity reduction.

  • Adding, removing, or nudging a few points can change which one wins.

• Errors cascade:

  • A different root split sends different subsets of data down each branch.

  • Every descendant node is then fit on different data, so the final tree can look completely different.

  • Greedy growth never revisits earlier choices to correct this.

• Hard thresholds: Points near a split boundary can switch leaves, causing abrupt jumps in prediction.

• Deep trees fit noise: Low bias but high variance: the structure reflects sample-specific quirks rather than the true signal.

• Mitigations:

  • Prune, or limit growth with max_depth and min_samples_leaf.

  • Better still, average many trees (bagging, random forests). This exploits the instability: decorrelated trees average out to much lower variance.

It is a pre-pruning threshold: a node is split only if the split reduces impurity by at least this amount. The reduction is weighted by the fraction of samples reaching the node, so splits that help only a tiny part of the data are penalized.

• Formula in scikit-learn:

  • The weighted decrease is (N_t / N) × (impurity − (N_tR / N_t) × right_impurity − (N_tL / N_t) × left_impurity).

  • N is the total number of samples, N_t is the number at the node, and N_tL and N_tR are the numbers in the left and right children.

  • Because of the N_t / N factor, deep nodes with few samples rarely clear the bar.

• Effect:

  • The default of 0.0 allows any split that does not increase impurity.

  • Larger values produce smaller trees and lower variance, and stop growth that only chases noise.

  • The meaningful scale depends on the criterion (Gini, entropy, MSE), so tune it with cross-validation.

• Caveat: early stopping is greedy:

  • A split with little gain on its own can enable very useful splits below it. XOR-like patterns are the classic case.

  • A threshold blocks such splits, whereas post-pruning (ccp_alpha) evaluates whole subtrees and avoids this.

max_depth caps how long any root-to-leaf path can be, which limits the tree uniformly. max_leaf_nodes caps the total number of leaves and, in scikit-learn, switches growth to best-first. That spends the leaf budget wherever it most reduces impurity, which can produce deep, unbalanced trees.

• max_depth:

  • It is a symmetric constraint: every branch stops at depth d, allowing up to 2^d leaves.

  • It limits how many features can interact along one path, to at most d.

  • It may waste capacity splitting uninformative regions while cutting off informative ones.

• max_leaf_nodes:

  • Nodes are expanded in order of greatest impurity reduction until the leaf budget runs out.

  • Complex regions can grow deep while simple regions stay shallow.

  • It controls model size directly: the number of distinct predictions equals the number of leaves.

  • This is the same idea as num_leaves with leaf-wise growth in LightGBM.

• Using them together:

  • Both can be set, and growth stops at whichever limit is hit first.

  • A common pattern is to use max_leaf_nodes for capacity and max_depth as a safety cap against very deep, narrow branches that overfit.

No. If two training rows have identical feature values but different labels, no split can separate them, so they always land in the same leaf. That leaf predicts one class and misclassifies the others. The best achievable training accuracy is the Bayes-optimal accuracy on the training set: each group of duplicates is assigned its majority label.

• Why splits can't help:

  • Every split is a test on feature values (e.g. x_j <= t). Identical rows always take the same branch.

  • The tree stops at that leaf because its impurity cannot be reduced further, even though it is not zero.

• Maximum training accuracy:

  • For each group of identical inputs, predict the majority label. Errors equal the sum of minority counts across those groups.

  • Example: 3 copies labelled A and 2 labelled B means at least 2 errors on those 5 rows.

• Practical implications:

  • Conflicting labels signal label noise or missing features. Collecting more informative features is the only way to separate these rows.

  • The leaf's class proportions (e.g. 0.6/0.4) are an honest probability estimate for that input region.

Raising min_samples_leaf forces every leaf to contain more training samples. The result is fewer, larger leaves: the prediction function becomes coarser and smoother, and probability estimates become less extreme and more stable. The trade-off is lower variance for higher bias.

• Smoother predictions:

  • Fewer splits are allowed, so the step function has fewer, wider steps. In regression, each leaf mean averages more points and is less sensitive to outliers.

  • Splits that would isolate a few points are disallowed. This removes the tiny "islands" that fit noise.

• Better probability estimates:

  • With 1-sample leaves, predict_proba returns only 0 or 1, which is overconfident and poorly calibrated.

  • With leaves of, say, 50 samples, the class proportions are smoother (e.g. 0.72), take more distinct values, and give better ranking (AUC) and calibration.

• Cost of setting it too high: The model underfits: real structure and small minority-class regions get merged away, and probabilities drift toward the overall base rate.

• Tuning: Choose it by cross-validation. A float value is treated as a fraction of the training set, which scales with dataset size.

Reduced-error pruning (Quinlan) is a post-pruning method that uses a separate validation set. It repeatedly replaces an internal node with a leaf whenever doing so does not increase validation error, and stops when no such replacement remains.

• Algorithm:

  1. Split the data into a training set and a pruning (validation) set, then grow a full tree on the training set.

  2. For each internal node, consider collapsing its subtree into a leaf that predicts the majority training class at that node.

  3. Measure validation error with and without the collapse. Prune if error does not get worse, usually choosing the prune with the biggest improvement first.

  4. Repeat until every remaining prune would hurt validation accuracy. Implementations often process nodes bottom-up.

• Strengths:

  • Simple and fast (linear in tree size with a bottom-up pass).

  • Gives the smallest subtree that is most accurate on the pruning set.

• Weaknesses:

  • It sacrifices training data for validation, which hurts on small datasets.

  • It can overfit the pruning set and tends to over-prune when that set is small. Rare-class branches are especially at risk.

  • Cost-complexity pruning with cross-validation avoids holding data out permanently.

Alpha is chosen empirically, usually by cross-validation. First compute the finite set of effective alphas at which the pruned tree changes (the pruning path). Then evaluate the subtree for each alpha on held-out folds and pick the alpha with the best validation score, or the largest alpha within one standard error of the best.

• Why only a finite set of candidates:

  • As alpha increases, weakest-link pruning yields a nested sequence of subtrees. The optimal tree changes only at specific breakpoint alphas.

  • In scikit-learn, cost_complexity_pruning_path() returns these ccp_alphas.

• Selection procedure:

  1. Get candidate alphas from the full tree trained on the training data.

  2. For each alpha, fit DecisionTreeClassifier(ccp_alpha=a) and score it with k-fold CV, or on a validation set.

  3. Choose the best alpha, then refit on all the training data.

• The 1-SE rule (from CART, Breiman et al.): Pick the simplest tree, meaning the largest alpha, whose CV error is within one standard error of the minimum. This favors smaller, more stable trees.

• Interpretation: Alpha = 0 gives the full tree. Larger alpha prunes more aggressively, and the largest alpha leaves only the root.

Mean decrease in impurity (MDI) sums, for each feature, the weighted impurity reduction at every node that splits on it. It then normalizes these totals so all importances add up to 1.

• Per-node gain:

  • For a node t with N_t samples split into L and R: ΔI(t) = (N_t / N) · [ I(t) − (N_L/N_t)·I(L) − (N_R/N_t)·I(R) ].

  • I is Gini or entropy for classification, and variance (MSE) for regression. N is the total training samples, so nodes that see more data count more.

• Aggregate per feature:

  1. Sum ΔI(t) over all nodes whose split feature is j.

  2. Divide by the sum across all features to normalize.

  3. In a forest, average these per-tree values across trees.

• In scikit-learn this is feature_importances_.

• Caveats:

  • It is computed on training data, so it reflects what the tree used. That is not necessarily what generalizes, and overfit splits inflate it.

  • It is biased toward high-cardinality or continuous features, because they offer more candidate thresholds.

  • Correlated features split the credit between them unpredictably.

  • Cross-check with permutation importance on held-out data (sklearn.inspection.permutation_importance).

A tree surrogate is a shallow, interpretable decision tree trained to mimic a black-box model. It is fit to the black box's predictions, not the true labels, so its rules approximate how the complex model behaves.

• How to build one:

  1. Run the black box on a dataset (training data or sampled inputs) to get predictions ŷ.

  2. Fit a depth-limited tree on (X, ŷ).

  3. Measure fidelity: agreement with ŷ on held-out data (accuracy, or R² for regression).

• Global vs local:

  • A global surrogate explains the model across the whole input space.

  • Local surrogates (e.g. LIME-style) fit only around one instance.

• Caveats:

  • It explains the model, not the data. A high-fidelity surrogate of a biased model is still biased.

  • Low fidelity means the explanation is misleading. Fidelity can also vary by region, so check it per segment.

  • There is a trade-off: deeper trees are more faithful but less readable.

• Don't confuse it with CART "surrogate splits": Those are backup splits on other features that mimic the primary split. CART uses them to route samples whose primary feature is missing.

Start at the root and, at each node, compare the sample's value for that node's feature with the threshold. Go left if it is ≤ the threshold, otherwise right, until you reach a leaf. The visited nodes and their conditions form the decision path.

• scikit-learn helpers:

  • clf.decision_path(X) returns a sparse node-indicator matrix (row i marks the nodes sample i visited).

  • clf.apply(X) returns the leaf id each sample lands in.

  • Combine them with tree_.feature and tree_.threshold to print each condition along with the actual feature value.

• Beyond the path: per-feature contributions:

  • Attribute the change in node value at each step to the feature that was split on. The prediction then equals the root mean plus the sum of these contributions (the treeinterpreter idea).

  • SHAP's TreeExplainer gives a more principled attribution.

Without surrogates, the tree needs some fixed rule for sending a missing value down a branch. Common options are a learned default direction, the majority child, fractional routing down every branch, or imputing the value before prediction.

• Learned default direction:

  • During training, each node records which side missing values should go to, chosen by gain (XGBoost, LightGBM, scikit-learn ≥ 1.3).

  • At inference, a missing value simply follows that stored direction.

• Majority child:

  • Send the sample to the child that received the most training samples.

  • scikit-learn does this when a feature had no missing values during training.

• Fractional routing (C4.5 style):

  • Send the sample down every branch, weighting each branch by its share of the training samples.

  • Combine the leaf predictions as a weighted average, which yields a probability distribution.

  • This is more robust than a hard choice, but the cost grows with the number of missing features.

• Impute before predicting:

  • Fill in the training mean, median, or mode, or a model-based estimate.

  • Always use statistics fitted on the training data, never on the test data.

  • Optionally add a binary is_missing indicator feature, so the tree can learn from missingness itself.

• Key principle: treat missing values at inference the same way they were treated in training. A mismatch shifts the input distribution the model sees, which causes skew between training and serving.

Misclassification error is too insensitive for growing trees: it only depends on the majority class, so splits that make nodes much purer often show zero or equal improvement. Gini and entropy are strictly concave, so they reward any increase in purity.

• Error is piecewise linear, not strictly concave:

  • Error = 1 − max_k p_k. If both children keep the same majority class as the parent, the weighted error doesn't drop at all, even if one child became much purer.

  • Strictly concave measures guarantee the weighted child impurity is lower than the parent whenever child distributions differ.

• Worked example (parent 400/400, error 0.25 after either split):

  • Split A: (300/100) and (100/300). Error 0.25, weighted Gini 0.375.

  • Split B: (200/400) and (200/0). Error 0.25, weighted Gini ≈ 0.333.

  • Error sees a tie; Gini prefers B because it creates a pure node that needs no further splitting.

• Consequences for greedy growth:

  • Ties and zero-gain splits can stop growth early, missing splits that enable good later splits.

  • Not differentiable, which makes it a poor fit for optimization.

• Where it is still used: evaluating and pruning a finished tree, since final accuracy is what you care about there.