How CART Scans Sorted Feature Values for the Best Split Threshold

A decision tree is built by asking the same question at every node: of all the ways to divide the data arriving at this node into two parts, which division reduces impurity the most? The question is easy to state and, in the naive form, expensive to answer. With $n$ samples at a node and $p$ features, there are roughly $n \cdot p$ distinct candidate divisions, and evaluating each one means recomputing the impurity of both children from scratch. Done literally, building one level of a tree costs $O(pn^2)$ per node, which becomes intolerable well before datasets reach a million rows.

CART, the tree algorithm described by Breiman, Friedman, Olshen and Stone, avoids the quadratic factor with two observations: candidate thresholds only exist between distinct adjacent values, and child statistics can be updated incrementally as the threshold sweeps left to right. The result is a single sort followed by a single linear pass per feature.

The candidate set is boundaries, not values

For an ordered feature, a threshold $t$ defines the split $x \le t$ versus $x > t$. Two thresholds that fall between the same pair of consecutive distinct values produce identical partitions, so the only thresholds worth considering lie in the gaps of the sorted distinct values. If a feature takes $k$ distinct values at a node, there are at most $k-1$ candidate splits. Continuous features with many duplicates collapse accordingly; a feature with one distinct value contributes no candidates at all and is effectively skipped.

This is where the sort pays for itself. Sorting the node’s rows by a feature costs $O(n \log n)$, and after sorting, the candidate thresholds are just the $k-1$ adjacent pairs. For all $p$ features the per-node cost of sorting is $O(pn\log n)$. A naive implementation that re-partitions the data for each candidate threshold instead costs $O(pn)$ per candidate and $O(pn^2)$ per feature, so the gap between the two grows with node size rather than staying constant.

The sort is usually performed once per feature at the root and then maintained as the tree grows, by passing the already-sorted index order down to each child and filtering it. Filtering preserves order, so no child ever re-sorts; the total work across a level is proportional to the data volume of that level rather than to $n \log n$ times the number of nodes.

One sweep, incremental counts

The second observation is that the impurity of the left child can be maintained as the sweep moves, because moving one sample across the boundary changes the class counts by exactly one. For a classification node with $K$ classes, keep a vector of left-side counts and the total counts. At each candidate position, move the current sample into the left vector, then evaluate both children from those counts in $O(K)$ time. Evaluating every candidate therefore costs $O(nK)$ per feature rather than $O(n^2 K)$.

The scan is written most clearly as a loop over the sorted order, tracking the running class histogram. The code below is the classification case with Gini impurity; it returns the best threshold, the impurity decrease, and the child counts needed to recurse.

def best_split_gini(X, y, n_classes):
    n = len(y)
    total = [0] * n_classes
    for label in y:
        total[label] += 1

    parent = 1.0 - sum((c / n) ** 2 for c in total)
    left = [0] * n_classes
    best = (0.0, None)          # (decrease, threshold)

    for i in range(n - 1):
        left[y[i]] += 1
        # Only boundaries between distinct values are candidates.
        if X[i] == X[i + 1]:
            continue
        nl = i + 1
        nr = n - nl
        gl = 1.0 - sum((c / nl) ** 2 for c in left)
        gr = 1.0 - sum(((total[k] - left[k]) / nr) ** 2 for k in range(n_classes))
        decrease = parent - (nl / n) * gl - (nr / n) * gr
        if decrease > best[0]:
            best = (decrease, (X[i] + X[i + 1]) / 2.0)
    return best

The child impurities are weighted by the fraction of samples they receive. That weighting matters: without it, a split that isolates a single sample would look excellent by unweighted impurity, since a one-element node has zero impurity by construction. The weighted form is what makes the criterion compare partitions rather than node sizes.

The same scan for regression

For squared-error regression the target constant at a leaf is the mean, and the impurity is the sum of squared deviations from that mean. The decrease in squared error from a split has a compact form that needs only sums and sums of squares, not a per-candidate loop over the right child:

$$ \Delta = \frac{S_L^2}{n_L} + \frac{S_R^2}{n_R} - \frac{S^2}{n} $$

where $S_L$, $S_R$ and $S$ are the sums of the target over the left child, the right child and the parent. Maximizing $\Delta$ is equivalent to maximizing the between-group sum of squares, so the scan maintains a running sum and updates it with one addition per sample. This is why regression trees can use the identical sorted-sweep machinery as classification trees: only the accumulator changes.

The equivalence also exposes a property that later stages depend on. Because the criterion is a variance decomposition, it is invariant to adding a constant to the target and scales quadratically with a multiplicative rescaling. A tree fitted to $y$ and a tree fitted to $ay + b$ have the same structure. Gradient boosting exploits this when it fits trees to residuals rather than to raw labels.

Duplicates, ties, and unordered features

Duplicates are the common practical hazard. If a feature has many repeated values, the number of distinct boundaries can be far smaller than $n$, and a scan that evaluates every index wastes time recomputing the same partition. Skipping indices where the value does not change, as in the loop above, costs one comparison per sample and removes the waste entirely. It also removes a subtler bug: without the skip, a threshold can be placed between two equal values, producing a partition that no future sample can ever satisfy consistently.

Ties in impurity decrease are resolved arbitrarily by most implementations, typically by taking the first candidate in feature order. The consequence is that two runs over permuted columns can produce different trees with nearly identical accuracy. Determinism requires fixing both the feature order and the candidate order, which is why libraries expose a random seed even for a single tree.

Unordered categorical features break the sorted sweep, since there is no natural order to scan. CART handles a categorical feature with $L$ levels by considering all $2^{L-1}-1$ binary partitions, which is exponential; for binary targets the optimal partition can be found by sorting levels by their proportion of the positive class, recovering a linear scan. Multiclass targets have no such reduction in general, which is the reason many implementations either forbid high-cardinality categorical splits or encode them as one-vs-rest binary columns.

What greedy selection costs

Every threshold is chosen to minimize impurity at one node, with no regard for the tree that follows. A split that looks weak locally can enable a strong split one level down, and a split that looks strong can consume the samples a better split would have needed. CART accepts this myopia because the alternative, searching over tree structures, is combinatorial. The practical mitigation is to grow past the point of usefulness and prune afterwards, which is exactly what the weakest-link pruning procedure does; cost-complexity pruning describes how the sequence of subtrees is generated.

The impurity measure itself is not neutral either. Gini and entropy produce different rankings of candidate splits on the same data, and the choice interacts with how the tree is later pruned. The comparison of the two, and the reason a third common criterion cannot be used for growth at all, is covered in Gini, entropy, and the misclassification trap.

One more cost is worth naming because it dominates at scale. The scan is linear in samples but the sort is not, and a deep tree sorts the same feature repeatedly at successive nodes. Histogram-based variants replace the exact sort with a fixed number of bins computed once per feature, trading threshold precision for a large constant-factor win; that trade is the subject of histogram split finding.