How to invent the decision tree algorithm from scratch

Part one · build it by hand

Machine learning is not one single method

When people say machine learning, it can sound like the name of one technology. It is closer to a toolbox. The field is full of different algorithms, and each one learns patterns from examples in its own way, then uses those patterns to make predictions about examples it has never seen.

Neural networks are the famous family. They are behind striking results in text, images, audio, and video. But fame is not the same as fit. A great deal of everyday data lives in tables — customers, houses, plants, loans, medical measurements — and on tables, tree-based methods are often the strong, practical choice. To see why, start with what makes a table different from other data.

Each row describes one thing

A sentence is a sequence of words: order matters. An image is a grid of pixels: position matters. In our seed table, each row describes one seed, and the columns record named properties of that seed. Shuffling these rows would not change their meaning because no seed depends on the row before it.

Think about people at a party. One person is tall, blond, and wearing glasses. Another is short, brunette, without glasses. This kind of data invites yes-or-no questions — is the person tall? are they wearing glasses? — and each answer divides the group in two. A table works the same way: a question about one column sends some rows one way and the rest the other way.

Hold on to that observation. Small questions are a natural way to organize tabular data, and — as we are about to see — they may be enough to predict something we do not know yet.

Our running example

Ten seeds and one prediction

Imagine we planted ten seeds. Each one received a certain number of sunlight hours per day and a certain number of liters of water per week. At the end of the experiment, each seed was either thriving or struggling.

Entity

one seed

Features

sunlight and water

Label

thriving or struggling

Now a friend brings us seed K. It will get 3 hours of sunlight per dayand 2 liters of water per week. Can the ten old seeds help us predict what will happen to the new one?

This task is called classification: we are not predicting an exact height, we are choosing between two labels — thriving or struggling.

The first invention

A split is a question

Staring at the table row by row is hard, so let us spread it across two axes. Sunlight runs left to right, water runs bottom to top. Circles are thriving seeds; squares are struggling seeds.

A line on this graph can act like a yes-or-no question. A vertical line asks whether sunlight is at most some cutoff. A horizontal line asks the same kind of question about water. We have not chosen the feature or cutoff yet.

Your first job is only visual: find one line that leaves circles and squares less mixed on its two sides. There may be several reasonable attempts. Commit to one before asking the playground for its clearest answer.

The reveal checks every available position and returnssunlight ≤ 3.5 hours. Seeds A through E answer yes: four are thriving and D is struggling. The other five answer no, and all five are struggling.

That question turned one mixed group into two less-mixed groups. The right group is finished because every seed in it struggles. The left group still contains both outcomes, so it needs another question. A cutoff such as 3.5 is called athreshold. A feature-and-threshold question that divides a group is called a split.

Turn one question into a structure

A mixed region can answer another question

One line is only the beginning. After a question divides the graph, each region holds a smaller version of the original problem. A region where every seed has the same outcome can stop. A mixed region can ask another question — using only the seeds inside it.

This is where lines become a tree. In the playground below, select a region, choose a feature, and cut only that region. The panel on the right records the exact same sequence of questions as a branching structure: the first cut is the root, each later cut hangs under the answer that led to it.

The pivot of this lesson

Stop and look at what you just did

Whether you completed the tree yourself or opened the guided solution, the construction used no formula. A node is a question, its two answers are branches, and every final region is a leaf that makes a prediction. The construction used exactly three skills:

1. Propose. You slid a line across a region and it snapped between neighboring seeds.
2. Judge. You looked at both sides and decided whether the outcomes became more alike.
3. Repeat. Inside any region that stayed mixed, you did the same thing again.

Two of those skills are mechanical. Proposing lines is a loop over positions. Repeating is the same procedure applied to a smaller group. A computer can do both without any insight.

The third skill is the obstacle. “This side looks cleaner” is a judgment, not an instruction. To automate the whole process, we need to replace your eyes with a number — one score that says how well did this question separate the outcomes? That single replacement is the entire second half of this lesson. Everything else, you have already invented.

Part two · automate it

Only a few questions are worth asking

