The question every waitlisted train ticket forces you to ask
If you have ever booked an IRCTC ticket and landed on the waitlist, you know the ritual. You do not just wait passively — you start asking questions. What quota is this, Tatkal or General? How far is the ticket from confirmation, WL 12 or WL 180? How many days are left before the journey? Which route is it — a busy trunk route like Delhi-Mumbai, or a quieter one? An experienced traveller, or a ticket checker who has seen thousands of PNRs, can often give you a surprisingly confident answer within four or five such questions, without doing any arithmetic in front of you. They are not guessing randomly. They have, from experience, learned which question to ask first (quota matters more than almost anything else), which question to ask next depending on the answer to the first, and so on, until they reach a confident "yes, this will confirm" or "no, this one is going to stay waitlisted."
That process — asking a sequence of narrowing questions, where the next question depends on the answer to the previous one, until you reach a confident final answer — is exactly what a decision tree is, formalised into an algorithm. The difference is that instead of one experienced human's intuition, a decision tree learns which question to ask, and in what order, directly from a table of past examples, by measuring exactly how much each candidate question narrows down the outcome. Nothing about it is mystical. It is countable, computable arithmetic, and by the end of this chapter you will compute it by hand for a real dataset, then confirm your arithmetic by running working code.
Anatomy of a decision tree
A decision tree is a flowchart-shaped model built out of four kinds of pieces. The root node is where every prediction starts — it asks the single most useful question about your data. A decision node (also called an internal node) is any node that still asks a question, splitting the data further based on the answer. A branch is the labelled path leading out of a decision node for one possible answer to its question. And a leaf node is where the questioning stops — it does not ask anything, it simply outputs a prediction, because by the time you reach it, the examples that took that exact path through the tree were (almost) all the same class.
To predict for a brand-new, never-seen-before example, you start at the root, answer its question using the new example's own feature values, follow the matching branch, and repeat at whichever node you land on, until you fall into a leaf. Whatever label sits in that leaf is the tree's prediction. There is no equation to evaluate, no distance to compute — just a walk down the tree, answering one question at a time.
A dataset small enough to compute by hand
To make every number in this chapter checkable by you, we will build a tree on a small, fully visible dataset: fourteen days at a school, recording three weather-related features and whether outdoor cricket practice actually happened. The features are Outlook (Sunny, Overcast, or Rain), Humidity (High or Normal), and Wind (Weak or Strong). The column we are trying to predict — the label or target — is Practice (Yes or No).
Day Outlook Humidity Wind Practice
1 Sunny High Weak No
2 Sunny High Strong No
3 Overcast High Weak Yes
4 Rain High Weak Yes
5 Rain Normal Weak Yes
6 Rain Normal Strong No
7 Overcast Normal Strong Yes
8 Sunny High Weak No
9 Sunny Normal Weak Yes
10 Rain Normal Weak Yes
11 Sunny Normal Strong Yes
12 Overcast High Strong Yes
13 Overcast Normal Weak Yes
14 Rain High Strong NoOut of these fourteen days, practice happened on nine of them (Yes) and was cancelled on five (No). A decision tree learning algorithm's job is to look only at this table — the three feature columns and the one label column — and figure out, purely by counting, which feature to ask about first, which to ask about second within each branch, and so on, until every branch ends in a confident leaf.
What makes a group "impure"? The marble-bag idea
Before we can compare candidate questions, we need a way to measure how "mixed up" a group of examples is. Imagine a bag of marbles. If a bag contains ten red marbles and zero green ones, you can reach in blindfolded and confidently predict red every time — the bag is pure. If a bag contains five red and five green, you have no useful basis for a prediction — it is as impure (mixed) as a bag can be. A bag with eight red and two green sits somewhere in between: mostly predictable, but not perfectly.
The Gini impurity is the standard way to turn this intuition into a number. For a group where a fraction p of examples belong to class Yes and the remaining examples belong to class No, the Gini impurity is:
Gini = 1 - (p_Yes)^2 - (p_No)^2Squaring each class's proportion and subtracting from 1 might look arbitrary, but check it against the marble bags: for the all-red bag, p_red = 1, p_green = 0, so Gini = 1 - 1^2 - 0^2 = 0 — zero impurity, exactly matching our intuition that a pure bag has no uncertainty. For the 5-red-5-green bag, p_red = p_green = 0.5, so Gini = 1 - 0.5^2 - 0.5^2 = 1 - 0.25 - 0.25 = 0.5 — this is the highest value Gini impurity can take for two classes, matching our intuition that a 50-50 mix is maximally uncertain. For the 8-red-2-green bag, Gini = 1 - 0.8^2 - 0.2^2 = 1 - 0.64 - 0.04 = 0.32, comfortably between the two extremes. The formula behaves exactly the way "how mixed is this bag" should behave, and it never needs anything beyond squaring and subtracting.
Now apply it to our full cricket-practice table. All fourteen rows together: 9 Yes out of 14, 5 No out of 14.
Gini(root) = 1 - (9/14)^2 - (5/14)^2
= 1 - 81/196 - 25/196
= 1 - 106/196
= 90/196 = 45/98 ≈ 0.4590.459 is fairly high impurity — sensible, since without asking any question at all, you are simply guessing "Yes" 9 times out of 14 and getting it wrong the other 5 times. The whole point of the tree-building algorithm is to find questions that push this number down toward zero as fast as possible.
Choosing the first question: comparing all three candidates
To test how good a candidate feature is as the root question, split the fourteen rows into groups by that feature's values, compute the Gini impurity of each resulting group, and then combine those group-Gini values into one number using a weighted average — weighted by how many rows fell into each group, since a group with more rows should count for more. This combined number is called the weighted Gini after the split. Subtracting it from the root's Gini (0.459) tells you the Gini gain — how much impurity that question removes. The feature with the highest gain becomes the question at that node.
Start with Outlook. It has three values, splitting the fourteen rows into three groups:
Sunny: 5 rows -> 2 Yes, 3 No -> Gini = 1 - (2/5)^2 - (3/5)^2 = 1 - 4/25 - 9/25 = 12/25 = 0.480
Overcast: 4 rows -> 4 Yes, 0 No -> Gini = 1 - (4/4)^2 - (0/4)^2 = 0
Rain: 5 rows -> 3 Yes, 2 No -> Gini = 1 - (3/5)^2 - (2/5)^2 = 12/25 = 0.480
Weighted Gini = (5/14)(0.480) + (4/14)(0) + (5/14)(0.480)
= 0.1714 + 0 + 0.1714 = 0.3429
Gini gain for Outlook = 0.459 - 0.343 = 0.116Notice something already: every single Overcast day led to practice happening. That group is perfectly pure before we have even split anything further — Overcast alone almost guarantees the answer.
Now Humidity, which only has two values:
High: 7 rows -> 3 Yes, 4 No -> Gini = 1 - (3/7)^2 - (4/7)^2 = 24/49 = 0.490
Normal: 7 rows -> 6 Yes, 1 No -> Gini = 1 - (6/7)^2 - (1/7)^2 = 12/49 = 0.245
Weighted Gini = (7/14)(0.490) + (7/14)(0.245) = 0.245 + 0.122 = 0.367
Gini gain for Humidity = 0.459 - 0.367 = 0.092And Wind:
Weak: 8 rows -> 6 Yes, 2 No -> Gini = 1 - (6/8)^2 - (2/8)^2 = 3/8 = 0.375
Strong: 6 rows -> 3 Yes, 3 No -> Gini = 1 - (3/6)^2 - (3/6)^2 = 0.5
Weighted Gini = (8/14)(0.375) + (6/14)(0.5) = 0.214 + 0.214 = 0.429
Gini gain for Wind = 0.459 - 0.429 = 0.031Lining the three candidates up — Outlook gains 0.116, Humidity gains 0.092, Wind gains only 0.031 — Outlook wins clearly. It becomes the root question. This is the entire "learning" step of a decision tree, repeated at every node: try every available feature, compute the Gini gain each one would produce, keep the one that removes the most impurity.
Recursing: each branch becomes its own smaller problem
Once the root splits on Outlook, the fourteen rows separate into three independent groups, and the algorithm now solves each group as its own fresh problem, using only the remaining features (Humidity and Wind) and only the rows in that group. This repeating, branch-by-branch process is called recursive partitioning — the same splitting procedure applied again and again on smaller and smaller slices of the data.
The Overcast group is already pure (Gini = 0, all four rows are Yes), so no further question is needed — it becomes a leaf immediately, predicting Yes.
The Sunny group has 5 rows (2 Yes, 3 No) and needs a further split. Testing the two remaining features on just these five rows:
Split Sunny group by Humidity:
High: 3 rows -> 0 Yes, 3 No -> Gini = 0
Normal: 2 rows -> 2 Yes, 0 No -> Gini = 0
Weighted Gini = 0 -> Gini gain = 0.480 - 0 = 0.480 (all impurity removed)
Split Sunny group by Wind:
Weak: 3 rows -> 1 Yes, 2 No -> Gini = 0.444
Strong: 2 rows -> 1 Yes, 1 No -> Gini = 0.5
Weighted Gini = 0.467 -> Gini gain = 0.480 - 0.467 = 0.013Humidity wins decisively inside the Sunny branch, and it does something remarkable: it separates the five rows perfectly. Every Sunny-High-Humidity day was a No, every Sunny-Normal-Humidity day was a Yes. Both children have Gini = 0, so both become leaves — no need to ask about Wind at all inside this branch.
The Rain group also has 5 rows (3 Yes, 2 No). Testing the remaining features:
Split Rain group by Humidity:
High: 2 rows -> 1 Yes, 1 No -> Gini = 0.5
Normal: 3 rows -> 2 Yes, 1 No -> Gini = 0.444
Weighted Gini = 0.467 -> Gini gain = 0.480 - 0.467 = 0.013
Split Rain group by Wind:
Weak: 3 rows -> 3 Yes, 0 No -> Gini = 0
Strong: 2 rows -> 0 Yes, 2 No -> Gini = 0
Weighted Gini = 0 -> Gini gain = 0.480 - 0 = 0.480 (all impurity removed)Inside the Rain branch, it is Wind, not Humidity, that separates the rows perfectly. Every Rain-Weak day was a Yes, every Rain-Strong day was a No. Both children are pure leaves, and this branch never needs to ask about Humidity.
A misconception worth correcting directly
Look closely at what just happened. At the root, comparing all fourteen rows, Wind was the worst of the three features — it produced the smallest Gini gain (0.031), far behind Outlook (0.116). Yet two levels down, inside the Rain branch, Wind became the perfect discriminator, splitting five rows into two completely pure groups. Many students, when first learning decision trees, assume a feature's usefulness is a fixed property of that feature — "Wind isn't a very useful feature for this problem" — and expect it to stay equally unhelpful everywhere in the tree. That assumption is wrong, and the Rain branch proves it. A feature's Gini gain is measured only on the rows that reached that particular node, not on the dataset as a whole. Wind's global usefulness across all fourteen days was low because Wind's effect on Sunny days is nearly irrelevant (Humidity dominates there) — but restricted to just the five Rain days, Wind turns out to be exactly the deciding factor. Each node in a decision tree solves its own small, local, self-contained impurity-minimisation problem; it does not remember or care which feature won at its parent or at any sibling branch.
A second, related misconception: reaching a leaf with Gini = 0 does not mean the tree has learned a law of nature — it only means that, among the specific rows in this training table, every example that reached this leaf happened to share the same label. With just fourteen rows spread across three features, some of this perfect separation is a small-sample coincidence. A larger, noisier real dataset (say, thousands of actual match days) would rarely split this cleanly, and forcing every leaf to be perfectly pure on such data is precisely what causes a tree to overfit — a point we return to shortly.
The finished tree
Putting every branch together, the fully grown tree has a root question on Outlook, a second question on Humidity inside the Sunny branch, a second question on Wind inside the Rain branch, and an immediate leaf under Overcast. Every leaf in this particular tree happens to be pure.
Using the tree: two full prediction traces
Suppose tomorrow is Sunny, Humidity Normal, Wind Strong. Start at the root and answer "Outlook?" — Sunny — so follow the Sunny branch to the Humidity node. Answer "Humidity?" — Normal — so follow that branch straight into the leaf Practice = Yes. Notice that Wind was never even asked. The tree only asks the questions relevant to the path a particular example takes; once Humidity alone fully determined the answer inside the Sunny branch, there was nothing left for Wind to contribute there, so it simply is not part of that path.
Now suppose the day is Rain, Humidity High, Wind Weak. "Outlook?" — Rain — follow the Rain branch to the Wind node. "Wind?" — Weak — follow that branch into the leaf Practice = Yes. Here it is Humidity that gets skipped, because inside the Rain branch, Wind alone was the perfect discriminator. This is a genuinely useful property of decision trees compared to, say, a checklist that forces you to answer every single feature every time: a tree only asks what is necessary for the specific example in front of it, and different examples can take paths of different lengths through the same tree.
Building it in code
The entire derivation above — compute Gini, try every feature, keep the best split, recurse on each branch, stop when a group is pure — translates almost line for line into a short Python program. This version was run to confirm it reproduces exactly the tree derived by hand:
from collections import Counter
data = [
{"outlook": "Sunny", "humidity": "High", "wind": "Weak", "practice": "No"},
{"outlook": "Sunny", "humidity": "High", "wind": "Strong", "practice": "No"},
{"outlook": "Overcast", "humidity": "High", "wind": "Weak", "practice": "Yes"},
{"outlook": "Rain", "humidity": "High", "wind": "Weak", "practice": "Yes"},
{"outlook": "Rain", "humidity": "Normal", "wind": "Weak", "practice": "Yes"},
{"outlook": "Rain", "humidity": "Normal", "wind": "Strong", "practice": "No"},
{"outlook": "Overcast", "humidity": "Normal", "wind": "Strong", "practice": "Yes"},
{"outlook": "Sunny", "humidity": "High", "wind": "Weak", "practice": "No"},
{"outlook": "Sunny", "humidity": "Normal", "wind": "Weak", "practice": "Yes"},
{"outlook": "Rain", "humidity": "Normal", "wind": "Weak", "practice": "Yes"},
{"outlook": "Sunny", "humidity": "Normal", "wind": "Strong", "practice": "Yes"},
{"outlook": "Overcast", "humidity": "High", "wind": "Strong", "practice": "Yes"},
{"outlook": "Overcast", "humidity": "Normal", "wind": "Weak", "practice": "Yes"},
{"outlook": "Rain", "humidity": "High", "wind": "Strong", "practice": "No"},
]
def gini(rows):
n = len(rows)
if n == 0:
return 0
counts = Counter(r["practice"] for r in rows)
return 1 - sum((c / n) ** 2 for c in counts.values())
def best_split(rows, features):
n = len(rows)
best_feat, best_gain, best_groups = None, -1, None
for feat in features:
groups = {}
for r in rows:
groups.setdefault(r[feat], []).append(r)
weighted = sum(len(g) / n * gini(g) for g in groups.values())
gain = gini(rows) - weighted
if gain > best_gain:
best_feat, best_gain, best_groups = feat, gain, groups
return best_feat, best_gain, best_groups
def build_tree(rows, features):
labels = [r["practice"] for r in rows]
if len(set(labels)) == 1:
return labels[0]
if not features:
return Counter(labels).most_common(1)[0][0]
feat, gain, groups = best_split(rows, features)
if gain <= 0:
return Counter(labels).most_common(1)[0][0]
remaining = [f for f in features if f != feat]
return (feat, {v: build_tree(sub, remaining) for v, sub in groups.items()})
def predict(node, sample):
if isinstance(node, str):
return node
feat, branch = node
return predict(branch[sample[feat]], sample)
tree = build_tree(data, ["outlook", "humidity", "wind"])
today = {"outlook": "Sunny", "humidity": "Normal", "wind": "Strong"}
print(predict(tree, today)) # Yes
today2 = {"outlook": "Rain", "humidity": "High", "wind": "Weak"}
print(predict(tree, today2)) # Yesbuild_tree does exactly the recursion from the previous section: it checks whether all remaining rows share one label (a pure leaf), otherwise it calls best_split to try every remaining feature and keep the one with the highest Gini gain, then calls itself again separately on each resulting group. predict is the tracing walk from the previous section, written as a function: look at the current node's feature, follow the branch matching the sample's value for that feature, and repeat until a leaf (a plain string) is reached. Running this program prints Yes for both test days — matching, row for row, the two traces worked out by hand above.
Why decision trees do not need feature scaling, and why they can overfit
Every split a decision tree makes is a comparison on a single feature at a time — "is Humidity High or Normal", or in a numeric dataset, "is Marks greater than 75". This means it never matters whether one feature is measured in single digits and another in thousands; the tree simply compares each feature's own values to its own candidate thresholds, one feature at a time, and never combines features into a single distance calculation. This is a genuine, practical difference from distance-based methods such as k-nearest neighbours, where comparing a feature like "runs scored" (ranging roughly 0 to 200) against a feature like "matches played" (ranging roughly 0 to 20) without first rescaling both to comparable ranges would let the larger-range feature dominate the distance purely by accident of units, not because it is more informative.
The cost of a decision tree's flexibility is that, left unchecked, it will happily keep splitting until every single leaf is perfectly pure — exactly what happened in our fourteen-row example. On a small, hand-picked table that is a feature. On a real dataset with thousands of rows and the inevitable noise of the real world, growing a tree all the way to perfect purity usually means the tree has memorised the specific accidents of the training rows — including outliers and mislabelled examples — rather than learning the genuine pattern, and it will then predict poorly on new data it has not seen. This failure mode is called overfitting. Real implementations, including the widely used DecisionTreeClassifier in the scikit-learn library, guard against it with stopping rules: a max_depth limit on how many questions deep the tree may go, a min_samples_leaf limit on how few rows are allowed to justify one more split, or by growing the full tree and then pruning branches back afterwards. You will also encounter entropy and information gain in other textbooks and tools (used by the classic ID3 and C4.5 algorithms) as an alternative to Gini impurity for measuring how mixed a group is; entropy involves logarithms rather than squares, but it is answering the same question and, in practice, usually chooses the same splits Gini would. scikit-learn's default, and the one this chapter builds by hand, is Gini, precisely because it needs nothing beyond squaring and subtracting.
Test your understanding
- A leaf ends up with 7 rows labelled Yes and 1 row labelled No. Compute its Gini impurity. (Work: 1 − (7/8)² − (1/8)² = 1 − 49/64 − 1/64 = 14/64 = 7/32 ≈ 0.219.)
- At some decision node, splitting on Feature A gives a weighted Gini of 0.30, and splitting on Feature B gives a weighted Gini of 0.18, when the node's own Gini before splitting is 0.42. Which feature should the tree pick, and what is its Gini gain? (Feature B, since its resulting impurity is lower; gain = 0.42 − 0.18 = 0.24, versus Feature A's gain of only 0.12.)
- Using the finished tree from this chapter, trace the prediction for a day that is Overcast, Humidity Normal, Wind Weak. Which questions does the tree actually ask before reaching a leaf, and which feature(s) never get checked?
- Explain, in your own words, why Wind produced the lowest Gini gain of the three features at the root, yet became the deciding feature inside the Rain branch. Use the phrase "local to the node" in your answer.
- A classmate grows a decision tree on 4,000 real (not toy) student attendance records until every leaf is 100% pure, and is proud that training accuracy is 100%. Explain what risk this creates, name the concept, and suggest one concrete change to the tree-building process that would reduce that risk.
Summary
A decision tree predicts by asking a sequence of feature-based questions, starting at a root node and following branches down to a leaf that holds the final prediction. The algorithm decides which question to ask at each node by measuring impurity — how mixed the labels are in a group of rows — using a formula like Gini impurity, 1 minus the sum of each class's squared proportion. At every node, it tries every available feature, computes how much each one would reduce the weighted average impurity of the resulting groups (the Gini gain), and keeps the feature that reduces impurity the most. It then repeats this same process independently inside each new branch, using only the rows and features still available there — which is why a feature can be nearly useless at the root and decisive two levels down, since usefulness is always measured locally, on the specific rows that reached that node. Because every split compares one feature to a threshold or category rather than computing distances across features, trees need no feature scaling — but because they can keep splitting until training data is perfectly, artificially pure, real-world use requires deliberate limits such as maximum depth or minimum leaf size to avoid overfitting to noise instead of learning the genuine pattern.