How Decision Trees Split Data

A decision tree predicting whether a loan applicant will default asks a sequence of yes-or-no questions: is income above $50,000? Is existing debt below 30% of income? Has the applicant missed a payment in the past year? Each question splits the remaining applicants into more homogeneous groups, and the tree keeps asking sharper questions until the groups at the bottom are dominated by a single outcome. The genuinely hard problem, the one that separates a working algorithm from a lucky guess, is figuring out mathematically which question to ask at each step, in what order, and when to stop asking.

That problem was solved, independently, by two research lineages in the 1980s: J. Ross Quinlan's information-theoretic ID3 and C4.5 algorithms, and Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone's statistically grounded CART framework. Both approaches are still running, in some form, inside nearly every gradient-boosted model and random forest deployed today. Understanding how they choose a split is understanding the actual engine underneath a huge share of modern applied machine learning.

Why not just ask questions in any order?

A tree could ask questions in a random order and still eventually separate defaulters from non-defaulters, given enough splits. But a randomly-ordered tree would need far more splits to reach the same separation, and every additional split increases the risk of overfitting, memorizing quirks of the training data rather than learning patterns that generalize to new applicants. If the third split down a random branch happens to isolate three training examples that all defaulted for reasons entirely unrelated to any feature the tree can see, the tree will "learn" that pattern anyway and apply it confidently to future data where it does not hold.

The algorithms behind decision trees do not ask questions in a fixed or arbitrary order. Quinlan's ID3, published in the journal Machine Learning in 1986, and its more capable successor C4.5, choose splits by measuring exactly how much each candidate question reduces uncertainty about the outcome (Quinlan, 1986). CART, described in Breiman, Friedman, Olshen, and Stone's 1984 monograph Classification and Regression Trees, arrived at a parallel solution from a different mathematical tradition, using a measure called Gini impurity instead of Shannon entropy. Both approaches converge on the same underlying idea: evaluate every possible split, quantify how much it clarifies the outcome, and greedily pick the best one.

This matters because a tree's entire "intelligence" lives in that split-selection step. There is no separate reasoning engine, no hidden logic beyond arithmetic run recursively at every branch. A decision tree is, in a very literal sense, nothing but a sequence of these split decisions stacked on top of each other.

Measuring uncertainty with entropy

Entropy — a measure, borrowed from Claude Shannon's 1948 paper "A Mathematical Theory of Communication," of how mixed or unpredictable a set of outcomes is. Quinlan's ID3 adapted Shannon's formula directly: for a group of examples split between two or more classes, entropy is calculated as the negative sum, over each class, of that class's proportion multiplied by the base-2 logarithm of that proportion.

The intuition is more useful than the formula on its own. A group that is exactly 50% defaulters and 50% non-defaulters has maximum entropy for a two-class problem, one full bit, because knowing nothing else about a random member of that group, you cannot predict their outcome better than a coin flip. A group that is 95% one outcome has low entropy, close to zero, because most members share the same label and there is very little "surprise" left in learning any individual's true class.

Entropy behaves like a formal measure of surprise. If a group is already almost entirely one outcome, learning any individual member's true label carries very little new information, so entropy is low. If a group is a perfect toss-up, every individual's label is maximally informative to learn, so entropy is high. This is exactly the same mathematical object that shows up in data compression: a message drawn from a highly predictable source compresses well because there is little entropy to transmit, and a mixed, unpredictable group of training labels is, in this framework, treated the same way.

Quinlan's original 1986 ID3 paper has been cited more than 18,000 times, according to citation-tracking aggregators, making it one of the most influential single papers in the applied machine learning canon (Semantic Scholar, citation count as of paper indexing).

It is worth being precise about what entropy is not. It is not a measure of how "important" a feature is in any human sense, and it says nothing about causation. A feature can produce low-entropy child groups purely by statistical coincidence in a small dataset, which is one reason single decision trees are notoriously unstable: change a handful of training examples and the tree that gets built can look completely different, because a different feature might edge out the previous winner at the very first split.

Information gain: choosing the best question

