How to build a decision tree from scratch

Neural networks are great for unstructured data — pixels, waveforms, sequences of characters — the kind where a single input value tells you nothing by itself. Give a deep network enough of it and it learns its own features, pixel patterns and word meanings and audio textures that would be very difficult to hand-craft, then draws whatever boundary between the classes the data calls for, however intricate.

But an enormous share of real-world machine learning does not run on data like that. It runs on tabular data — data that lives in a table, the shape of a spreadsheet or a database query result. Each row represents one sample or observation — a transaction, a patient, a delivery, a player; each column is a feature with a name and a meaning of its own.

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.

The method that wins most often on data shaped like this is gradient boosting: train one small model after another, each one correcting the errors its predecessors left behind. The recipe does not care what that small model is, but in practice the combination of gradient boosting and decision trees shows the best results on tabular data. A decision tree is a model that predicts by asking questions about the columns and following the answers down to a verdict; boosting, like a random forest, is an ensemble — hundreds of trees whose answers are combined into one, which beats any single tree.

Usually you meet gradient boosting under the name of an implementation rather than the method — XGBoost, with its siblings LightGBM and CatBoost — and even in the age of LLMs those quietly run a remarkable share of production ML. Uber estimates arrival times with distributed XGBoost, Stripe catches fraud rings with it, and Dropbox runs an XGBoost ranker inside its LLM-powered enterprise search.

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 changes.

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.

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:

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 in the source file) is a thallium stress test, which images blood flow to the heart muscle at rest and under exertion: normal means flow looks fine, a fixed defect is starved in both states — tissue already dead from an earlier heart attack — and a reversable defect is starved only under exertion, a narrowed but still-living vessel. vessels (Ca) is how many major coronary vessels, 0 to 3, showed up as diseased under fluoroscopy.

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 one question that decides the branching logic, with two edges leading out of it, True and False, and every row that arrives gets sent down one of them. Depending on the algorithm, a node can have more than two branches: ID3 and C4.5 would give stress_test one branch per value and fan it into three children at once. We are implementing CART, which only ever asks yes/no questions, so two edges is all a node here will ever have. That is also what every mainstream implementation uses — binary splits scored by an impurity measure — from sklearn’s DecisionTreeClassifier to the trees inside random forests and XGBoost.

The boxes are leaves: a path ends there, nothing more is asked, and all the leaf holds is a count of the labels carried by the training patients who came down that same path. Those counts are its answer to any new patient who lands there — which is why the boxes above read Yes: 2, Yes: 1, No: 1, and No: 1: two patients with a diseased vessel, both with the disease; two who are indistinguishable and disagree; one clear case without it. Divide those counts by their total and you have a probability: 100% Yes in the first leaf, 100% No in the last, and 50/50 in the middle one.

Those two node types are the whole model: decision nodes route a row, leaves answer it, and every patient entering at the top ends up in exactly one leaf. A decision tree partitions the rows of a table into groups — and those groups can be drawn, as regions of the space of every possible (stress test, vessel count) pair. Drawn, they give a tree its signature look: every boundary a cut parallel to an axis, because every question names one column and one value. Below it sits beside three other ways of separating the same points — a straight line, the smooth curve a neural network would bend through them, and the ragged outline k-nearest-neighbours gets by having each location polled by the training points closest to it.

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.

Besides those, we need a rule for when to stop, since we usually do not want to keep splitting until every row has a leaf of its own. Left alone that is exactly where it ends up, because splitting only runs out when no question divides a pile any further. Such a tree has stored the table rather than learned from it: a leaf holding a single training patient can only repeat that patient’s outcome, so any new patient routed there gets one person’s result rather than a pattern seen across many.

From rows to questions

Every decision node holds a question, so building a tree means choosing questions. To build the list of candidates, pair every feature with every value that feature takes in the data — each pair is one question. The column’s type picks the comparison. A categorical column asks for an exact match — Is stress_test == fixed? is true for the fixed-defect patients and nobody else. A numeric column asks for a threshold instead — Is vessels >= 1? is true for a patient with 1 diseased vessel and for every patient above that, which is what makes the value a cut point on a number line rather than a name to match.

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:

One column, one value, one comparison: that is all a question ever is, here and on any other dataset. CART never joins two conditions into a single question, e.g. stress_test == normal AND vessels >= 1, never weighs one column against another, and never uses a value that is not present in the dataset — no vessels >= 1.5 sitting between two observed counts, and no vessels >= 3 either, because 3 never appears in our five-row dataset.

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 Question holds a column index plus a value, and its match method decides which of the two comparisons applies by looking at the type of the value it finds:

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

    def match(self, example):
        val = example[self.column]
        if is_numeric(val):
            return val >= self.value      # numeric: threshold
        else:
            return val == self.value      # categorical: equality

    def __repr__(self):
        condition = ">=" if is_numeric(self.value) else "=="
        return "Is %s %s %s?" % (header[self.column], condition, str(self.value))

def is_numeric(value):
    return isinstance(value, int) or isinstance(value, float)

There are several ways to implement that matching logic. Ours is the three-line is_numeric branch inside match, 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’s tree requires numeric input, so stress_test has to be one-hot encoded first — one 0/1 column per value:

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, CatBoost and XGBoost split on subsets: they test 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}?

Measuring the diversity of a dataset

We now know how to build the list of candidate questions, so the next thing to understand is how to score them and decide which one becomes the node’s question. For that we need a measure of how mixed a pile of labels is, called Gini impurity, and a way to score each question by how much unmixing it does — how much less mixed its two piles come out than the pile they came from. That score is called information gain, and the question with the most of it wins.

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?

One way to come up with such a number would be to sample: pick two items at random, note whether they are the same kind or different kinds, put them back, and repeat. The fraction of pairs that come back different is an estimate of how mixed the set is, and it requires knowing nothing about the set beyond what the draws happen to show.

Suppose we did it ten times on each set. This is the result we got:

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:

And the number behaves the way we wanted it to. The smaller it is, the more often two random picks came back the same kind — the more uniform the set. The larger it is, the more often they differed — the more diverse the set. The estimate also sharpens the longer you keep drawing: ten pairs is already enough to separate these two sets, and a hundred would pin each number down. Keep drawing and it settles onto one exact 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 statistic is older than machine learning and turns up in other fields under other names — Simpson’s index in ecology, the Herfindahl–Hirschman index in economics.

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 class_counts(rows):
    """Counts the number of each type of example in a dataset."""
    counts = {}  # label -> count
    for row in rows:
        label = row[-1]  # the label is always the last column
        if label not in counts:
            counts[label] = 0
        counts[label] += 1
    return counts

The initial run over the entire dataset, class_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 — four lines of Python:

def gini(rows):
    """Calculate the Gini Impurity for a list of rows."""
    counts = class_counts(rows)
    impurity = 1
    for lbl in counts:
        prob_of_lbl = counts[lbl] / float(len(rows))
        impurity -= prob_of_lbl**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.

Information gain — scoring a split

Our goal is to score questions, and we now know how to compute the impurity of a pile of rows. So what we can do is make a split using a candidate question, measure the impurity of each of the two piles it produces, and compare that with what we started with. This is the recipe for information gain, the score we use to judge a question by.

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.

Read it as a transaction in uncertainty. In the diversity vocabulary of the previous section, the weighted sum is the diversity remaining after the split, and the gain is the diversity removed by asking the question. A gain of 0 means the two piles are just as mixed as the one they came from, so the question separated nothing; a question whose two children both come out pure removed every bit of mixing there was. So we are hunting for the questions with the largest gain — the ones that buy the most diversity removed for the one question they cost.

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. partition performs step 1, sorting the rows into the two piles a question makes, and info_gain performs steps 2 to 4, scoring what came out against what went in:

def partition(rows, question):
    """Split rows into those matching the question, and those that don't."""
    true_rows, false_rows = [], []
    for row in rows:
        if question.match(row):
            true_rows.append(row)
        else:
            false_rows.append(row)
    return true_rows, false_rows

