How to build a decision tree classifier from scratch

A decision tree predicts by asking a sequence of questions about an input row. We will build one in pure Python, starting with five patients and checking each split by hand.

One good example is the Cleveland heart-disease study, where each row is a patient and the last column is what we want to predict:

The last column — tinted above — contains an observed event: this patient turned out to have heart disease, that one turned out not to. That column is called a label; every column before it describes the case, and only this one says how the case turned out. What we want to learn is the relationship between the two — from the cases where the label is already known, so that it can be applied to cases where it is not. When the label is a category, as it is here, that is the classification task.

Decision trees also form the base models in random forests and gradient boosting. Understanding how one tree chooses its splits makes those ensembles easier to follow.

Two tasks come up on tabular data: classification, where the answer is a category, and regression, where it is a number — a salary, a price. A decision tree handles both. This article builds the classifier; point the same code at a numeric target, replace the impurity measure with the variance of that target and the leaf’s label counts with their average, and you have a regression model that predicts a number — nothing else in the code changes, though a good deal about the resulting model does, which is the subject of the companion article.

Boosting is the subject of a later article. This one focuses on the part it repeats hundreds of times: how a single decision tree gets built from a table of rows — where its questions come from, how one of them is chosen over the others, and when the splitting stops. We write it in pure Python, no NumPy and no scikit-learn, on five rows small enough to check every number by hand.

Download the complete Python example and run python3 heart_tree.py.

Two node types, and the regions they carve

We will work on five patients from the Cleveland heart-disease study. The full table holds 303 patients and thirteen features (predictors), but we will use just five rows and two of the features, plus the label:

training_data = [
    ["normal", 0, "No"],
    ["fixed", 0, "Yes"],
    ["reversable", 2, "Yes"],
    ["reversable", 1, "Yes"],
    ["fixed", 0, "No"],
]

Given a patient’s stress-test result and vessel count, the tree will have to predict whether that patient has heart disease — so it is worth knowing what those two columns record.

stress_test (Thal) records a thallium test result: normal, fixed defect, or reversible defect. We retain the source spelling reversable in the code. vessels (Ca) counts major vessels, from 0 to 3, colored by fluoroscopy; it is not a count of diseased vessels. These definitions come from the UCI dataset documentation.

We are going to take those five rows and split them into smaller and smaller groups, using the features and their values to decide which group each row belongs to. The sequence of splits draws as a branching diagram, which is where the name “tree” comes from.

There are two types of node in that diagram.

The diamonds are decision nodes. Each holds a yes/no question and sends a row down either the True or False branch. Our CART-style tree always splits into two children; other tree algorithms can use more branches.

The boxes are leaves. Each stores the label counts of the training rows that reached it: Yes: 2, Yes: 1, No: 1, or No: 1. Dividing by the total gives class-frequency estimates of 100% Yes, 50/50, and 100% No. These tiny samples do not establish the probability of disease for a new patient.

Decision nodes route rows to leaves, partitioning the input space. For numeric features, a threshold cuts along one axis. The figure below uses a separate synthetic dataset to illustrate boundary shapes: the straight line, smooth neural-network-style curve, and tree splits are schematic; the k-nearest-neighbor panel is computed from the plotted points.

So what would it actually take to build one of these? We would need two things.

• A way to generate candidate questions from a table, since the tree has to get them from somewhere.
• A way to score those candidates, so the best one can be picked — a decision node holds one question and no more.

We also need a stopping rule. Here we stop when no candidate reduces impurity beyond a small numerical tolerance. This can leave a mixed leaf, even when a sequence of further splits could separate its rows: the XOR pattern is one example. Depth limits and minimum leaf sizes provide additional control over overfitting.

From rows to questions

Generate candidates by pairing each feature with every distinct value it takes in the current rows. A categorical rule tests equality, such as stress_test == fixed. A numeric rule tests a threshold, such as vessels >= 1, which is true for counts 1, 2, and 3.