For every candidate split at every node, ID3 and C4.5 calculate information gain — the entropy of the parent group before the split, minus the weighted average entropy of the child groups produced by the split, where each child's weight is the proportion of examples that fall into it. A split that neatly separates defaulters from non-defaulters produces a large information gain, because the resulting child groups are much purer than the mixed parent group. A split that barely changes the mix, say, splitting applicants by whether their last name starts with a letter in the first half of the alphabet, produces information gain close to zero, because the child groups look about as mixed as the parent.

The algorithm evaluates every possible split on every available feature at the current node, computes the resulting information gain for each candidate, and picks whichever single split scores highest. It then repeats the entire process independently and recursively inside each resulting child group, treating each one as a fresh smaller dataset to be split again. This is what makes the algorithm greedy: at each step it commits fully to whichever split looks best right now, with no mechanism for looking two or three splits ahead to see if a slightly worse immediate split might set up a much better subsequent one.

Greediness is a deliberate engineering tradeoff, not an oversight. Genuinely searching every possible sequence of splits to find the globally optimal tree is an NP-hard combinatorial problem; even a modest dataset with a few dozen features has more possible tree structures than could be evaluated in the lifetime of the universe. Greedy, one-step-at-a-time selection makes tree-building fast enough to run on ordinary hardware, at the cost of sometimes settling into a locally good but globally suboptimal structure. Quinlan's C4.5, released as a successor to ID3, addressed several of ID3's practical weaknesses without abandoning the greedy core: it handled continuous-valued features by testing threshold splits rather than requiring pre-discretized categories, tolerated missing values, and introduced a normalized variant of information gain called the gain ratio, which corrected ID3's tendency to unfairly favor features with many distinct values.

Why does information gain favor features with many values?

A feature like a unique customer ID has one distinct value per row, so splitting on it produces child groups that are, trivially, 100% pure, since each group contains exactly one example. Raw information gain rewards this even though the split is useless for prediction. C4.5's gain ratio divides information gain by the intrinsic entropy of the split itself, penalizing splits that fragment the data into many tiny groups and correcting this bias (Quinlan, 1986).

Gini impurity: CART's faster alternative

Gini impurity — the probability that a randomly chosen element from a group would be mislabeled if it were randomly assigned a label according to the group's own class distribution. It is computed as one minus the sum, over each class, of that class's squared proportion in the group.

Breiman, Friedman, Olshen, and Stone's CART framework, published in book form in 1984 as Classification and Regression Trees, defaulted to Gini impurity rather than Shannon entropy, largely because it avoids logarithm computations and is therefore cheaper to evaluate at scale, a meaningful consideration in 1984 on hardware many orders of magnitude slower than anything in common use now. CART also generalized decision trees beyond classification into regression, using variance reduction as the equivalent splitting criterion for continuous numeric targets rather than discrete class labels.

In practice, entropy-based information gain and Gini impurity tend to select very similar splits on real datasets, and the empirical difference between the two criteria is usually small enough that the choice comes down to computational convenience or library defaults rather than a meaningfully different final tree. Scikit-learn, one of the most widely used machine learning libraries, defaults its DecisionTreeClassifier to Gini impurity for exactly this reason, while still offering entropy as a configurable alternative.

Splitting criterion	Formula basis	Common in	Computational cost
Information gain (entropy)	Shannon entropy, 1948	ID3, C4.5	Higher (logarithms)
Gini impurity	Probability of misclassification	CART, most modern libraries	Lower (no logarithms)
Variance reduction	Statistical variance of target	CART regression trees	Moderate

All three criteria answer the same underlying question, "how much purer are the child groups than the parent," using different arithmetic.

CART introduced a second structural difference that outlived the entropy-versus-Gini debate: it restricts every split to strictly binary, producing exactly two children per node, whereas ID3 originally allowed a categorical feature to be split into as many branches as it had distinct values. Binary splitting turned out to be the more durable design choice; nearly every modern tree-based library, including scikit-learn's implementation and the tree learners inside XGBoost and LightGBM, builds strictly binary trees regardless of which impurity measure it uses internally.

Why trees eventually need to stop growing

Left unconstrained, a decision tree can keep splitting until every leaf node contains a single training example or a group of examples that all share one label, at which point it achieves perfect accuracy on the training data. This is not a sign of a good model. It is the clearest possible symptom of overfitting — building a model so tightly fit to the training data's specific examples, including their noise and idiosyncrasies, that it fails to generalize to new, unseen data. A fully grown tree essentially memorizes a lookup table dressed up as a decision procedure.