Before scoring questions, we should count them. A threshold like 2.25 can feel arbitrary — why not 2.3, or 2.31? Look at the sunlight column: 2.0 and 2.5 are neighboring values. Every line drawn between them sends the same rows to the same sides. All those thresholds are the same question wearing different numbers, so we test just one of them: the midpoint.

This makes the search finite. Sort the distinct values of a column and take the midpoint of each neighboring pair: ten distinct values give nine candidate thresholds. Two features, nine thresholds each — at the root there are exactly18 questions worth testing, not infinitely many. The playgrounds above were already snapping your line to these midpoints.

So the computer can generate every question worth asking. What it still cannot do is pick the best one. “This looks cleaner” has to become a number.

Step one: measure the mixture of a single group

Forget splits for a moment and look at one group of seeds. What your eyes actually checked, side by side, was how mixed each group was. A useful mixture score should follow three rules:

1. A pure group scores 0. If every seed has the same outcome, there is no mixture.
2. An even mixture scores highest. A 50/50 group is as mixed as two classes can be.
3. Only the label counts matter. The score should not care where the seeds sit or what order they are in.

The standard choice for classification trees is Gini impurity, and it has a concrete meaning. Imagine drawing one seed label from a bowl, putting it back, and then drawing again. Putting it back keeps the odds the same on both draws. Gini is the chance that the two labels disagree.

Our full group has four thriving and six struggling seeds. Disagreement can happen in two orders. We can draw thriving and then struggling, or struggling and then thriving:

In a pure group, disagreement is impossible, so Gini is 0. In a two-class group split evenly, disagreement is as likely as it can be, so Gini reaches 0.5.

That is close to the maximum possible value of 0.5 for two classes. It does not mean a model is wrong 48% of the time — there is no model yet. It only means the group still contains a strong mixture of both labels.

Step two: score a question, not just a group

A question creates two groups, so we need to combine two Gini values into one score. Take the clearest first question, sunlight ≤ 3.5. The yes side has four thriving seeds and one struggling seed. The no side has five struggling seeds — pure, Gini 0:

Each side is weighted by the fraction of rows it received. Here the split happens to send five rows each way, so the weights are equal; the same rule also works when later splits create unequal groups:

Before the question, the group's Gini was 0.48. After it, the weighted mixture is 0.16. The improvement is called the Gini gain:

This is the number that replaces your eyes. A higher gain means the question removed more mixture. It uses nothing but label counts, so a computer can evaluate it for any candidate question in a few multiplications.

The score can compare any two candidates

To feel the score working, keep the feature fixed and move only the threshold. Before reading the numbers below, look at the two pictures and predict which question leaves less mixture behind.

The whole algorithm

Two loops and a memory

Now every ingredient is on the table, and the algorithm almost writes itself. At the current group of rows:

1. For each feature — sunlight, then water —
2. for each midpoint threshold of that feature,
3. compute the Gini gain of the question they form,
4. and remember the best one seen so far.

That is the entire search: two nested loops and one remembered winner. There is no cleverness inside — the computer does exactly what you did in the first playground, except it checks all 18 questions and refuses to have taste. Watch it run.

If you ran the search to the end, the numerical winner matched the pattern your eyes could see: sunlight ≤ 3.5 leaves all five high-sunlight seeds together in a pure struggling group and earns a gain of 0.320. The loop did not invent a new idea; it measured every possible line and confirmed the clearest one.

The third skill: repeat inside every mixed leaf

One search gives one question, and one question is not yet a tree. The winning split leaves F, G, H, I, and J in a pure struggling leaf — that side is done. The other side still holds both labels, so we run the exact same searchon A, B, C, D, and E alone. Water ≤ 3.1 separates D from the four thriving seeds, and every leaf is pure.

This pattern — a procedure that applies itself to the smaller problems it creates — is called recursion. The rule never changes; only the set of active rows shrinks. Step through it below and try to predict which group will split next.

The finished structure is worth a full look:

Compare it with the tree you built by hand. The computer may not have made your exact cuts, but it followed your exact method — and now the two vocabularies line up:

Stress the mechanism

The same small questions can build complex boundaries