That pairing is the whole generator, so it is worth writing out in full. For our dataset there are two columns with three distinct values each, so we end up with a list of six pairs:

Our implementation tests one feature at a time and uses observed values as numeric thresholds. That is a simplification, not a requirement of CART: scikit-learn uses midpoints between adjacent distinct values. Both choices offer the same training partitions, but can route a new value between two observations differently. Categorical CART splits can also test subsets of categories; ours tests one category against the rest.

Those six are the whole of what this tree can ask — and not all of them make it into the finished tree. Most candidates are tried, scored and rejected; here only two survive to become questions in the tree we are going to build, while the other four are evaluated and discarded. And the list is finite — never longer than the number of distinct values in the table — which is why the next step can simply try every one of them.

In code, questions are defined as one small class. A Rule holds a column index plus a value, and its holds method decides which of the two comparisons applies by looking at the type of that value:

FEATURES = ["stress_test", "vessels", "disease"]

class Rule:
    """One yes/no test: a column, and the value it is compared against."""

    def __init__(self, column, value):
        self.column = column
        self.value = value

    def holds(self, row):
        observed = row[self.column]
        if isinstance(self.value, (int, float)):
            return observed >= self.value     # numeric: threshold
        return observed == self.value         # categorical: equality

    def __repr__(self):
        operator = ">=" if isinstance(self.value, (int, float)) else "=="
        return f"Is {FEATURES[self.column]} {operator} {self.value}?"

There are several ways to implement that matching logic. Ours is the isinstance check inside holds, and it is the reason this tree handles a text column and a number column side by side with no preprocessing at all. The libraries do not all take that route.

Scikit-learn requires numeric inputs. For an unordered feature such as stress_test, one-hot encoding preserves the categories without imposing an order:

The tree then asks is_fixed >= 0.5 where ours asks stress_test == fixed — the same split, spread over three columns. The 0.5 is not meaningful in itself: the column holds only 0 and 1, so any cut between them separates the same rows, and sklearn puts its thresholds at the midpoint of two adjacent values. A column with four categories would simply become four such 0/1 columns, each still asked about at 0.5 — the encoding grows sideways, and every question stays a yes/no test on one value.

LightGBM splits on subsets instead: it tests a group of categories at once, which is still one question about one column — the difference is that the value being tested is a set rather than a single category:

ours:    Is stress_test == fixed?
theirs:  Is stress_test in {normal, reversable}?

LightGBM and XGBoost support categorical partitioning, using an ordering of category statistics to search candidate groups. CatBoost uses ordered target statistics for many categorical features and one-hot encoding for some low-cardinality features; its treatment depends on the configuration. See the CatBoost documentation.

Measuring the diversity of a dataset

To choose a split, we first measure how mixed the labels are with Gini impurity. We then calculate the reduction in size-weighted impurity. The code calls this gain; strictly, information gain usually means the corresponding reduction in entropy.

Let’s look at Gini impurity first, which is the measurement of how mixed a collection is — one number saying whether the things in it are all of a kind or a jumble of many.

Suppose you need to say which of two collections is the more mixed one. One look at the image below is enough to tell that the second set is more diverse: four kinds instead of two, and spread more evenly across them. The eye settles it instantly.

Now suppose we did not know the composition of either set — no tallies, no list of kinds, just the ability to reach in and take something out. Could we put a number on the diversity?

Draw two items independently with replacement, record whether their kinds differ, and repeat. Replacing the first item before the second draw makes the probabilities multiply as used below.

The figure shows one illustrative sequence of ten pairs for each set:

Four of the left set’s pairs hold two different kinds; seven of the right set’s do. Divide by the number of draws and you have the estimate — the hat on $\hat{d}$ denotes a value estimated from a sample, as opposed to one computed from the whole population:

A larger fraction of mismatches suggests greater diversity. More independent pairs generally improve the estimate, but ten or even a hundred pairs do not guarantee an accurate value.

Generally, though, you do not need to sample at all: when you know what the set contains, a little probability theory gives you that exact value directly. Work out the chance the two picks agree, then subtract it from 1.