Practical implementations counter this in several overlapping ways, most of which are exposed as configurable hyperparameters in standard libraries. Limiting maximum tree depth stops the recursive splitting after a fixed number of levels, regardless of whether further splits would technically improve training purity. Requiring a minimum number of samples per leaf, or per split, prevents the tree from carving out branches to accommodate a handful of unusual examples. Pruning — removing branches after a tree has already been fully grown, based on whether they meaningfully improve performance on data the tree was not trained on — is CART's own solution, formalized as cost-complexity pruning in Breiman and colleagues' 1984 work, which balances tree size against a penalty term for complexity and selects the subtree that performs best on held-out validation data.

The tension these techniques manage is a version of the classic bias-variance tradeoff that runs through nearly all of supervised learning. A shallow, heavily constrained tree is simple and stable but may be too crude to capture real structure in the data, a problem called underfitting. A deep, unconstrained tree captures fine-grained structure but is unstable and prone to treating noise as signal. Cross-validation, evaluating candidate depths or pruning thresholds on data withheld from training, is the standard way practitioners find the point on that tradeoff that actually generalizes best, rather than guessing at a "reasonable-sounding" depth.

How does pruning actually decide what to remove?

Cost-complexity pruning, CART's method, assigns every possible subtree a score combining its error rate on validation data with a penalty proportional to the number of leaves it contains. The algorithm compares subtrees at increasing penalty strengths and selects whichever one minimizes validation error without carrying unnecessary extra branches (Breiman et al., 1984).

Why a single split's benefit isn't always obvious upfront

Greedy, one-split-at-a-time selection has a specific, well-documented blind spot: a feature that looks weak in isolation at the root of the tree, contributing very little information gain on its own, might combine powerfully with a second feature several levels down to produce a highly predictive split, even though neither feature alone scored well at the point it was evaluated. Zip code alone might barely separate loan defaulters from non-defaulters across an entire population, but zip code combined with income, evaluated only after income has already been split on, can produce a sharply predictive subgroup. A purely greedy algorithm, evaluating each feature independently at each node without any lookahead, has no way to detect this kind of interaction in advance; it only discovers it if the feature still happens to look useful within the narrower subgroup created by the first split.

This is one of the central reasons ensemble methods — techniques that combine predictions from many individual models rather than relying on one — built from decision trees tend to outperform any single tree. Random forests, introduced by Leo Breiman in a 2001 paper building directly on his earlier CART work, construct many different decision trees, each trained on a randomly resampled subset of the training data and restricted to a random subset of features at each split, then average their predictions. Because each individual tree in the forest is exposed to a different random slice of the data and features, the trees end up disagreeing in different ways, and averaging across many different greedy, locally-blind trees smooths out the specific blind spots any single tree would have committed to. Gradient boosting frameworks such as XGBoost and LightGBM take a different route to the same underlying goal, building trees sequentially where each new tree is trained specifically to correct the errors of the ensemble built so far, but they too rely on the same core split-selection machinery, evaluating candidate splits by impurity reduction, described above.

The practical upshot is that a single decision tree remains genuinely valuable for its interpretability, a human can trace the exact sequence of questions that produced any given prediction, but production systems that need maximum predictive accuracy on complex tabular data almost always reach for an ensemble of trees rather than one tree alone.

Common misconceptions about how trees choose splits

A frequent misunderstanding is that decision trees choose splits based on which feature seems intuitively "most important" to a human analyst, weighing prior domain knowledge the way a person would. In reality, the algorithm has no concept of domain relevance at all. It mechanically calculates information gain or Gini impurity reduction for every candidate split on every available feature at every node and picks whichever number is mathematically highest, with zero regard for whether that feature makes intuitive sense to a human expert. This is precisely why decision trees can and do surface counterintuitive, spuriously predictive splits when trained on noisy or leaky data, since the algorithm cannot distinguish a genuinely causal pattern from a coincidental correlation that happens to reduce impurity in the training set.

