Decision Tree

How an algorithm classifies through "yes/no" questions – and why too many questions make it dumb.

Imagine a doctor in the ER: "Fever, yes or no?" — if yes, then "Cough?". Every question splits the patients into two groups until a diagnosis emerges. Nobody has to process all symptoms at once — the path through the questions yields the answer.

A decision tree does exactly that. It asks a series of simple yes/no questions about the features of the data points and slices them step by step into ever purer groups. The result: a tree of questions a human can actually read.

Analogy:

Definition:

A binary decision tree learns from labeled data where and on which features to cut so that the resulting groups are as pure as possible. Per node a greedy algorithm picks the split that reduces the impurity of the child groups the most — measured with Gini impurity or entropy.

The information gain is the difference between the parent node's impurity and the weighted impurity of its two children. Recursion stops when a node is pure, the maximum depth is reached, or too few samples remain. Predictions are made by routing a new point from the root through the tree until it lands in a leaf.

The tree is built node by node — every step is almost embarrassingly simple. Repeated, that is what you see in the demo:

Split — the best cut
For each node the algorithm tries every possible threshold in every feature and picks the cut with the highest information gain. The node remembers "feature x ≤ threshold" and divides the data into two halves.
Purity — Gini or entropy
Gini impurity measures the probability of misclassifying a randomly drawn sample: 0 for a pure node, 0.5 for a 50/50 mix. Entropy measures the same thing in bits. Both push the tree to produce groups that are as homogeneous as possible.
Stop — when does the tree stop growing?
Without a brake the tree would put every single point into its own leaf — memorizing every speck of noise. So it stops at the maximum depth, when too few samples remain in a node, or when a node is already pure.

This is the trade-off: too few splits and the tree cannot separate the pattern (underfitting); too many and it memorises noise instead of generalising (overfitting). The demo shows both directly — the overfitting gap between training and test accuracy tells you when you have gone too far.

Click on the surface to set points. Tune the depth and watch the tree carve the plane into ever finer pieces – until it memorises every speck of noise.

Guided tour

New to the topic? Follow the tour step by step – or jump straight into free experimentation.

What this demo shows

Two views side by side make it visible how a tree of questions carves a surface into regions. Here is what you see on screen.

Classification surface

Place at least 4 points or load a dataset.

Class AClass BDecision boundaryTest point

Learned tree

Showing the complete tree. Hit ▶ to watch it grow split by split.

No data – set a few points or pick a dataset.

Points

Leaves

Depth

–

Train accuracy

–

Test accuracy

Overfitting gap

Dataset

Max depth: 4

Min samples / split: 2

Split criterion

Gini

Entropy

Both measure how "mixed" a node still is – Gini is faster to compute, entropy measures in bits. Which splits the tree picks is almost always identical. Toggle and compare. Train ratio: 80%

Theory

Pseudocode

Step by step

Flow diagram

A tree of yes/no questions

A binary decision tree classifies data points by a chain of simple threshold tests. At each node a feature and a threshold are chosen: everything below the threshold goes left, everything above goes right. That way the tree carves the feature space into axis-aligned rectangles — each leaf yields a prediction.

Information gain — the best cut

To stop the tree from growing arbitrarily, a greedy algorithm picks at each node the split that reduces impurity the most. Impurity measures are:

Gini impurity: 1 − Σ p_k² — probability of misclassifying a randomly drawn sample
Entropy: −Σ p_k · log₂ p_k — information content of the class distribution in bits

Information gain = impurity(parent) − (n_L/n)·impurity(left) − (n_R/n)·impurity(right). The algorithm tries every feature and every possible threshold and picks the one with the highest gain.

Stop criteria

Recursion stops when one of these holds:

The node is pure (all points belong to the same class)
The maximum depth has been reached
The node holds fewer samples than the minimum required for a split
No split has positive gain (no cut improves purity)

Bias-variance trade-off

Shallow (depth 1–3): high bias, the tree cannot separate the pattern → underfitting
Medium (depth 4–6): good balance, train and test accuracy stay close
Deep (depth ≥ 8): high variance, the tree memorises noise → overfitting

Play in the demo! Crank max depth up — the overfitting gap between train and test accuracy reveals the moment the tree starts memorising instead of learning.

English

                      
                        
                          1
                          # Decision tree — recursive build
                        
                      
                        
                          2
                          function build_tree(data, depth):
                        
                      
                        
                          3
                              # 1. Check stop criteria
                        
                      
                        
                          4
                              if depth == maxDepth or pure(data) or |data| < minSamples:
                        
                      
                        
                          5
                                  return leaf(majority_class(data))
                        
                      
                        
                          6
                           
                        
                      
                        
                          7
                              # 2. Find the best split (highest information gain)
                        
                      
                        
                          8
                              best = argmax over (feature, threshold) of gain(data, feature, threshold)
                        
                      
                        
                          9
                              if best.gain <= 0:
                        
                      
                        
                          10
                                  return leaf(majority_class(data))
                        
                      
                        
                          11
                           
                        
                      
                        
                          12
                              # 3. Partition data at the split
                        
                      
                        
                          13
                              left  = { d in data | d.feature <= best.threshold }
                        
                      
                        
                          14
                              right = { d in data | d.feature  > best.threshold }
                        
                      
                        
                          15
                           
                        
                      
                        
                          16
                              # 4. Recursion: build children
                        
                      
                        
                          17
                              return node(best, build_tree(left, depth+1), build_tree(right, depth+1))

1 / 5

🛑 Check stop criteria

