How does a CART decision tree choose which feature and threshold to split a node on?
answer
- try everything, keep the best
- children counted by size, not equally
- parent impurity minus weighted children
- midpoints between sorted distinct values
- decision is final, then recurse
basics
~20 sA CART tree scores every candidate split - each feature crossed with each candidate cut point - by the sample-weighted impurity of the two children it would create, then keeps the single split with the largest impurity drop and recurses.
solid answer
~40 sGrowth is greedy and node-local. At a node, the learner enumerates candidate splits: for each feature it sorts the distinct values and tests the midpoints between consecutive ones, giving at most `n - 1` cut points per feature. Each candidate is scored by the impurity of the resulting children, weighted by the fraction of the node's rows that fall into each: `score = (n_L/n)*I(left) + (n_R/n)*I(right)`, where `I` is Gini for classification or within-node variance for regression. The gain is `I(parent) - score`, and the split with the largest gain wins. The chosen split is then final - the learner never revisits it - and the same procedure repeats independently inside each child until a stopping rule fires. The size weighting is what stops a tiny pure child from buying a bad split.
code
python · 24 linesrows = [(1.0, 0), (2.0, 0), (3.0, 1), (4.0, 0), (5.0, 1), (6.0, 1)]
def gini(labels):
n = len(labels)
if n == 0:
return 0.0
p = sum(labels) / n
return 1 - p ** 2 - (1 - p) ** 2
parent = gini([y for _, y in rows])
values = sorted({x for x, _ in rows})
best = None
for a, b in zip(values, values[1:]):
t = (a + b) / 2
left = [y for x, y in rows if x <= t]
right = [y for x, y in rows if x > t]
n = len(left) + len(right)
score = len(left) / n * gini(left) + len(right) / n * gini(right)
if best is None or score < best[1]:
best = (t, score)
print("parent impurity:", parent)
print("best threshold:", best[0], "weighted child impurity:", best[1])
print("gain:", parent - best[1])go deeper
Be ready to say in one breath that the tree tries every feature and every cut point, measures how mixed the two resulting groups are, and keeps the cut that leaves them cleanest.
You are expected to write the scoring formula: parent impurity minus the size-weighted average of the children's impurity, and to explain that continuous features are cut at midpoints between sorted distinct values.
Show you know the cost and the consequences: sort once and sweep, ties broken arbitrarily, the decision at each node is never revisited, and categorical features with many levels need a shortcut or they blow up the candidate set.
Own the tradeoff between search quality and training cost. Argue when an exhaustive per-node scan is worth it, when binned or subsampled candidate thresholds are the right economy, and what that approximation costs you in split quality.
## The problem a split solves A decision tree carves the feature space into rectangular regions by asking one yes/no question at a time. At any node you hold a set of training rows; you want to replace that set with two subsets that are each *more homogeneous* in the target than the parent was. "Choosing a split" means choosing a **feature** and a **cut point** on that feature that best achieves this, under some numeric definition of homogeneity called an **impurity** measure. ## Impurity, and why it is weighted For classification, the usual impurity of a node is the Gini index `I = 1 - sum(p_i^2)` over class proportions `p_i` in that node (entropy `-sum(p_i * log2 p_i)` is the alternative). For regression it is the within-node variance, i.e. the mean squared deviation from the node's mean target. All of these are zero when the node is pure and rise as the node becomes mixed. A candidate split produces two children, so you need one number for the pair. CART uses the **sample-weighted** average: ``` score(split) = (n_L / n) * I(left) + (n_R / n) * I(right) gain(split) = I(parent) - score(split) ``` The weights matter enormously. Consider a node of 200 HR records where the target is whether an onboarding checklist was completed, split 120 yes / 80 no. A candidate split peels off 4 rows that are all "yes" - a perfectly pure child - and leaves 196 rows at 116/80. The pure child contributes `4/200 * 0 = 0`, but the big child contributes `196/200 * I(116/80)`, which is barely below the parent's impurity. The overall gain is tiny, and some other split that moves 90 rows into a 75%-pure child will beat it easily. An unweighted average of the two child impurities would have scored the 4-row split as a triumph. Weighting by node size is exactly what encodes "purity is only worth what it buys you in rows explained". ## Enumerating candidates **Continuous features.** Only the *ordering* of the values matters, so the learner sorts the node's distinct values `v1 < v2 < ... < vk` and considers thresholds at the midpoints `(v_j + v_{j+1})/2`. Any threshold between two consecutive distinct values yields the identical partition, so there are at most `k - 1` genuinely different splits per feature. Implementations sort once and then sweep, updating class counts incrementally, so scoring all `k - 1` candidates costs one pass after the sort rather than one full recount each. **Ordinal features** behave the same way. **Categorical features** are harder: a binary tree must split the `k` categories into two subsets, and there are `2^(k-1) - 1` non-trivial ways to do that. For two-class targets there is a classical shortcut - order the categories by the proportion of the positive class within each, then treat that ordering like a continuous feature; the best contiguous cut in that ordering is provably the best subset split. For multi-class targets no such shortcut exists in general, and learners fall back on heuristics or on one-hot-style binary questions. ## Greedy recursion Once the best split is found it is applied, and the exact same procedure runs inside each child, with that child's rows only. Nothing is reconsidered: the root's decision constrains everything below it forever. This is why the algorithm is called **greedy recursive partitioning**. It is cheap - roughly `O(features * n log n)` at the root, shrinking as nodes get smaller - and it is why trees train fast on wide tabular data. ## Consequences worth naming in an interview - **Ties.** Two features can produce identical gain; implementations break ties by feature order or at random, which is one source of run-to-run variation. - **The gain is a local score, not a global objective.** Nothing in this procedure optimises the whole tree. - **Zero gain is not the same as no signal.** A feature can be worthless at the root and decisive two levels down. - **Missing values** need a separate policy, because a row with no value for the candidate feature cannot be sent left or right by the rule alone. - **The criterion is computed on the target, not on the feature.** A common muddle is to imagine the tree ranking features by correlation or by their own spread; the impurity is always a property of the label distribution inside the candidate children. ## How to say it in ten seconds "For every feature and every cut point, compute the impurity of the two children, weight each by its share of the rows, subtract from the parent's impurity, and take the biggest drop. Then do it again inside each child."
- On a 200-row node, one candidate split makes a pure child of 4 rows and leaves 196 rows almost as mixed as the parent. Why does the tree usually reject it?Because child impurities are weighted by row share. The pure child contributes 4/200 times zero, so the score is dominated by the 196-row child, whose impurity is nearly the parent's. The gain is therefore near zero and almost any split that moves real volume into a cleaner child will outrank it. Unweighted averaging would have made the 4-row split look excellent, which is precisely why the weighting exists.
- How many thresholds does the search actually evaluate for a continuous feature?At most one fewer than the number of distinct values in that node. Values are sorted and the candidate cuts are the midpoints between consecutive distinct values, because any threshold between the same two values produces the identical partition. Implementations sort once and sweep, updating counts incrementally, so all candidates are scored in a single pass after the sort.
- How does the search change for a categorical feature with many levels?A binary tree must pick a subset of levels to send left, and there are 2^(k-1) - 1 non-trivial subsets for k levels, so brute force explodes. For a two-class target there is an exact shortcut: order the levels by the positive-class rate inside each, then scan that ordering like a continuous feature - the best contiguous cut is the best subset. Multi-class targets have no such guarantee.
Like cutting a shuffled deck of red and black cards: you try every cut position, and keep the one that leaves each half as close to single-coloured as possible - counting a half's tidiness in proportion to how many cards it holds, so a spotless three-card pile counts for almost nothing.
saying these in an interview costs you the question
- Says the tree picks the feature most correlated with the target
- Averages the two child impurities without weighting by node size
- Thinks the search optimises the whole tree, not one node
- Believes the threshold is the feature's mean or median
- Says a split is kept whenever either child gets purer