Take the left set. Seven of its ten items are blue squares, so a single pick is a square with probability 0.7 — and the probability of picking two squares in a row is $0.7 \times 0.7 = 0.49$. The circles give $0.3 \times 0.3 = 0.09$. Those are the only two ways the picks can match, so they agree $0.49 + 0.09 = 0.58$ of the time. But what we are after is the opposite — how often the two picks come back different — and since every draw either matches or does not, that is one minus the chance of a match: $1 - 0.58 =$ 0.42.

The right set is the same calculation with four kinds instead of two:

Two picks agree 30% of the time, so they differ 0.70 of the time — matching the seven-out-of-ten the sampling turned up, without a single draw.

The same logic can be demonstrated geometrically. Lay out every ordered pair of picks as a cell in a grid — first pick across, second pick down. Ten items give a hundred cells, and that grid is every outcome there is:

That exact value has a name. The probability that two items drawn at random from a set are of different kinds is the set’s Gini impurity, and written down it is:

where $p_k$ is the fraction of the set belonging to kind $k$. The two halves are the two ways of saying it: $\sum_k p_k^2$ is the probability the draws agree — for each kind, the chance both land in it, added up — and one minus that is the chance they differ.

Our two sets, run through it, are the arithmetic from a moment ago in its compressed form:

The concentration statistic $\sum_k p_k^2$ is also used in Simpson’s index and the Herfindahl–Hirschman index. Gini impurity is one minus that sum, not the same statistic.

Gini on our five rows

So now we are ready to calculate Gini impurity for our five rows. First we need a tally of kinds, which in our case are labels: where the sets above held squares, circles, triangles and a star, a pile of rows holds Yes and No. So count them, how many of each label are in a given pile, because every quantity in this article follows from that dictionary.

def label_counts(rows):
    """Tally the labels in a pile — the label is always the last column."""
    counts = {}
    for row in rows:
        counts[row[-1]] = counts.get(row[-1], 0) + 1
    return counts

The initial run over the entire dataset, label_counts(training_data), gives {'No': 2, 'Yes': 3} — our five patients, tallied by kind.

Now, with the tally at hand, we can compute the Gini impurity — five lines of Python:

def gini(rows):
    """Impurity of a pile: 0 when every row in it carries the same label."""
    if not rows:
        raise ValueError("Cannot measure impurity of an empty group")
    impurity = 1
    for count in label_counts(rows).values():
        share = count / len(rows)
        impurity -= share ** 2
    return impurity

The loop is the formula, one term per label — feed it a pile of all-Yes patients and it returns 0.0, feed it one Yes and one No and it returns 0.5. Our own training set, three Yes against two No, starts at:

gini(training_data) → 0.48

We are going to run through every candidate question and see which one leaves the least mixing behind, so 0.48 is the number to beat. It is also a high starting point: with two labels, Gini is at its maximum of 0.5 when they are split evenly, so three Yes against two No leaves us at 0.48 — about as jumbled as five rows can be.

Gini gain — scoring a split

Score a candidate by subtracting its children’s size-weighted Gini impurity from the parent’s impurity:

Written down, it is one line:

And it is four steps long:

1. split the pile $S$ with the question, giving two piles — $S_L$, the rows that answered True, and $S_R$, the rows that answered False;
2. run gini on each of them;
3. combine those two numbers into one, weighted by how many rows went to each side: $\frac{|S_L|}{|S|}$ gives us the weight of the left pile and $\frac{|S_R|}{|S|}$ the weight of the right, each one the share of the parent’s rows that went that way;
4. subtract that from the parent’s impurity, $\text{Gini}(S)$.

What is left is the impurity the question removed — the higher it is, the better the question.

Zero gain means this split leaves the weighted impurity unchanged. Pure children give the largest possible gain: the full impurity of their parent.