Before doing anything else: does the current dataset fit a leaf? If depth is maxed out, the node is pure, or too few samples remain, the algorithm returns a leaf with the majority class. No further recursion.

    # 1. Check stop criteria
    if depth == maxDepth or pure(data) or |data| < minSamples:
        return leaf(majority_class(data))

Decision trees aren't just a teaching example — they run wherever decisions need to be traceable:

Credit scoring

Banks decide on a loan based on income, debt and history. The tree delivers the reasoning along with the verdict — crucial, since rejections must be legally explainable.

Medical triage & diagnosis

A chain of symptom questions leads to a suspected diagnosis or urgency level — a path that clinicians can read without any AI knowledge.

Customer analytics

Which customers are likely to churn? Which segment responds to an offer? Trees segment tabular data quickly and explainably.

Random forests & gradient boosting

Hundreds of averaged trees form random forests and XGBoost — still the strongest models for structured tabular data and perennial winners of data-science competitions.

The deeper the tree, the better the model.

More depth only raises training accuracy. Past a point the tree memorises noise (overfitting) — what matters is test accuracy, not depth.

A decision tree is always easy to interpret.

Only while it stays small. A tree with hundreds of nodes is, in practice, just as opaque to humans as a neural network.

Features must be normalised before training.

Not needed: trees compare individual thresholds per feature and are therefore scale-invariant — unlike, say, a perceptron or k-means.

A tree can draw any boundary you like.

Splits are always perpendicular to an axis. Diagonal or circular boundaries (see the "Spiral" dataset) are only approximated in a staircase pattern — with many small cuts.

What does Gini impurity measure in a node?

The depth of the node in the tree.

The probability of misclassifying a randomly drawn sample — i.e. how mixed the classes inside the node are.

The number of data points assigned to the node.

The threshold at which the node splits.

1. What does Gini impurity measure in a node?

☐ A) The depth of the node in the tree.
☐ B) The probability of misclassifying a randomly drawn sample — i.e. how mixed the classes inside the node are.
☐ C) The number of data points assigned to the node.
☐ D) The threshold at which the node splits.

2. What happens in this demo if you crank max depth very high (e.g. 10) with enough points placed?

☐ A) Train accuracy climbs to almost 100 %, test accuracy drops — the tree memorises noise.
☐ B) Both accuracies rise to 100 % in lockstep.
☐ C) The tree aborts because it hits the maximum number of nodes.
☐ D) The decision boundary becomes smoother because the tree sees more data.

3. Why are decision trees considered "interpretable", unlike e.g. neural networks?

☐ A) They only use integer thresholds.
☐ B) They are always 100 % accurate on new data.
☐ C) Every prediction corresponds to a readable chain of if-then questions a human can actually follow.
☐ D) They do not need any training data.

4. How does a random forest improve on a single decision tree?

☐ A) It makes the single tree deeper.
☐ B) It trains many trees on random sub-samples of data and features and averages their predictions — that lowers variance.
☐ C) It removes every leaf that has only one class.
☐ D) It replaces Gini with a neural network per node.

Answer Key: 1) B · 2) A · 3) C · 4) B

Questions, not formulasA decision tree classifies through a chain of simple yes/no threshold questions; every path from root to leaf reads as an if-then rule.
Purity drives the splitsAt each node the greedy algorithm picks the cut with the highest information gain, i.e. the largest drop in impurity (Gini or entropy).
Depth is a trade-offToo shallow underfits, too deep overfits. The gap between training and test accuracy (the overfitting gap) shows when you've gone too far.
Axis-aligned & scale-invariantCuts are perpendicular to an axis; curved boundaries are only approximated in steps. In return, no feature normalisation is required.
Strongest in a crowdRandom forests and gradient boosting average many trees and rank among the best methods for tabular data anywhere.

Decision Tree

What is a decision tree?

Analogy:

Definition:

Question by question to a class

Split — the best cut

Purity — Gini or entropy

Stop — when does the tree stop growing?

Interactive demo

What this demo shows

Classification surface

Learned tree

Decision Tree — how the tree grows

A tree of yes/no questions

Information gain — the best cut

Stop criteria

Bias-variance trade-off

🛑 Check stop criteria

🛑 Stop criteria

🔍 Best split

⛔ No gain?

↔️ Partition

🔄 Recursion

Where decision trees show up in the real world

Credit scoring

Medical triage & diagnosis

Customer analytics

Random forests & gradient boosting

Common misconceptions

Test your understanding

What does Gini impurity measure in a node?

The essentials in five points

What is a decision tree?

Analogy:

Definition:

Question by question to a class

Split — the best cut

Purity — Gini or entropy

Stop — when does the tree stop growing?

Interactive demo

What this demo shows

Classification surface

Learned tree

Decision Tree — how the tree grows

A tree of yes/no questions

Information gain — the best cut

Stop criteria

Bias-variance trade-off

🛑 Check stop criteria

🛑 Stop criteria

🔍 Best split

⛔ No gain?

↔️ Partition

🔄 Recursion

Where decision trees show up in the real world

Credit scoring

Medical triage & diagnosis

Customer analytics

Random forests & gradient boosting

Common misconceptions

Test your understanding

What does Gini impurity measure in a node?

The essentials in five points

Related Content

Article

Bayes & Conditional Probability

Bias & Data Quality

Linear & Logistic Regression

Programming vs. Training

How Good Is Your Model? Metrics That Actually Matter

When the Model Memorizes (Overfitting)

Supervised Learning — Learning with a Teacher

What Is an Algorithm?

Demo

Naive Bayes (Classification)

Neural Network Playground

Perceptron (Neural Networks)

Supervised Learning

Glossary