The seed dataset ended after two questions because its pattern was unusually cooperative. The algorithm is not limited to two cuts. Each new question acts only inside one existing region, so vertical and horizontal lines can compose into stripes, staircases, boxes, and many smaller rectangles.

Choose a point pattern below and predict what the tree will need before you run it. Then step through the same Gini search you just learned: iterate overx and y, try every midpoint threshold, keep the largest gain, and repeat inside the remaining mixed regions.

The invariant is now easier to see. A more elaborate boundary does not require a more elaborate kind of question; it requires more rounds of the same search. The diagonal becomes a staircase because this tree only asks one-feature, axis-aligned questions. The center island needs nested cuts because no single vertical or horizontal question can isolate the middle group.

More splits also mean more chances to fit accidents in the training points. That is why tree complexity cannot grow without a stopping rule.

When should the tree stop?

Our toy data becomes pure after two questions. Real data is noisier, and a tree that keeps splitting can end up memorizing tiny accidents of the training set. Practical trees therefore stop growing a branch when any of these hold:

1. The node is pure. Every active row has the same label.
2. No split has positive gain. The available questions do not improve the group.
3. The depth limit is reached. We refuse to ask more nested questions.
4. Too few rows remain. We avoid making a rule from a fragile group.

When a branch stops, its leaf predicts the most common label among its rows. It can also keep the class counts: a leaf with eight thriving and two struggling seeds is less certain than a leaf with ten thriving seeds, even though both predict thriving.

The tree is greedy

At each node, the search keeps the best split it can see right now. It never asks whether a slightly worse first split might enable much better later splits — testing every possible complete tree would be astronomically expensive. This shortcut makes training fast, and its cost is honesty about the word “best”: the winning split is only the best local choice, under the current score, for the current rows.

Prediction travels through the finished questions

Training searched through many questions; prediction only answers the ones that survived. A new row starts at the root and follows one branch at a time until it lands in a leaf.

A perfect training result can be a warning

This tree classifies all ten training seeds correctly. That is convenient for teaching, because every step stays visible. On real data, perfection is often a symptom: the tree may have memorized the training rows instead of learning a pattern. This failure is called overfitting, and we detect it by testing on labeled data the tree never used while choosing its thresholds. Depth limits, minimum group sizes, minimum gain, and pruning all express the same principle: a new branch must earn its complexity.

Beyond the plane

More features, same two loops

Every playground so far used two features, and that was a choice of scenery, not of method. Two features fit on a screen, so each question could be drawn as a line. But look back at what the search actually consumed: it sorted one column, took midpoints, counted labels, and computed a gain. At no point did the algorithm look at the picture. It read columns.

So let it read more of them. The table below describes twelve greenhouse seedlings with three measurements each — sunlight, water, and temperature. A third feature would already need a three-dimensional graph, and a fourth would defeat drawing altogether. The table has no such limit, so this time the table itself is the data space.

Nothing in the recipe changes. For each feature — now three of them — and for each midpoint threshold of that feature, compute the Gini gain of the question they form and remember the best one seen so far. Twelve distinct values per column give eleven midpoints, so the root search tests exactly 3 × 11 = 33 candidates. Then the winning question divides the rows into two groups, and the same search runs again inside any group that stays mixed.

The winning root question came from the temperature column — a feature no two-dimensional graph of sunlight and water could even display. The loop did not need to know that in advance; temperature simply produced the largest gain, so the memory kept it. The recursion then ran twice more: inside the warm group, water separated the three underwatered seedlings, and inside the warm, watered group, sunlight isolated the single shaded one. Three searches, three features, four pure leaves — every column earned its node by winning one local search.

This is the entire generalization. The loop never asks how many columns the table has; it only asks for the next one. Ten features would mean ten lanes in the ledger and a longer loop — not a new idea. The two-feature graphs of this lesson were scaffolding for your eyes. The algorithm was reading the table all along.

Keep the smallest useful mental model

You built the tree first and met the algorithm second — and that order was the point. The formula did not introduce a new idea; Gini gain only turned the judgment your eyes were already making into a number a loop could maximize. The diagram was never the starting point. It was the result.