It is worth highlighting why the weighting in step 3 is needed at all, because without it the score is easy to fool. Two of our candidates, Is stress_test == normal? and Is vessels >= 1?, each split the five rows into one perfectly pure child, with Gini exactly 0, and one child that is still mixed. Where they differ is in how much data that clean child carries: one of them peels off a single patient and leaves four mixed rows behind, the other takes two out and leaves three. Only the weighting sees that difference. It makes a pure child count for exactly what it weighs, so a child of one row barely registers and the mess left behind sets the score.

Here are both of them worked out in full, each with its two children combined the two ways — counted equally, then weighted by the share of the rows each child holds:

Now the same treatment for the other candidate. Is vessels >= 1? also carves off a perfectly pure child, but that child holds two patients rather than one, and the pile it leaves behind is three rows rather than four — and messier, at 0.444 instead of 0.375:

So the numbers in the two figures show something stronger than a rescaling. Counted equally, Is stress_test == normal? scores 0.293 and Is vessels >= 1? scores 0.258, so the first question wins. Weighted, they come out 0.180 and 0.213, and the second wins instead. The weighting does not merely shrink the scores — it reverses the order, and since this is the root, the two answers give trees that differ all the way down.

This is how we implement the split and its information gain, weighting included. split_rows performs step 1, sorting the rows into the two piles a question makes, and split_gain performs steps 2 to 4, scoring what came out against what went in:

def split_rows(rows, rule):
    """Sort every row into the pile where the rule holds, and the pile where it does not."""
    true_pile, false_pile = [], []
    for row in rows:
        (true_pile if rule.holds(row) else false_pile).append(row)
    return true_pile, false_pile

def split_gain(parent_impurity, true_pile, false_pile):
    """What went in, minus the two piles that came out, each weighed by its share."""
    share = len(true_pile) / (len(true_pile) + len(false_pile))
    return parent_impurity - share * gini(true_pile) - (1 - share) * gini(false_pile)

Run them over the two candidates above and they return 0.180 and 0.213 — the same numbers the figures worked out by hand, now computed rather than drawn.

The mechanism — split, then recurse

We now have every piece: a way to generate questions, a way to measure how mixed a pile is, and a way to score what a question does to it. Here is the procedure that puts them together. A decision tree is grown by one recipe, applied to one pile of training rows:

1. Try every question the data allows — every feature, every value that feature takes.
2. Score each question by how much it unmixes the labels in the pile — that is information gain, built on Gini impurity, exactly as we just derived it.
3. If no question helps, stop: the pile becomes a leaf, and its label counts become the prediction.
4. Otherwise use the best question to split the pile into two smaller piles.
5. Run this same procedure on each of the two piles.

This procedure has a canonical name — recursive binary splitting — a top-down, greedy algorithm used to build decision trees by successively dividing a dataset into two groups. It starts with all data at the root, evaluates every feature and split point to minimize error or maximize purity, and repeats the process on each new subgroup until a stopping limit is reached.

Greedy means choosing the best split at the current node without looking ahead or revisiting earlier choices. A split with no immediate gain can still enable useful splits below it, as in XOR. Our stopping rule will miss those.

Being recursive is what carves the rectangles from the intro’s figure: each call owns one region of feature space — the rows that survived the questions above it — and either subdivides that region or seals it as a leaf. The rectangles are the piles at the bottom of the recursion.

Choosing the root split — and the tie

Before we build the whole recursive thing, let’s quickly look through the implementation of the part that runs at a single node — the search for the best splitting question. At the root that node holds all five patients, and the function doing the searching is choose_split, which tries every value of every feature and keeps the best one.

It is two nested loops — every column on the outside, every distinct value that column takes on the inside — and each pair they produce goes through four steps:

1. build a Rule out of the column and the value;
2. hand it to split_rows, which sorts the rows into the two piles it makes;
3. score those piles with split_gain;
4. compare that score against the best seen so far, and keep the question if it wins.

When both loops finish, the question still holding the best score is what the function returns.