A second common misconception is that a deeper tree is unconditionally a better tree, since it fits the training data more precisely. As covered above, deeper trees usually generalize worse, not better, to new data past a certain point, which is exactly why controlling maximum depth, minimum leaf size, and pruning are standard, necessary configuration choices in any serious deployment rather than optional refinements a practitioner can skip.

A third misconception worth flagging: that Gini impurity and entropy-based information gain produce meaningfully different trees, and that choosing between them is a consequential modeling decision. In practice, as noted above, the two criteria tend to select very similar splits on the same data, and the meaningful modeling decisions, tree depth, minimum samples per leaf, pruning strategy, and whether to use a single tree versus an ensemble, matter considerably more to final model performance than the choice of impurity measure.

Finally, some practitioners assume that because a decision tree is easy to visualize as a flowchart, it must also be simple to train correctly. The mechanics of choosing a split are straightforward arithmetic, but choosing the right stopping criteria, validating on truly held-out data, and recognizing when a single tree's instability calls for an ensemble instead are all judgment calls that require the same statistical care as any other modeling technique. The visual simplicity of the output is not a shortcut around the underlying methodology.

The takeaway

A decision tree's entire behavior traces back to one repeated calculation: at every node, measure how impure the current group of examples is using entropy or Gini impurity, test every candidate split on every available feature, and greedily commit to whichever split reduces that impurity the most. Quinlan's ID3 and C4.5 formalized the entropy-based version of this idea in the 1980s; Breiman, Friedman, Olshen, and Stone's CART formalized the Gini-based version around the same time, and both lineages remain directly embedded in the tree-building code inside modern libraries and ensemble methods like random forests and gradient boosting. The tradeoff every practitioner eventually confronts, greedy short-term splitting decisions versus long-term generalization, is managed through depth limits, minimum leaf sizes, and pruning, not by making the splitting arithmetic itself any smarter. Understanding that arithmetic is understanding what a decision tree actually is.

---

Read next:

• How random forests reduce error
• Why overfitting hurts machine learning
• What feature engineering means

FAQ

Q: How does a decision tree decide which question to ask first?

It calculates information gain (entropy-based) or Gini impurity reduction for every possible split on every available feature at the root node, then picks whichever single split reduces uncertainty about the outcome the most. It repeats this process recursively for each resulting subgroup, treating each one as a fresh dataset to split again.

Q: What is entropy in the context of decision trees?

Entropy, adapted from Claude Shannon's 1948 information theory, measures how mixed a group of outcomes is. A group split evenly between classes has high entropy, close to one bit for a two-class problem, while a group dominated by one class has low entropy near zero. ID3 and C4.5 favor splits that reduce weighted average entropy the most.

Q: What is the difference between information gain and Gini impurity?

Both measure how much a candidate split improves the purity of the resulting child groups, but information gain uses Shannon entropy and logarithms, while Gini impurity uses a computationally cheaper measure based on misclassification probability. They tend to select similar splits in practice; the choice is largely one of computational convenience.

Q: Why do decision trees need pruning?

Left unconstrained, a tree can keep splitting until every leaf contains a single training example, achieving perfect training accuracy but memorizing noise rather than learning generalizable patterns, a failure mode called overfitting. Pruning, formalized in CART as cost-complexity pruning, removes branches that do not meaningfully improve performance on held-out validation data.

Q: Who invented the algorithms behind decision trees?

Ross Quinlan published ID3 in the journal Machine Learning in 1986, later followed by the improved C4.5 algorithm, both built on Shannon-entropy-based information gain. Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone developed the competing CART framework, published in 1984, which commonly uses Gini impurity and restricts every split to two branches.

Q: Why do single decision trees often perform worse than random forests?

A single tree builds its splits greedily, one step at a time, with no ability to look ahead and detect feature combinations that only become useful several splits deep. Random forests train many trees on different random subsets of data and features, then average their predictions, which smooths out the blind spots any individual greedy tree would commit to.

Q: Can decision trees handle numeric features, not just categories?

Yes. C4.5 and CART both handle continuous numeric features by testing threshold splits, for example "is income above $50,000," treating each candidate threshold as its own binary split and evaluating the resulting information gain or Gini impurity reduction exactly as it would for a categorical feature.