def info_gain(left, right, current_uncertainty):
    p = float(len(left)) / (len(left) + len(right))
    return current_uncertainty - p * gini(left) - (1 - p) * gini(right)

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

Calling the algorithm greedy means it decides each split by looking only at the pile in front of it. It takes whichever question scores best right there, and then never returns to it: the choice is not revisited when the children turn out badly, and it is never coordinated with splits made elsewhere in the tree. Locally best at every step, with no guarantee that the finished tree is the best tree — and the next section shows how little it takes to expose the gap, when two root questions score exactly the same and the choice between them changes everything below.

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 find_best_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 Question out of the column and the value;
2. partition the rows with it, into the two piles it makes;
3. score those piles with info_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 find_best_split(rows):
    best_gain = 0
    best_question = None
    current_uncertainty = gini(rows)
    n_features = len(rows[0]) - 1

    for col in range(n_features):
        values = set([row[col] for row in rows])
        for val in values:
            question = Question(col, val)
            true_rows, false_rows = partition(rows, question)

            if len(true_rows) == 0 or len(false_rows) == 0:
                continue  # this split doesn't divide the data

            gain = info_gain(true_rows, false_rows, current_uncertainty)

            if gain >= best_gain:
                best_gain, best_question = gain, question

    return best_gain, best_question

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 len(true_rows) == 0 or len(false_rows) == 0 guard drops it before info_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. Ties and near-ties are common on real data, and when that happens, the later candidate overwrites the earlier one. That behaviour 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 >= best_gain:

Ties and near-ties turn up constantly on real data, and that is what makes this quirk a problem. Nothing in the data preferred vessels to stress_test — a comparison operator did, and since this is the root, everything below it is built on that choice. A small change to the rows is enough to flip a near-tie and reorganize the whole subtree underneath. That is what makes a single tree a high-variance model: its shape depends on the particular sample it was trained on. We return to it near the end of the article, where it is one of the two failures that explain why one tree is rarely the model you ship.

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 Decision_Node holds a question and two branches. In the textbook’s vocabulary, the question is a splitting rule — one predicate on one feature — 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 — find_best_split learns those rules, and the nodes are where the chosen ones live.

class Leaf:
    def __init__(self, rows):
        self.predictions = class_counts(rows)

class Decision_Node:
    def __init__(self, question, true_branch, false_branch):
        self.question = question
        self.true_branch = true_branch
        self.false_branch = false_branch

def build_tree(rows):
    gain, question = find_best_split(rows)

    if gain == 0:
        return Leaf(rows)          # base case: no question helps anymore

    true_rows, false_rows = partition(rows, question)
    true_branch = build_tree(true_rows)
    false_branch = build_tree(false_rows)

    return Decision_Node(question, true_branch, false_branch)

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 came out two questions deep, with three leaves. Let’s read it top to bottom, starting at the root: vessels >= 1, the winner of the tie. Every patient with a diseased vessel has heart disease, and that branch terminates immediately at a pure leaf, both of them, done in one question.

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.

This process of scoring questions, splitting the pile on the winner and recursing is essentially the training procedure. A neural network’s architecture is designed upfront, layer counts and widths and wiring, and gradient descent nudges the values inside that fixed frame thousands of times. A tree has no fixed frame and nothing that gets nudged: training invents which feature each node asks about, at what threshold, in what order, and how deep. A neural network trains the values inside a fixed structure; a tree trains the structure itself, and its values fall out as summaries — counts of whichever rows happened to arrive. There were no epochs and no convergence: each node scored its candidates once, kept the highest, and never revisited the choice, so when the root call of build_tree returned, training was over. The model never got gradually better; it got gradually built.

Classifying — reading the probability off a leaf

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

def classify(row, node):
    if isinstance(node, Leaf):
        return node.predictions

    if node.question.match(row):
        return classify(row, node.true_branch)
    else:
        return classify(row, node.false_branch)

def print_leaf(counts):
    total = sum(counts.values()) * 1.0
    return {lbl: str(int(counts[lbl] / total * 100)) + "%" for lbl in counts}