def choose_split(rows):
    parent_impurity = gini(rows)
    winning_gain, winning_rule = 0, None

    for column in range(len(rows[0]) - 1):
        for value in sorted(set(row[column] for row in rows), reverse=True):
            rule = Rule(column, value)
            true_pile, false_pile = split_rows(rows, rule)

            if not true_pile or not false_pile:
                continue  # this rule doesn't divide the data

            gain = split_gain(parent_impurity, true_pile, false_pile)

            if gain >= winning_gain:
                winning_gain, winning_rule = gain, rule

    return winning_gain, winning_rule

One call at the root scores every question the generator produced, and comes back with this:

Six questions — two columns with three distinct values each — but only five of them get a number. Is vessels >= 0? is true of every patient, because 0 is the smallest value that column takes, so it sends all five rows down the True branch and none down the False one. One child holds the whole pile and the other holds nothing, which is not a split but a copy — nothing was divided, so there is nothing to score. The not true_pile or not false_pile guard drops it before split_gain ever sees it. Its gain would have been exactly 0 anyway — one child weighing nothing, the other being the parent — but skipping it also stops a non-split from being returned as the best question when nothing else scores above zero.

Now look at the top of that table, because it is the interesting part. Two different questions came back with the same score of 0.2133. When that happens, the later candidate overwrites the earlier one. That behavior is an implementation detail, and in our algorithm it comes from two things: columns are scanned in index order, so stress_test (column 0) gets there first and is then quietly displaced by the equally-good vessels (column 1); and the comparison is written with >= rather than >, which lets the displacement happen at all:

if gain >= winning_gain:

Here the tied questions select exactly the same two groups of training patients, so the tie does not change their subsequent partitions. It can change predictions for unseen combinations, such as normal with vessels=3. We scan distinct values in descending order so ties are reproducible; >= still gives the last tied candidate the win.

Recursion — building the tree

Now that a single node can find its question, we are ready to build the whole tree — the recursion that runs that search on pile after pile, and stores what it finds. Storing it takes one class per node type from the opening diagram: a Leaf holds the label counts of whatever rows reached it, and a Node holds a question and two branches. In the textbook’s vocabulary, the question is a splitting rule — one predicate on one feature, which is where the Rule class takes its name — and a decision node is that rule wired into the flowchart, with the two branches giving its yes/no answers somewhere to go. You can think of a finished tree as a series of splitting rules. Starting at the top of the tree and applied on the way down — choose_split learns those rules, and the nodes are where the chosen ones live.

class Leaf:
    def __init__(self, rows):
        self.counts = label_counts(rows)

class Node:
    def __init__(self, rule, if_true, if_false):
        self.rule = rule
        self.if_true = if_true
        self.if_false = if_false

def grow_tree(rows):
    if not rows:
        raise ValueError("Training rows must not be empty")
    gain, rule = choose_split(rows)

    if gain <= 1e-12 or rule is None:
        return Leaf(rows)          # base case: no rule helps anymore

    true_pile, false_pile = split_rows(rows, rule)
    return Node(rule, grow_tree(true_pile), grow_tree(false_pile))

When we run it on the five patients, this is the tree we end up with — drawn with the piles visible at every branch:

The tree has depth 2 and three leaves. The root sends the two training rows with vessels >= 1 to a pure Yes leaf. This describes these two rows, not a medical rule.

That is worth pausing on: a whole group fell out of the data with no mixture at all — Gini 0, produced by a single question. One level down, the lone normal patient does the same — and notice that stress_test has three values while the tree only ever asks about one of them. stress_test == fixed? peels the fixed-defect patients off, and whatever is not fixed rides the False branch together, undistinguished. Here that happens to be the single normal patient, because both reversable patients left at the root.

Of the tree’s three leaves, two are pure; every training row except the colliding pair gets sorted into a group with zero mixture, and the recursion stops in each of them precisely because there is no impurity left to remove.

That leaves the third leaf, holding one Yes label and one No for the identical set of feature values. No question could separate those two patients — and no other model could either, because what would tell them apart is not in the data at all. This could be resolved if we used more predictors, since the eleven columns we threw away may well hold something that separates these two patients.

