---
source: 'https://howaiworks.ai/glossary/decision-trees'
section: glossary
title: Decision Trees (DT)
description: >-
  How a decision tree actually chooses each split: Gini impurity worked by hand,
  why depth drives overfitting, and what a single tree cannot represent.
tags:
  - decision trees
  - Machine Learning
  - classification
  - regression
  - supervised learning
  - tree-based models
  - Interpretability
category: Machine Learning
datePublished: '2025-08-17'
lastUpdated: '2026-07-22'
---

# Decision Trees (DT)

> How a decision tree actually chooses each split: Gini impurity worked by hand, why depth drives overfitting, and what a single tree cannot represent.

## Definition

A decision tree is a [supervised learning](https://howaiworks.ai/glossary/supervised-learning) model that predicts by
asking a sequence of yes/no questions about the input — "prior default? income above $51,500?" —
until it reaches a leaf that holds an answer. The structure is obvious. The only non-obvious part,
and the thing worth reading a page about, is **how the tree chooses each question**, because nobody
writes those questions down. The algorithm invents them by brute force: at every node it enumerates
every feature and every threshold, scores each candidate split by how much it reduces the *mixing*
of the labels, and keeps the winner.

That score has a name — **impurity** — and it is one line of arithmetic you can do in your head.
Everything else about trees (depth limits, pruning, why a single tree is unstable, why forests
exist) follows from the fact that the choice is made greedily, one node at a time, with no way to
look ahead. This page works one split all the way through on ten rows of data so you can see the
numbers that decide it.

## How It Works

### The number the tree is minimising

The most common impurity measure is **Gini impurity**. For a node containing a mix of classes,
where p₁, p₂, … are the fractions of the node belonging to each class:

```
Gini = 1 − (p₁² + p₂² + … )
```

That is the whole formula. Read it as: *the probability that two rows pulled at random from this
node have different labels*. A node where every row shares one label scores 0 — pull two rows, they
always agree. A node split evenly between two classes scores 1 − (0.5² + 0.5²) = **0.5**, the worst
a two-class node can do. Everything in between is a number telling you how mixed the node is.

The tree's goal at every node is to find the split whose children are, on average, purer than the
parent. The reduction is the **gain**:

```
gain = impurity(parent) − [ (n_left/n) × impurity(left) + (n_right/n) × impurity(right) ]
```

The weighting matters. A split that carves off two perfectly pure rows out of a thousand is nearly
useless, and the n/n weights say so by shrinking its contribution to almost nothing.

### A worked split: two candidates, one winner

Here are ten loan applicants. Two features — annual income and whether the applicant has a prior
default on record — and one label, whether the loan was repaid.

| Applicant | Income ($k) | Prior default | Outcome |
|---|---|---|---|
| A | 22 | no | repaid |
| B | 28 | yes | defaulted |
| C | 31 | yes | repaid |
| D | 39 | no | defaulted |
| E | 45 | yes | defaulted |
| F | 58 | no | repaid |
| G | 61 | no | repaid |
| H | 74 | no | repaid |
| I | 88 | yes | defaulted |
| J | 96 | no | repaid |

**The parent node.** All ten rows: 6 repaid, 4 defaulted, so p = 0.6 and 0.4.

```
Gini(parent) = 1 − (0.6² + 0.4²) = 1 − (0.36 + 0.16) = 0.48
```

**Candidate 1 — split on prior default.** The "yes" branch takes B, C, E, I: 1 repaid out of 4. The
"no" branch takes A, D, F, G, H, J: 5 repaid out of 6.

```
Gini(yes) = 1 − ((1/4)² + (3/4)²) = 1 − (0.0625 + 0.5625) = 0.375
Gini(no)  = 1 − ((5/6)² + (1/6)²) = 1 − (0.6944 + 0.0278) = 0.2778

weighted  = (4/10 × 0.375) + (6/10 × 0.2778) = 0.15 + 0.1667 = 0.3167
gain      = 0.48 − 0.3167 = 0.1633
```

**Candidate 2 — split on income at $51,500.** (That threshold is not arbitrary; the next section
explains where it comes from.) Below it sit A, B, C, D, E: 2 repaid out of 5. At or above it sit F,
G, H, I, J: 4 repaid out of 5.

```
Gini(low)  = 1 − (0.4² + 0.6²) = 1 − (0.16 + 0.36) = 0.48
Gini(high) = 1 − (0.8² + 0.2²) = 1 − (0.64 + 0.04) = 0.32

weighted   = (5/10 × 0.48) + (5/10 × 0.32) = 0.24 + 0.16 = 0.40
gain       = 0.48 − 0.40 = 0.08
```

**Prior default wins, 0.1633 against 0.0800** — twice the gain — so it becomes the root of the
tree, and the income question is pushed down into whichever branch still needs it. Notice that the
low-income child scored 0.48, identical to the parent: that half of the split learned literally
nothing, and it drags the weighted average up. A split is only as good as its *worse* child.

If you prefer entropy to Gini, the same table gives Entropy(parent) = 0.971 bits and an
[information gain](https://howaiworks.ai/glossary/information-gain) of 0.256 bits for the prior-default split — a
different unit, the same winner. The two measures agree on the vast majority of real splits; Gini
is the default in scikit-learn because it avoids a logarithm per candidate.

### Continuous features: sort, then test the gaps

A tree has no concept of "income" as a quantity. It converts a continuous feature into a finite set
of yes/no questions by **sorting the values and testing the midpoints between consecutive distinct
ones**. The ten incomes above — 22, 28, 31, 39, 45, 58, 61, 74, 88, 96 — give nine candidate
thresholds: 25, 29.5, 35, 42, 51.5, 59.5, 67.5, 81, 92. The tree scores all nine and keeps the
best. In this data that best is 51.5, the midpoint of 45 and 58, worth a gain of 0.08; the next
best candidates, 25 and 92, are worth only 0.036 each.

Two consequences fall straight out of this. First, **trees never need feature scaling**: only the
*order* of the values matters, so standardising income, taking its logarithm, or measuring it in
yen produces an identical tree. That is a real advantage over anything distance-based or
gradient-trained. Second, the cost of a node is a sort plus a linear scan — for m features and n
rows, roughly m × n log n at the root — which is why fitting a tree on tabular data is fast enough
that ensembles of hundreds of them are practical.

### Where the splitting stops, and why depth is the knob

Left alone, the recursion does not stop until every leaf is pure. It always can: give a leaf one
row and its impurity is 0. On a 10,000-row training set that means up to 10,000 leaves, one per
example, and **zero training error** — the tree has memorised the data rather than learned it. This
is [overfitting](https://howaiworks.ai/glossary/overfitting) in its most naked form, and trees reach it faster than
almost any other model family because nothing in the fitting procedure resists it.

Depth is the main control because its effect is exponential. A tree of depth d has at most 2^d
leaves: depth 3 gives 8, depth 10 gives 1,024, depth 20 gives 1,048,576. On 10,000 rows, any depth
beyond about log₂(10,000) ≈ 13 is already in the regime where leaves hold single examples, so a
`max_depth` of 20 is not "a bit deeper" than 13 — it is unlimited in practice. The complementary
knobs work on the same problem from the other end: `min_samples_leaf` refuses to create a leaf
below a given size, and `min_impurity_decrease` refuses a split whose gain is not worth taking.
Requiring 20 samples per leaf caps a 10,000-row tree at 500 leaves however deep you let it go.

### Pruning: grow it too far on purpose, then cut back

Stopping early has a known failure: the greedy search cannot look ahead, so a split with a gain of
0.001 may be the only thing standing between the tree and two excellent splits below it. A depth
limit throws those away.

**Cost-complexity pruning**, from the original 1984 CART book, fixes this by growing the tree to
full size and then removing subtrees. It scores a tree as its error plus a penalty per leaf,
`R(T) + α|T|`, where |T| is the number of leaves. At α = 0 the full tree wins; as α rises, whole
subtrees stop paying for themselves and collapse into single leaves; at a large enough α only the
root survives. Choosing α by [cross-validation](https://howaiworks.ai/glossary/cross-validation) picks the tree size
that generalises, rather than the one you guessed. In scikit-learn this is the `ccp_alpha`
parameter.

## Types

The three named algorithms people still cite differ in specific, checkable ways — splitting
criterion, how they treat categorical features, and whether they prune.

**ID3** (Quinlan, 1986) is the ancestor. It splits on information gain using entropy, handles only
categorical features, and makes one branch per category — a six-value feature produces a six-way
split. It does not prune and has no mechanism for continuous features or missing values. Its
notorious flaw is a bias toward high-cardinality features: split on a customer ID with 1,000
distinct values and every child holds one row, so the information gain is the maximum possible
while the predictive value is zero.

**C4.5** (Quinlan, 1993) is ID3 with that flaw patched and the practical gaps filled. It replaces
information gain with **gain ratio**, dividing the gain by the entropy of the split itself — for a
1,000-value ID that divisor is log₂(1,000) ≈ 9.97 bits against 1 bit for a binary feature, a
roughly tenfold penalty that removes the incentive. It handles continuous features by threshold
search, routes rows with missing values down both branches with fractional weights, and prunes
after growing.

**CART** (Breiman, Friedman, Olshen and Stone, 1984) is what almost every modern library actually
implements. It uses Gini for classification and variance reduction for [regression](https://howaiworks.ai/glossary/regression),
makes **strictly binary splits** even on categorical features, and prunes by cost complexity. The
binary-only rule is why scikit-learn requires categorical features to be encoded numerically first.
The regression variant is the same algorithm with a different score: instead of Gini it minimises
the squared error within each child, and the leaf predicts the mean of its rows rather than the
majority class.

## Real-World Applications

**Clinical decision rules** are the strongest case for a genuine single tree, because the model has
to be executed by a doctor from memory. The PECARN pediatric head-injury rule was derived by binary
recursive partitioning on a cohort of more than 42,000 children ([Kuppermann et al., *The Lancet*,
2009](https://www.thelancet.com/journals/lancet/article/PIIS0140-6736(09)61558-0/abstract)) and came
out as six yes/no questions per age group, with a reported negative predictive value of 99.95% in
children aged two and over. It is used in emergency departments to decide against a CT scan. No
ensemble could occupy that role: the output had to be something a clinician can apply at the
bedside without a computer.

**Credit scoring** is the other durable one, for regulatory rather than clinical reasons — a lender
must be able to state the specific reasons for a denial, which favours models whose decisions
attribute to named inputs. [AI in finance](https://howaiworks.ai/glossary/ai-finance) covers what the rules require and
why gradient-boosted trees rather than deep networks dominate underwriting; the point here is that
the attributability comes from the tree structure underneath.

**Exploratory analysis** is the everyday use and the least discussed. Fitting a depth-3 tree to a
new dataset takes seconds and tells you which two or three features carry the signal and roughly
where their interesting thresholds lie — a fast, readable first pass before anything heavier, and a
practical form of [feature selection](https://howaiworks.ai/glossary/feature-selection).

**As a component**, the single largest deployment of decision trees is invisible: they are the base
learner inside [random forests](https://howaiworks.ai/glossary/random-forest) and [gradient
boosting](https://howaiworks.ai/glossary/gradient-boosting), which remain the strongest general-purpose models for
tabular data. Every XGBoost model is a few hundred to a few thousand trees of the kind described
above.

## Key Concepts

- **The three kinds of node**: the root holds all training rows, every internal one holds a single
  test, and a leaf holds a prediction — the majority class for classification, the mean for
  regression.
- **Greedy construction**: the best split at each node is chosen without regard to what it makes
  possible below. Finding the globally optimal tree is NP-hard, so mainstream libraries do not try.
- **Built-in ranking of features**: summing the weighted impurity reduction a column earns across
  every node it splits scores how much work it did — cheap to compute, and biased toward
  high-cardinality columns for exactly the ID3 reason above.
- **Axis-aligned split**: every test compares one feature to one constant, so every boundary a tree
  can draw is perpendicular to a feature axis.

## Challenges

**A single tree is high-variance, and the root is where it shows.** Because the whole structure
hangs off one greedy first choice, changing a handful of training rows can change that choice and
invalidate everything beneath it. In the ten-row table above, flip applicant A from repaid to
defaulted — one row in ten — and the prior-default gain falls from 0.1633 to 0.0833 while the
income split at 51.5 rises to 0.1800. The root swaps, and every question below it is re-derived on
different data. A model whose top-level explanation changes when one row moves is not a stable
explanation, whatever its accuracy. This instability is the entire reason
[ensemble methods](https://howaiworks.ai/glossary/ensemble-methods) exist: averaging many decorrelated trees cancels the
variance while keeping the flexibility, which is what [random forests](https://howaiworks.ai/glossary/random-forest) and
[gradient boosting](https://howaiworks.ai/glossary/gradient-boosting) do and where the practical accuracy lives.

**A diagonal boundary is expensive, and the arithmetic is unforgiving.** Every split is
axis-aligned, so a true boundary running at 45° through two features has to be approximated by a
staircase. Take the unit square with the boundary x + y = 1. A staircase of k steps whose corners
touch that line leaves k right triangles uncovered, each with legs 1/k, so the misclassified area
is k × ½(1/k)² = **1/(2k)**. Getting that below 1% needs k = 50 steps, which is 100 leaves and 99
internal nodes; below 0.1% needs k = 500, so 1,000 leaves. Error falls only linearly in the size of
the tree. [Logistic regression](https://howaiworks.ai/glossary/logistic-regression) represents the same boundary exactly
with three numbers — two weights and an intercept — and a single [neural
network](https://howaiworks.ai/glossary/neural-network) unit does the same. When your features interact smoothly and
diagonally, a tree is the wrong shape, and no amount of depth fixes the shape.

**Interpretability is a property of the depth, not of trees as a family.** A depth-3 tree is at most
eight leaves and eight rules, which a person can read, argue with, and sign off on — this is the
claim that makes trees attractive in the domains
[explainable AI](https://howaiworks.ai/glossary/explainable-ai) cares about. A depth-20 tree can hold over a million
leaves, and a prediction path through it that names twenty conditions is not an explanation anyone
can check. The commonly repeated "decision trees are interpretable" is true of the trees people
draw in tutorials and false of the trees that win accuracy comparisons, and the gap between those
two is exactly the accuracy-versus-interpretability trade-off.

**Splitting bias and thin leaves.** Impurity-based selection favours features with many distinct
values, because more candidate thresholds means more chances at a high score — the ID3 problem
above, still present in Gini implementations and still visible in built-in importances. And because
a leaf's prediction is estimated from whatever rows land in it, a leaf holding three rows gives you
a probability with three rows' worth of confidence, which is how a tree that looks precise turns
out to be guessing.

## Code Example

Fitting a shallow tree and printing it as text is usually more informative than any accuracy
number, because it shows you exactly which splits the algorithm chose and in what order.

```python
from sklearn.tree import DecisionTreeClassifier, export_text
import numpy as np

# The ten applicants from the worked example above.
# Columns: income ($k), prior_default (1 = yes)
X = np.array([[22, 0], [28, 1], [31, 1], [39, 0], [45, 1],
              [58, 0], [61, 0], [74, 0], [88, 1], [96, 0]])
y = np.array([1, 0, 1, 0, 0, 1, 1, 1, 0, 1])  # 1 = repaid

tree = DecisionTreeClassifier(criterion="gini", max_depth=2, random_state=0)
tree.fit(X, y)

# The tree as text. The root test is the split worked out by hand above.
print(export_text(tree, feature_names=["income", "prior_default"]))

# Gini(parent) = 0.4800, straight from the class balance.
p = y.mean()
print(f"Gini(parent) = {1 - (p**2 + (1 - p)**2):.4f}")

# Impurity-weighted importances: prior_default 0.583, income 0.417.
for name, imp in zip(["income", "prior_default"], tree.feature_importances_):
    print(f"{name}: {imp:.3f}")

# Unconstrained, the same ten rows are memorised: 6 leaves, depth 3, 100% training accuracy.
full = DecisionTreeClassifier(random_state=0).fit(X, y)
print(full.get_n_leaves(), full.get_depth(), full.score(X, y))
```

The printed tree splits on `prior_default <= 0.50` at the root, matching the hand calculation, and
only then reaches for income. Drop `max_depth` and the tree keeps splitting until every leaf is
pure — training accuracy 1.0 on data it has simply memorised. Overfitting a tree takes one omitted
keyword argument, which is why the depth and pruning controls above are not optional extras.

## Frequently Asked Questions

### How does a decision tree decide which feature to split on?

It scores every possible split and keeps the best one. The score is the drop in impurity: measure how mixed the classes are in the parent node, measure the same thing in the two children, weight the children by how many rows they hold, and subtract. The split with the largest drop wins. Nothing is learned by gradient descent — the tree simply enumerates candidates and picks the greedy best at each node.

### What is Gini impurity?

Gini impurity is 1 minus the sum of the squared class proportions in a node. A node with 6 repaid and 4 defaulted loans scores 1 − (0.6² + 0.4²) = 0.48; a node where every row shares one label scores 0. It is the chance that two rows drawn at random from the node disagree, so lower means purer.

### Gini impurity or entropy — which should I use?

It almost never matters. The two curves have the same shape and the same minimum, and they usually select the same split; entropy costs a logarithm per candidate, Gini costs a multiplication. Pick either and spend the effort on depth and pruning instead, which change results by far more.

### How does a decision tree handle continuous features like income?

It sorts the values and tests the midpoints between consecutive distinct ones. Ten distinct incomes give nine candidate thresholds, and the tree evaluates each. This is why trees never need feature scaling — only the ordering of a feature matters, so log-transforming or standardising it produces exactly the same tree.

### Why do decision trees overfit so easily?

Because an unconstrained tree keeps splitting until every leaf is pure, which on 10,000 training rows means up to 10,000 leaves and zero training error — the tree has memorised the data. Depth is the main knob: each extra level doubles the leaves the tree may use, so limiting max_depth, requiring a minimum number of samples per leaf, or pruning after growth is what makes a tree generalise.

### Are decision trees interpretable?

A shallow one is. A depth-3 tree is eight rules you can read aloud, which is why regulated domains still use them. A depth-20 tree can hold over a million leaves and is no more readable than any other black box. Interpretability is a property of the depth, not of trees as a family.

## Related

### Related terms

- [Information Gain](https://howaiworks.ai/glossary/information-gain)
- [Random Forest (RF)](https://howaiworks.ai/glossary/random-forest)
- [Gradient Boosting](https://howaiworks.ai/glossary/gradient-boosting)
- [Ensemble Methods](https://howaiworks.ai/glossary/ensemble-methods)
- [Overfitting](https://howaiworks.ai/glossary/overfitting)
- [Classification (CLF)](https://howaiworks.ai/glossary/classification)

---

Source: https://howaiworks.ai/glossary/decision-trees — HowAIWorks.ai