Each Decision_Node stores one Question — a column index plus a value — and match compares the row’s entry in that column against it, returning a plain True or False. That boolean is the only thing classify needs: True sends the row down true_branch, False down false_branch, 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?; match 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?; match 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 classify returns the counts stored there: one Yes and one No.

Those counts returned by classify 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 print_leaf does here.

For this particular patient the counts are one of each, so the two readings are “no majority” and “50/50” — the same fact, twice. And 50/50 is the right answer to give: two training patients have exactly those features and disagree, so a model claiming certainty would be lying, which in this domain is not a figure of speech. That is irreducible error, and the leaf counts report it for free, without any extra machinery for uncertainty.

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.

Which is why the number of decision nodes and the number of features are independent. The features only supply the menu; the data decides which questions get asked and how often — and that menu is rebuilt at every node rather than fixed once for the whole tree. find_best_split reads it off the rows in front of it, values = set([row[col] for row in rows]), so the list of candidate questions shrinks as the piles do: our root can ask Is vessels >= 2?, but the node below it cannot, because no row that reached there has a 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.

But cleaning the training data does not close the gap, because a patient arriving tomorrow can still carry a stress_test value the tree has never seen. The == comparison that match uses on a categorical column fails, the row slides down the False branch, and the answer comes back looking exactly like a well-founded one. That silence is the real defect — not that the tree is wrong, but that nothing in {'No': '100%'} distinguishes three confident training rows from a value the model has never encountered.

Real tree libraries are designed to handle missing values without any pre-processing of the dataset. XGBoost learns a default direction per split, sending the rows it cannot answer whichever way scored better on the training data, and CART’s original formulation keeps surrogate splits — backup questions correlated with the primary one, asked of any row that cannot answer it.

Why one tree is not the end of the story

The model we have built is real CART, in about 200 lines of pure Python, and if you point it at real data it will grow you a real tree. However, there are two problems with our implementation, and the rest of the tree world exists to deal with them.

First, the tree will overfit if nothing stops it growing. Overfitting is a model memorising its training data instead of learning from it, and so losing the ability to generalise to anything else. In a neural network it happens through the weights: given enough capacity and too little regularisation, gradient descent keeps adjusting them until the network reproduces its training set almost exactly. In a tree it happens through the splitting: left unchecked, build_tree keeps cutting until it has handed almost every training row a pure leaf of its own, because gain == 0 is the only thing that stops it. The capacity axis is not how long you trained but how deep you grew, which is why every regularizer for trees is structural — depth limits, minimum leaf sizes, pruning.

Let’s see how this problem manifests itself on a real dataset, using sklearn as a fair stand-in for our code here: leave DecisionTreeClassifier(criterion="gini") at its defaults — no depth limit, no minimum leaf size, no pruning — and it has no stopping rule but purity either, so the tree it grows is the tree build_tree would grow, only computed faster.

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 (what build_tree does)
  depth      7
  leaves     19
  train acc  1.000
  test acc   0.912

Accuracy here is simply the fraction of rows whose predicted label matches the recorded one — measured on the 398 rows the tree was built from, and again on the 171 it never saw. Train accuracy 1.000 therefore means it got all 398 right, which it managed by splitting until the stragglers — the rows that refused to group with anything else — each sat in a leaf of their own: the same gain == 0 behaviour we watched on the five patients, with 398 rows instead of 5.

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:

Read the last two rows against each other, because this is the whole lesson. Going from depth 2 to depth 7 improves training accuracy from 0.960 to 1.000 and makes the model worse — test accuracy falls from 0.947 to 0.912. The unpruned tree is not merely wasteful. It is beaten by a tree one third its depth, one that gets 4% of the training data wrong. Those extra five levels of depth are the tree memorizing 398 specific rows, and build_tree has no way to know it, because from the inside every one of those splits reduced impurity.