Training chooses the tree’s structure, thresholds, and leaf counts. Once the recursive calls return, the model is ready to predict; there are no gradient updates or training epochs in this implementation.

Classifying — reading the probability off a leaf

Prediction is recursion again, and shorter than the training code:

def descend(row, node):
    if isinstance(node, Leaf):
        return node.counts

    branch = node.if_true if node.rule.holds(row) else node.if_false
    return descend(row, branch)

def as_percentages(counts):
    total = sum(counts.values())
    return {label: f"{count / total:.0%}" for label, count in counts.items()}

Each Node stores one Rule — a column index plus a value — and holds compares the row’s entry in that column against it, returning a plain True or False. That boolean is the only thing descend needs: True sends the row down if_true, False down if_false, and the recursion stops as soon as it lands on a Leaf.

Let’s take one patient’s data, ['fixed', 0, 'Yes'], and see how the tree predicts whether they have heart disease or not:

1. the root asks Is vessels >= 1?; holds reads the patient’s vessels entry — that is 0 — and since the value is numeric it evaluates 0 >= 1, giving False, so the row takes the false branch;
2. that node asks Is stress_test == fixed?; holds reads the patient’s stress_test entry — 'fixed' — and since the value is a string it evaluates 'fixed' == 'fixed', giving True, so the row takes the true branch;
3. that branch is a Leaf, so descend returns the counts stored there: one Yes and one No.

Those counts returned by descend are the prediction, in raw form. They can be read as a single label, by taking whichever is most common in the leaf — this is what predict does in a library like sklearn, and it is unambiguous in the pure leaves, where {'Yes': 2} means Yes. They can also be read as a probability, by dividing each count by the total, which is predict_proba, and what as_percentages does here.

The mixed leaf reports 50/50 because it contains one example of each class. That is an empirical estimate from two rows, not proof of a 50% population risk or a complete uncertainty estimate. Identical inputs with conflicting labels impose a training-error floor on deterministic predictors using these features. A library returning one class must also choose a rule for tied counts.

The widget below is a slightly bigger toy — two numeric features, thresholds instead of our mixed types — but the mechanism is identical, and it shows the two views of a tree at once. The left panel is the partition; the right panel is the walk. The two sliders are the feature values $x_1$ and $x_2$ — dragging them composes a new row and moves it around the feature space. The moment that point crosses a dashed line is exactly the moment the path through the tree changes, because the region and the leaf are the same object wearing different clothes.

Notice, too, that this tree uses the feature denoted by $x_1$ twice — once at the root, and again two levels down at a different threshold. Those are two different questions on one column — same feature, different value — because a feature is not used up by being split on: the first cut separates what it can, and the rows left over may still be separable along that same axis.

The same feature may be used at several nodes. Each node rebuilds its candidates from the rows that reached it, so a value absent from those rows is no longer a candidate there. For example, the False child of our root has no row with vessels=2.

Now hand it five patients it has never seen, all of them real rows from the same file:

patient   2  ['normal',     3]   Actual: Yes.  Predicted: {'Yes': '100%'}
patient   9  ['reversable', 1]   Actual: Yes.  Predicted: {'Yes': '100%'}
patient 266  ['fixed',      0]   Actual: Yes.  Predicted: {'Yes': '50%', 'No': '50%'}
patient  88  ['NA',         0]   Actual: No.   Predicted: {'No': '100%'}
patient 267  ['NA',         0]   Actual: Yes.  Predicted: {'No': '100%'}

The first test row is ['normal', 3, 'Yes'], and a vessels count of 3 never appeared in training — our five patients only ever showed 0, 1 and 2. It still falls into a leaf, because vessels >= 1 is a threshold rather than a lookup: 3 clears it and walks the same path a 1 would. Thresholds generalize past their training values for free.

