A decision tree is a supervised learning model that predicts an outcome by passing each example through a hierarchy of if-then tests on its features, ending in a leaf that holds a class label or a numeric value. Machine learning practitioners call the variant that predicts categories a classification tree and the variant that predicts numbers a regression tree; together they are often grouped under the name CART.
Decision trees matter for two reasons. They are among the most interpretable models in machine learning, because a single prediction can be traced as a readable path of conditions. They are also the building block of the strongest tabular methods, including random forest and gradient boosting, which combine hundreds or thousands of trees.
How a decision tree splits the data
A decision tree is built by recursive binary partitioning: the algorithm searches every feature and candidate threshold, chooses the split that best separates the target, and then repeats the search independently inside each resulting subset. The process is greedy, which means each split is optimal only locally and the algorithm never revisits earlier choices.
Each internal node stores one test, such as “income below 42,000” or “color is red”. Each leaf node stores the prediction: the majority class (or class proportions) for classification and the mean of the training targets for regression. Prediction cost is proportional to tree depth, so a balanced tree with depth 10 needs at most ten comparisons per example.
The quality of a split is measured by how much it reduces node impurity. The table below lists the criteria used in common implementations.
| Criterion | Task | What it measures |
|---|---|---|
| Gini impurity | Classification | Probability of mislabeling a random sample drawn from the node |
| Entropy (information gain) | Classification | Reduction in uncertainty, in bits, after the split |
| Gain ratio | Classification | Information gain normalized by split size, used in C4.5 |
| Mean squared error | Regression | Variance of targets around the leaf mean |
| Mean absolute error | Regression | Deviation around the leaf median, more robust to outliers |
In practice Gini impurity and entropy produce very similar trees; Gini is slightly cheaper to compute because it avoids logarithms, which is why it is the default in many libraries.
Main decision tree algorithms
Several classic induction algorithms define how trees are grown, which split types they allow and how they handle missing data. Most modern software follows the CART approach with binary splits, but the older families still appear in literature and in some statistical tools.
| Algorithm | Split type | Distinctive feature |
|---|---|---|
| ID3 | Multiway on categorical features | Uses information gain; no pruning or numeric thresholds |
| C4.5 and C5.0 | Multiway and numeric thresholds | Gain ratio, pruning and handling of missing values |
| CART | Binary only | Gini or squared error, cost-complexity pruning, surrogate splits |
| CHAID | Multiway | Chi-square significance tests, popular in market segmentation |
| Conditional inference trees | Binary | Permutation tests that reduce bias toward many-valued features |
The choice of algorithm matters less than the stopping and pruning settings, because those decide whether the final tree generalizes or memorizes the training data.
Controlling depth, overfitting and pruning
An unrestricted decision tree keeps splitting until every leaf is pure, which typically yields near-zero training error and poor test accuracy. This is the classic high-variance side of the bias-variance tradeoff: small changes in the training data can produce a completely different tree.
Two strategies limit this. Pre-pruning stops growth early through hyperparameters, while post-pruning grows a large tree and then removes branches that do not improve validation performance. CART uses cost-complexity pruning, which adds a penalty alpha per leaf and selects alpha by cross-validation.
| Hyperparameter | Typical range | Effect when increased |
|---|---|---|
| Maximum depth | 3 to 20 | More complex boundaries, higher overfitting risk |
| Minimum samples per leaf | 1 to 100 or 0.5% to 5% of rows | Smoother predictions, less variance |
| Minimum samples to split | 2 to 200 | Fewer splits on small subsets |
| Maximum number of leaves | 8 to 1,000 | Caps total model size directly |
| Cost-complexity alpha | 0 to about 0.05 | Stronger pruning, simpler tree |
A practical rule is to tune minimum samples per leaf first, because it controls leaf reliability directly, and then tune depth or alpha with cross-validation rather than by inspection.
Decision trees compared with related models
A single decision tree trades accuracy for transparency, and its neighbors in machine learning resolve that trade-off differently. The comparison below shows where the single tree fits among common tabular models.
| Model | Interpretability | Typical accuracy on tabular data | Main weakness |
|---|---|---|---|
| Single decision tree | Very high | Moderate | High variance, unstable structure |
| Random forest | Low to moderate | High | Large model, slower prediction |
| Gradient boosting | Low | Usually highest | Sensitive to tuning, can overfit |
| Logistic regression | High | Moderate | Needs manual interactions and nonlinearity |
| k-nearest neighbors | Moderate | Moderate | Requires feature scaling, slow at query time |
Trees capture feature interactions and nonlinear effects automatically, and they need no feature scaling, because a threshold test is unaffected by monotonic transformations. Their decision boundary, however, is made of axis-aligned rectangles, so a diagonal boundary requires many small steps.
Limitations and common mistakes
Most problems with decision trees come from instability, bias in split selection and misleading importance scores. The following points summarize what experienced practitioners watch for.
- Instability: removing a few rows can change the root split and therefore the entire tree, so a single tree should not be treated as a stable description of the data.
- Bias toward many-valued features: impurity-based criteria favor features with many distinct values, such as identifiers, which can create spurious splits.
- Impurity-based feature importance inherits that bias; permutation importance is a more reliable check.
- Poor extrapolation: a regression tree predicts a constant beyond the range of the training data, so it cannot follow a trend.
- Class imbalance: without class weights, leaves tend to predict the majority class and minority recall suffers.
A frequent mistake is to report the accuracy of a fully grown tree evaluated on its own training data, which overstates performance. Always evaluate on held-out data and inspect the depth of the selected model.
A non-technical view
A decision tree works like a game of twenty questions. To decide whether a loan application looks risky, it might first ask whether the income is above a certain level, then whether there were late payments, then how long the person has held the job. Each answer sends the case down a different branch until it reaches a final verdict.
The computer learns which questions to ask, and in which order, by studying many past examples. The key takeaway is simple: a decision tree is easy to read and explain, but a tree that asks too many questions starts memorizing old cases instead of learning general rules.
A concrete example
A regional telecom operator wants to predict which subscribers will cancel their contracts in the next quarter. The analytics team has 120,000 customer records with features such as contract type, monthly charge, number of support calls and tenure in months.
The team trains a classification tree with maximum depth 5 and at least 200 customers per leaf. The root split is contract type, followed by support calls above three and tenure below eight months. The resulting tree reaches slightly lower accuracy than a gradient boosting model on the test set, but it produces a dozen readable rules that the retention department can apply directly.
The outcome is a two-model setup: the boosted model scores customers, while the shallow decision tree explains the main churn segments to managers and guides the design of targeted retention offers.