A credit-card company approves your $5,000 charge in 200ms. A doctor's triage tool decides if you wait 5 minutes or 5 hours. Both are decision trees. By the end, you'll build one by hand and understand exactly why it never explained more than 'if-then-else'.
Learning Objectives
After this lesson, you will be able to:
Understand how decision trees work — they ask a series of yes/no questions to narrow down to a prediction, like a flowchart
Calculate Gini impurity and information gain — the math that picks the best question to ask at each step
Know why trees without limits grow too big and memorize noise, and how to control them with max depth and pruning
Recognize that tree boundaries are always straight horizontal/vertical lines, which is sometimes a limitation
Explain when to prefer a single decision tree over an ensemble, and when to use regression trees instead of classification trees
Don't worry if Gini impurity and information gain sound intimidating — a decision tree is really just playing "20 Questions" with your data. It picks the best question at each step to narrow down the answer as fast as possible!
Playground:Scrolly Decision Tree → — scroll through a tree as it grows split-by-split, then jump to the Decision Boundary lab to see how trees carve feature space into rectangles.
The algorithm begins with all training examples in a single root node. At this point, the node contains a mix of classes -- for example, 60 cats and 40 dogs. The impurity is high because the classes are mixed. The tree's job is to ask the right questions to separate them.
Measure how mixed the current node is using Gini impurity or entropy. A pure node (all one class) has impurity 0. A 50/50 split has maximum impurity. This baseline impurity tells us how much room there is for improvement -- the tree will try to find a split that creates purer child nodes.
For every feature and every possible threshold, evaluate the information gain: how much would this split reduce impurity? The algorithm exhaustively tests all options -- "weight > 7kg?", "height > 30cm?" -- and selects the one that produces the purest child nodes. This greedy search is the computational core of tree building.
Apply the chosen split. Data points that satisfy the condition go left; the rest go right. Each child node now contains a subset of the original data, ideally with a more uniform class distribution than the parent. The feature space has been partitioned by an axis-aligned boundary.
Now watch the same algorithm play out on a real dataset, split by split, with the impurity dropping at each level.
Scrolly: watch a tree grow split-by-split, with Gini reported at each nodeInteractive
Loading visualization...
Quick check
During CART construction, the algorithm is scanning candidate splits at a node and finds one that produces Left child Gini = 0.0 and Right child Gini = 0.0. What does this tell the algorithm to do?
At each node, the tree considers every possible split of every feature and chooses the one that best separates the classes. "Best" is measured by an impurity metric -- how mixed are the classes in each resulting group?
Try it! Open the Python REPL and type these lines yourself. Train a tree and print its rules: from sklearn.tree import DecisionTreeClassifier, export_text; from sklearn.datasets import load_iris; X, y = load_iris(return_X_y=True); tree = DecisionTreeClassifier(max_depth=2).fit(X, y); print(export_text(tree, feature_names=load_iris().feature_names)) — you can read the yes/no questions!
For a binary classification with p being the proportion of class 1:
Information Gain is the reduction in entropy (or Gini) after a split:
IG(S,A)=H(S)−v∈values(A)∑∣S∣∣Sv∣H(Sv)
What Do You Think?
A dataset has 100 examples: 90 cats and 10 dogs. A split produces Left: 85 cats, 5 dogs and Right: 5 cats, 5 dogs. Is this a good split?
This is a decent but imperfect split. The left node (85/90 = 94% cats) is quite pure, but the right node (50/50) is maximally impure. A better split might achieve pure or near-pure nodes on both sides. The tree algorithm evaluates ALL possible splits and picks the one with the highest information gain.
Now we evaluate candidate splits. With 5 unique humidity values, midpoints are 55, 70, 82.5, 87.5.
Split humidity ≤ 70 → Left = {Day 2, Day 4} = (0 yes, 2 no), Gini = 0. Right = {Day 1, Day 3, Day 5} = (3 yes, 0 no), Gini = 0. Weighted child Gini = (2/5)·0 + (3/5)·0 = 0. Information gain = 0.48 − 0 = 0.48 (perfect split!).
Split temp ≤ 21 → Left = {Day 1, Day 3} = (2 yes, 0 no), Gini = 0. Right = {Day 2, Day 4, Day 5} = (1 yes, 2 no), Gini = 1 − (1/3)² − (2/3)² = 0.444. Weighted child Gini = (2/5)·0 + (3/5)·0.444 = 0.267. Information gain = 0.48 − 0.267 = 0.213.
humidity ≤ 70 wins with gain 0.48 vs. 0.213. The tree picks it, both children are pure, and we're done — total depth 1. This is exactly the algorithm sklearn runs at every node, on every feature, every time.
Run the same calculation end-to-end: train a depth-2 tree on Iris, print the rules, and verify the Gini / entropy at every node by hand. Feel free to swap criterion="gini" for "entropy" and watch which splits change.
Loading visualization...
Quick check
A node holds 80 cats and 20 dogs. Gini impurity is 1 − (0.8)² − (0.2)² = 0.32. Entropy is roughly 0.72 bits. Which is the better split criterion?
function BuildTree(data, features):
if all labels are the same: return Leaf(label)
if no features left or stopping criterion met: return Leaf(majority_label)
best_feature, best_threshold = find_best_split(data, features)
left_data = data where feature <= threshold
right_data = data where feature > threshold
left_child = BuildTree(left_data, features)
right_child = BuildTree(right_data, features)
return Node(best_feature, best_threshold, left_child, right_child)
Try it: Increase tree depth and watch rectangular regions appearInteractive
Loading visualization...
Try this: Observe how the decision tree creates axis-aligned (rectangular) boundaries. Each split is perpendicular to a feature axis. Compare this to the smooth boundaries you saw with logistic regression -- trees carve up the space into rectangular regions, each predicting the majority class within it. Increase the tree depth to see finer partitions.
Root split: The algorithm scans every feature at every possible threshold value. For a numeric feature with 100 unique values, it tests 99 possible split points. It picks the split that maximizes information gain across the entire dataset.
Second level: Each child node independently finds its best split. The left branch might split on a different feature than the right branch.
Recursive splitting: Each new node splits again, creating finer and finer partitions of the feature space.
Leaf creation: When a node is pure (all one class), has too few samples, or reaches the maximum depth, it becomes a leaf and outputs a prediction.
Grow the full tree, then prune back branches that do not improve validation performance. Scikit-learn uses cost-complexity pruning (ccp_alpha parameter).
ccp_alpha is the right knob, but most users treat it like a black box. The actual algorithm — Breiman's minimal cost-complexity pruning, the same one that ships in scikit-learn — has a beautifully principled story behind it. It is the only pruning rule that searches the entire regularization path and is provably the global optimum at every α.
Step 1: Define the penalized cost. Let R(T) be the training error of tree T and |T| the number of leaves. The cost-complexity functional is R_α(T) = R(T) + α|T|. At α = 0 the unpruned full tree wins (zero training error). As α grows, the penalty on each leaf grows, and we eventually prefer simpler trees.
Step 2: Define the "weakest link" of a tree. For any internal node t, let T_t be the subtree rooted at t, R(t) be the training error if we replace T_t with a single leaf at t, and R(T_t) be the training error of the actual subtree. Define:
g(t)=∣Tt∣−1R(t)−R(Tt)
Step 3: Prune the weakest link repeatedly. Starting from the full tree T_0:
Compute g(t) for every internal node.
Pick the node with the smallest g(t) — call it α_1. Collapse that subtree into a leaf, giving tree T_1.
Recompute g(t) on T_1 and repeat. Each iteration produces a strictly smaller tree and a strictly larger threshold.
The output is a sequence of thresholds 0 = α_0 < α_1 < α_2 < ... < α_n and a corresponding nested sequence of subtrees T_0 ⊃ T_1 ⊃ T_2 ⊃ ... ⊃ T_n (the last one is just the root). Breiman's theorem guarantees that T_i is the exact minimizer of R_α(T) for every α ∈ [α_i, α_{i+1}). This is what scikit-learn's clf.cost_complexity_pruning_path(X, y) returns.
Step 4: Cross-validate to pick α. Training error always falls when you keep more leaves, so R(T) alone cannot choose α. Instead, fit the pruning path once on training data, then for each α_i in the path, train a fresh tree at that ccp_alpha and score it via K-fold CV. The α that maximizes validation accuracy is the final choice.
Why this beats ad-hoc rules. Pre-pruning rules like "stop splitting when Gini drop < 0.01" or "max_depth = 5" are greedy and local — they make a yes/no decision at each node without seeing the whole tree. Cost-complexity pruning is global: it considers every possible nested pruning of the full tree and picks the one that is provably optimal on the regularization curve. The same logic re-appears in Lasso (LARS algorithm) and quantile regression — wherever there is a sequence of nested models indexed by a regularization parameter.
Loading visualization...
Quick check
You train two trees on the same dataset: Tree A with max_depth=3 hits 88% train / 86% test accuracy. Tree B with max_depth=None hits 100% train / 79% test. Which knob should you tune NEXT to improve Tree B's test accuracy the most?
Trees are not just for classification. For regression, instead of Gini impurity, the split criterion is variance reduction (or MSE):
MSEnode=n1i∈node∑(yi−yˉnode)2
Each leaf predicts the mean of the training values in that leaf. The predicted output is a step function (piecewise constant), which creates characteristic "staircase" predictions.
Tests · Verify that Gini impurity of a pure node is 0. Check that the first split achieves positive information gain. Build the full tree and verify 100% training accuracy.
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import cross_val_score
X, y = load_breast_cancer(return_X_y=True)
# COMMON BUG: forgetting max_depth → 100% train accuracy, ~89% test (overfit)
# FIX: cap depth, use min_samples_leaf
tree = DecisionTreeClassifier(max_depth=4, min_samples_leaf=5, random_state=0)
print(f"CV accuracy: {cross_val_score(tree, X, y, cv=5).mean():.3f}")
# Expected output: CV accuracy: ~0.925
A pruned tree (max_depth=4) lands around 92-93% CV accuracy on this dataset. Crank max_depth=None (the default) and CV accuracy drops to ~89% because the tree memorizes training noise.
#Decision Tree vs. Random Forest vs. XGBoost: When Each Wins
Situation
Reach for
Need a human-readable flowchart for a regulator or domain expert
Single decision tree (max_depth ≤ 4)
Quick baseline on tabular data, no tuning budget
Random Forest with defaults (n_estimators=500)
Need every last 1% of accuracy on tabular data
XGBoost / LightGBM / CatBoost with early stopping
Streaming/online updates (data drifts hourly)
Single tree or Hoeffding tree (RF/XGBoost retrain offline)
< 1000 rows
Single shallow tree often ties RF; XGBoost overfits
> 1M rows with mixed categoricals
LightGBM or CatBoost (faster than XGBoost on histograms)
Interpretable feature interactions matter
RF for global importances; XGBoost + SHAP for per-prediction
Rule of thumb: start with a single tree only as a sanity baseline, then immediately reach for a Random Forest, and only invest in gradient boosting once you've established the RF score.
Trees learn which questions to ask from data. Each node splits on the feature and threshold that best separates classes, measured by information gain or Gini impurity reduction
Gini impurity measures class mixing. A pure node (all one class) has Gini = 0; a maximally mixed node has maximum Gini; the algorithm greedily chooses splits that create the purest child nodes
Unpruned trees always overfit. Without depth limits, trees grow until every leaf contains one training example, memorizing noise; always set max_depth and tune via cross-validation
Trees need no feature scaling. Splits on thresholds are scale-invariant, making trees excellent for mixed feature types without preprocessing
Single trees are high-variance. Small changes in training data can produce completely different tree structures, which is why ensemble methods (Random Forests, Gradient Boosting) are preferred in practice
A single tree is powerful but fragile. What if you could train hundreds of trees and let them vote? Next up: Random Forests & Gradient Boosting -- where many weak learners combine to create the most powerful classical ML algorithms.
Treat each child node as a new root and repeat the process: calculate impurity, find the best split, partition the data. The tree grows deeper with each recursion. Each level asks a more refined question, carving the feature space into increasingly specific rectangular regions.
Recursion stops when a node is pure (all one class), contains too few samples (min_samples_leaf), or the tree reaches maximum depth. This node becomes a leaf that outputs a prediction -- the majority class for classification, or the mean value for regression. Stopping criteria prevent the tree from memorizing noise.