The second problem is that the tree is unstable — change the data a little and it can come out a different shape. Which brings us back to the >= we used to compare each candidate’s gain against the best seen so far, and to the order the loop happens to visit those candidates in. Greedy scoring produces ties and near-ties constantly on real data, and which side wins comes down to an undocumented implementation detail — you watched it happen at the root, two questions with identical scores and one character deciding between them. Point the same code at the full Cleveland study — the 297 patients with no missing values, all thirteen predictors, 207 rows for training and 90 held out — and at ten of the finished tree’s 35 decision nodes two candidate questions score exactly the same while cutting the patients into different piles. Nothing in the data separates them, so whichever one the algorithm keeps is arbitrary — and anything that disturbs the scores flips the choice and rebuilds everything below it.

And the cost lands on real patients. Delete a single training row and refit, and the tree that comes back sends as many as 12 of the 90 held-out patients home with a different diagnosis. Change nothing at all and the predictions still move — find_best_split visits tied candidates in whatever order a set iterates, which differs from run to run, so ten runs on identical patients gave four distinct models, disagreeing with one another on up to 4 of the 90 diagnoses. Two runs on the same data hand you two different models, both of them correct by the algorithm’s own lights.

Those two behaviours 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.

The two move in opposite directions as a method gets more flexible, and for a tree, flexibility is depth. Keep it shallow and it is too simple to capture the pattern — high bias — but steady: train it on another sample and roughly the same tree comes back. Let it grow and it can fit anything, noise included — low bias — at the cost of exactly the instability described above, which is variance. Training accuracy only ever rewards the first of the two, since a deeper tree always fits its own rows better, while test accuracy answers to both — which is why it peaks at depth 2 in the table and slides from there. And no depth can drive test error to zero, because underneath both terms sits the irreducible error we met at the 50/50 leaf — the part of the outcome the features simply do not determine.

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.

Let’s look at the one solution that applies at the level of a single tree — pruning, which amounts to replacing gain == 0 with a stopping rule that knows when to quit. The remedies come in two named families. Pre-pruning (early stopping) refuses to grow in the first place: max_depth, minimum rows per split or per leaf, minimum gain thresholds — the depth slider above was pre-pruning at its crudest. It is cheap, but greedy in a second way: a weak split can be the doorway to a strong one below it, and a tree stopped early never finds out (known as the horizon effect). Post-pruning lets the tree grow fully and then cuts back the branches that do not pay for themselves on held-out data; CART’s canonical version is cost-complexity pruning: score the tree as its error plus a price per leaf, and cut back whatever fails to earn its keep. That is the tree’s loss function finally made explicit — fit term plus complexity penalty, the same shape regularisation takes anywhere else — and sklearn exposes the price as ccp_alpha.

Instability is not usually fixed within a single tree at all. Instead of looking for a smarter tiebreak, you stop relying on one tree. Grow many of them, each on a slightly different sample of the rows and columns, so they land on different sides of the ties, then average their answers: that is a random forest, and averaging is what cancels the variance. Grow them in sequence instead, each correcting what the last got wrong, and that is gradient boosting, where the correcting is what works off the bias.

Where our version is slower than a real one

There is one important optimization technique missing from our implementation, and every real library has it. Everything else matches what a production implementation does — the same candidate questions, the same impurity, the same gain, the same split chosen — but find_best_split as we wrote it is brute force in the literal sense.

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: partition walks every row to sort it into two piles, and info_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, partition walks all five rows and drops 210 into the False list and the other four into the True list. info_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:  partition 5 rows → gini({210}) + gini({233,250,286,300})   = 10 visits
>= 250:  partition 5 rows → gini({210,233}) + gini({250,286,300})   = 10 visits
>= 286:  partition 5 rows → gini({210,233,250}) + gini({286,300})   = 10 visits
>= 300:  partition 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.

One such table is built per feature, since each column has its own ordering and its own thresholds: sort by cholesterol and sweep it, then sort by age and sweep that, and so on, with the best line across all the tables becoming the node’s question. That is the whole difference. Our version pays one full pass per candidate; the sweep pays one pass per feature and then reads every candidate off the table it built on the way. At five rows this is invisible; at a hundred thousand it is the difference between a second and a week.