Missing values are a different story: the model simply does not handle them correctly. Patients 88 and 267 have no recorded stress test — the file says NA — and since NA never appeared in training it fails the stress_test == fixed? test and slides down the False branch, which is how patient 267 comes back as {'No': '100%'} while actually having the disease.

In practice you would deal with that before training — drop the incomplete rows, impute the missing entries, or make "missing" a category of its own.

An unseen category follows the same False branch as any other value that fails the equality test. Our model neither detects that novelty nor reduces the displayed percentage. In the example above, 100% No is based on a leaf containing just one training row.

Missing-value support depends on the implementation. Some libraries learn a default branch; original CART can use surrogate splits. These mechanisms do not make an arbitrary string such as "NA" a recognized missing value: use the representation the library expects.

Why one tree is not the end of the story

This is a small CART-style implementation. Its main limitations are unrestricted growth, sensitivity to the training sample, simple categorical handling, and no explicit missing-value policy.

A deep tree can overfit. It can keep improving training fit by creating small leaves whose predictions reflect noise in that sample. Stopping at negligible gain prevents useless immediate splits, but does not control generalization. Depth limits, minimum leaf sizes, and pruning address that problem.

For a larger example, use scikit-learn’s DecisionTreeClassifier. It follows the same greedy idea, but its midpoint thresholds, tie handling, and stopping details can produce a different tree from ours.

Now point it at the breast-cancer dataset (398 train rows, 171 test, 30 features):

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

data = load_breast_cancer()
X_tr, X_te, y_tr, y_te = train_test_split(
    data.data, data.target, test_size=0.3, random_state=0
)

unpruned = DecisionTreeClassifier(criterion="gini", random_state=0).fit(X_tr, y_tr)
print(unpruned.get_depth(), unpruned.get_n_leaves())
print(unpruned.score(X_tr, y_tr), unpruned.score(X_te, y_te))

for depth in (1, 2, 3, 5, 7):
    pruned = DecisionTreeClassifier(
        criterion="gini", max_depth=depth, random_state=0
    ).fit(X_tr, y_tr)
    print(depth, pruned.score(X_tr, y_tr), pruned.score(X_te, y_te))

The unrestrained tree — the one with nothing holding it back — comes out like this:

UNPRUNED (scikit-learn)
  depth      7
  leaves     19
  train acc  1.000
  test acc   0.912

Training accuracy 1.000 means all 398 training labels are reproduced. It does not require one leaf per row: this fit has only 19 leaves. Its accuracy on the 171 held-out rows is 0.912.

Now let’s add the one knob our version does not have — max_depth, a hard cap on how many questions deep the tree may go, which stops the splitting whether or not there is gain left to collect. When we run the same tree capped at a series of depths and collect the results, this is what comes out:

On this split, depth 2 scores 0.947 on held-out data, compared with 0.912 at depth 7, despite its lower training accuracy. This illustrates overfitting; it does not establish depth 2 as generally optimal. If these results guide the choice of depth, this held-out set is serving as validation data. Evaluate the selected model on a separate test set.

A single tree can also be unstable. Small changes to training rows can change which candidate wins a close comparison, affecting the subtree below it. This sensitivity to the sample is different from an avoidable implementation issue such as iterating an unordered set.

Sorting the candidate values fixes run-to-run variation caused by Python’s set order. It does not remove statistical instability: retraining on a different sample can still change the fitted tree.

Those two behaviors are two sides of the bias-variance tradeoff. In statistical learning, bias is the error introduced by approximating a complicated reality with a simpler model — a model too rigid to represent the pattern will be wrong no matter how much data you hand it. Variance is the amount the fitted model would change if you estimated it from a different training set: retrain on another sample of patients and a high-variance method gives you a noticeably different model, making noticeably different mistakes.

Increasing depth often lowers bias and raises variance, but this is a tendency, not a guarantee about every dataset or accuracy score. Noise conditional on the available features limits achievable expected performance; a conflicting pair in a small training set does not quantify that population limit.

There are established methods to address those problems — a cap on depth, a minimum number of rows per leaf, a minimum gain worth splitting for, and cutting back branches after the fact. In practice you rarely apply them to a lone tree; they are the knobs you tune inside an ensemble — a model built from many trees whose answers are combined into one, which is what a random forest and gradient boosting each are.

Pre-pruning limits growth with controls such as max_depth and min_samples_leaf. Post-pruning grows a larger tree first, then removes branches. CART cost-complexity pruning balances training impurity against a penalty per leaf; scikit-learn exposes that penalty as ccp_alpha. Choose its value using validation data or cross-validation, keeping the final test set separate.

A random forest averages many trees trained with randomized rows and feature choices, reducing variance when their errors are not perfectly correlated. Gradient boosting fits trees sequentially to improve the ensemble’s loss. Continue with the regression-tree article.

Where our version is slower than a real one

Our split search repeatedly scans the same rows. Production implementations can reuse counts or histograms to reduce that work. They also differ in candidate thresholds, categorical support, missing-value handling, and tie rules, so speed is not their only difference from this example.

The loop runs over every feature and every distinct value that feature takes, so the number of candidates is features × values. Each candidate then costs a full pass over the data: split_rows walks every row to sort it into two piles, and split_gain calls gini on each pile, which counts its labels from scratch. That is $O(\text{features} \times \text{values} \times \text{rows})$. On five rows with three values per column, invisible. On a continuous feature — cholesterol, say — nearly every row carries a distinct value, so the candidate count grows with the data while each candidate still costs a full scan: quadratic in the number of rows, and hopeless at a hundred thousand of them.

Take five rows of a cholesterol column — 210 (No), 233 (No), 250 (Yes), 286 (Yes), 300 (Yes). The generator turns them into five candidate questions, one per observed value, of which four actually split the pile:

Follow two of them, >= 233 and >= 250, through our code.

For >= 233, split_rows walks all five rows and drops 210 into the False list and the other four into the True list. split_gain then calls gini on each, and gini walks the one-row pile counting labels, then the four-row pile counting labels. Five visits to split, five to count. For >= 250 it begins again from the same five rows, and so on down the list:

>= 233:  split_rows 5 rows → gini({210}) + gini({233,250,286,300})   = 10 visits
>= 250:  split_rows 5 rows → gini({210,233}) + gini({250,286,300})   = 10 visits
>= 286:  split_rows 5 rows → gini({210,233,250}) + gini({286,300})   = 10 visits
>= 300:  split_rows 5 rows → gini({210,233,250,286}) + gini({300})   = 10 visits

Forty row visits, and nothing is carried between the lines — even though each pair of piles differs from the pair above it by exactly one row.

Here are those same five rows, sorted by cholesterol and carrying the disease label each patient turned out to have, which is how a real implementation would hold them:

Real implementations get both answers out of the first walk. Sort the rows by the feature, and then, while evaluating the very first candidate, pass through them once keeping a running tally of the labels seen so far — by the end of that single pass every later candidate has been answered too:

Every line is the line above it plus the label of the row just walked past: 210 is a No, so the tally opens at {No: 1}; 233 is another No, taking it to {No: 2}; 250 is a Yes, adding the first Yes; and so on. One increment per row, five rows, one pass.

Because the rows arrive in ascending order, each of those tallies is also the group falling below a particular threshold — which is what turns it into an answer:

Since the gain formula weighs both children, both groups are needed — but only the first is tracked as the sweep advances. The group at or above the threshold never needs counting; it can be derived. The node’s own totals were worked out when it was created — {No: 2, Yes: 3} here — so whatever is not below the threshold is above it. Neither question re-reads anything — two lookups and a subtraction each, with Gini following from four integers.

For $n$ rows and $d$ features, the naive search can take $O(dn^2)$ work at one node. Sorting each numeric feature and sweeping through it reduces this to roughly $O(dn\log n)$ including sorting, for a fixed number of classes. Once sorted, each sweep is linear. This is a per-node comparison; the cost of building the whole tree also depends on its shape.