Decision tree structure and terminology: Worked examples

Everything below reuses only ideas already earned in the parent: a leaf owns a set of samples $R_{ℓ}$ ; a classification leaf predicts the majority class (fewest wrong labels); a regression leaf predicts the mean (smallest squared error); depth = number of edges on the longest root-to-leaf path.

The scenario matrix

Every worked example below is tagged with the cell of this matrix it covers. Together they fill every cell.

Cell	Case class	What is "extreme / degenerate" about it
C1	Classification leaf, clear majority	ordinary, sanity-anchor
C2	Classification leaf, tie in counts	two classes equally frequent — which wins?
C3	Classification leaf, pure (one class only)	impurity $= 0$ , degenerate happy case
R1	Regression leaf, several targets	mean of a spread
R2	Regression leaf, single sample	mean of one number — memorisation limit
G1	Geometry: two axis-aligned splits → boxes	the "staircase" made visible
G2	A diagonal boundary a tree cannot draw	limiting behaviour: infinitely many steps
D1	Depth counting with an unbalanced tree	worst-case path, not average
W1	Real-world word problem (loan approval path)	reading a root-to-leaf rule
X1	Exam twist: does adding a split always cut training error?	zero / no-op split, sign of gain

C1 — Classification leaf with a clear majority

Worked example Statement (cell C1)

A leaf owns labels ${Cat, Cat, Dog, Cat, Dog, Cat}$ . What does the leaf predict, and how many training samples does it get wrong?

Forecast: guess the predicted class and the error count before reading on.

Count each class. Cat $= 4$ , Dog $= 2$ , total $= 6$ . Why this step? A classification leaf minimises $\sum_{i} 1 [y_{i} \neq = \overset{y}{^}_{ℓ}]$ ; that sum only depends on the class counts, so counting is the whole computation.
Pick the argmax. $\overset{y}{^}_{ℓ} = ar g max_{c} ∣ {i : y_{i} = c} ∣ = Cat$ (since $4 > 2$ ). Why this step? Predicting Cat is wrong only for the 2 Dogs; predicting Dog would be wrong for the 4 Cats. The bigger group leaves fewer wrong.
Errors made $=$ (everything not Cat) $= 2$ .

Verify: error if we predicted Dog would be $4 > 2$ . So Cat is strictly better — consistent with "majority minimises misclassification." ✓ Prediction = Cat, errors = 2.

C2 — A tie: two classes equally frequent

Worked example Statement (cell C2)

A leaf owns ${A, A, B, B}$ . Counts are equal. What happens?

Forecast: is the prediction undefined, random, or decided by a rule?

Count. $A = 2$ , $B = 2$ . Why this step? Same reason as C1 — the loss depends only on counts.
Both minimise the loss equally. Predicting $A$ misclassifies the 2 $B$ 's; predicting $B$ misclassifies the 2 $A$ 's. Both give error $= 2$ . Why this step? $ar g max$ is a set here, not a single value — the objective genuinely has two minimisers.
Tie-break rule. Libraries break ties deterministically — scikit-learn predicts the class with the smallest index / first in sorted order, here $A$ . Why this step? A model must be reproducible, so an arbitrary-but-fixed rule is applied. The loss is identical either way; only the label chosen differs.

Verify: error count is $2$ whichever we pick, so no tie-break can lower the loss — the ambiguity is real, and only the reported label is a convention. ✓ Errors = 2, predicted label = A (by sort-order tie-break).

C3 — A pure leaf

R1 — Regression leaf, several targets

Worked example Statement (cell R1)

A regression leaf owns targets ${8, 11, 13, 8}$ . What does it predict and what is its squared error?

Forecast: guess the number, then compute the leftover error.

Take the mean. $\overset{y}{^}_{ℓ} = \frac{8 + 11 + 13 + 8}{4} = \frac{40}{4} = 10$ . Why this step? A regression leaf minimises $\sum_{i} (y_{i} - \overset{y}{^}_{ℓ})^{2}$ . Setting $\frac{d}{d y ^ _{ℓ}} \sum (y_{i} - \overset{y}{^}_{ℓ})^{2} = - 2 \sum (y_{i} - \overset{y}{^}_{ℓ}) = 0$ gives $\overset{y}{^}_{ℓ} = \frac{1}{n} \sum y_{i}$ — the mean. (Full derivation in the parent note.)
Residuals. $(8 - 10, 11 - 10, 13 - 10, 8 - 10) = (- 2, 1, 3, - 2)$ . Why this step? The leftover squared error tells you how "impure" a regression leaf still is — the analogue of misclassification count.
Squared error $= 4 + 1 + 9 + 4 = 18$ .

Verify: try $\overset{y}{^} = 11$ instead: residuals $(- 3, 0, 2, - 3)$ , SSE $= 9 + 0 + 4 + 9 = 22 > 18$ . The mean wins. ✓ Prediction = 10, SSE = 18.

R2 — Regression leaf with a single sample (memorisation limit)

G1 — Two axis-aligned splits build boxes

Worked example Statement (cell G1)

A tree on features $(x_{1}, x_{2})$ splits first on $x_{1} \leq 4$ , then (on the right side) on $x_{2} \leq 3$ . Sketch the regions and give each leaf's box.

Forecast: how many boxes, and what are their coordinate ranges?

First split $x_{1} \leq 4$ draws a vertical line at $x_{1} = 4$ . Why this step? A test on feature $j$ is a line perpendicular to axis $j$ ; testing $x_{1}$ moves you left/right, so the cut is vertical.
Left leaf = all points with $x_{1} \leq 4$ (any $x_{2}$ ) — the whole left slab.
Second split $x_{2} \leq 3$ applies only on the right ( $x_{1} > 4$ ), drawing a horizontal line at $x_{2} = 3$ inside that slab only. Why this step? Splits are local to a node's region; the horizontal cut exists only where $x_{1} > 4$ , which is why tree boundaries are ragged, not a full grid.
Three leaves / boxes:
- $L_{1} : x_{1} \leq 4$ (any $x_{2}$ )
- $L_{2} : x_{1} > 4$ and $x_{2} \leq 3$
- $L_{3} : x_{1} > 4$ and $x_{2} > 3$

Verify: the three boxes are disjoint and cover the plane — every point lands in exactly one leaf. Prediction is constant inside each box → piecewise-constant, the staircase from the parent note. ✓ Leaf count = 3.

G2 — The diagonal a tree cannot draw

Worked example Statement (cell G2)

The true boundary is the diagonal $x_{1} + x_{2} = 5$ . How does an axis-aligned tree approximate it, and what happens in the limit?

Forecast: can one split do it? Two? Infinitely many?

One axis-aligned split can't tilt. Any single test is a horizontal or vertical line; a $4 5^{\circ}$ line is impossible to reproduce with one cut. Why this step? The model class is hyper-rectangles; a slanted separator is simply not in the family.
Stack cuts to approximate. Alternating vertical/horizontal cuts trace a staircase hugging the diagonal. Why this step? Each extra split refines one step of the stair, getting closer without ever being straight.
Limiting behaviour: as depth $\to \infty$ , the staircase $\to$ the diagonal, but never equals it, and each extra step costs a split (more risk of overfitting). Why this step? This is why Random Forests average many staircases to smooth the effective boundary.

Verify: check the two staircase steps land on the correct side of $x_{1} + x_{2} = 5$ — e.g. point $(1, 1)$ has sum $2 < 5$ (below), $(4, 4)$ has sum $8 > 5$ (above); both are classified correctly by the drawn steps. ✓

D1 — Depth of an unbalanced tree

Worked example Statement (cell D1)

A tree: Root splits into Leaf-A (left) and Internal-B (right). Internal-B splits into Leaf-C and Internal-D. Internal-D splits into Leaf-E and Leaf-F. What is the tree's depth?

Forecast: guess the number of edges on the longest path.

List each root-to-leaf path and count edges.
- Root→A: 1 edge.
- Root→B→C: 2 edges.
- Root→B→D→E: 3 edges.
- Root→B→D→F: 3 edges. Why this step? Depth is the number of edges on the longest root-to-leaf path, so we must inspect every path, not average them.
Take the maximum $= max (1, 2, 3, 3) = 3$ . Why this step? Depth caps model complexity by the worst-case number of questions any sample can face — a max_depth=3 limit would allow this exact tree.

Verify: the shallowest leaf (A) is at edge $1$ , but depth is not the average $(1 + 2 + 3 + 3) /4 = 2.25$ ; it is the max $= 3$ . ✓ Depth = 3.

W1 — Real-world word problem: reading a decision path

Worked example Statement (cell W1)

A loan tree: Root asks Credit_score ≤ 600?. False branch (score $> 600$ ) asks Debt_ratio ≤ 0.35?. True branch of that → Leaf: "Approve". Applicant: credit score $720$ , debt ratio $0.28$ . What is the decision and the plain-English rule?

Forecast: approve or reject?

Root test: is $720 \leq 600$ ? No → take the False branch (go right). Why this step? By the parent's convention True→left, False→right; the applicant's score exceeds the threshold, so we go right.
Next test: is $0.28 \leq 0.35$ ? Yes → take the True branch. Why this step? A root-to-leaf path is a chain of ANDed conditions; we follow each answer until a leaf.
Land on Leaf "Approve." The rule is: IF Credit_score $> 600$ AND Debt_ratio $\leq 0.35$ THEN Approve.

Verify: the applicant satisfies both ANDed conditions ( $720 > 600$ ✓ and $0.28 \leq 0.35$ ✓), so "Approve" is consistent with the path. ✓ Decision = Approve.

X1 — Exam twist: does a split always reduce training error?

Worked example Statement (cell X1)

A node has ${A, A, A, B}$ (majority $A$ , so $1$ error). We split on a feature. Case (i): the split puts ${A, A}$ left and ${A, B}$ right. Case (ii): the split puts ${A, A, A, B}$ all in one child (the other child is empty). Does training error drop in each case?

Forecast: which split actually helps? Does a split ever hurt?

Parent error. Majority $A$ , so $1$ misclassified $B$ . Parent error $= 1$ . Why this step? We compare children against this baseline — the "gain" is parent error minus total child error.
Case (i) child errors. Left ${A, A}$ : pure, $0$ errors. Right ${A, B}$ : tie, majority gives $1$ error. Total $= 0 + 1 = 1$ . Why this step? Total training error after the split is the sum over children.
Case (i) gain $= 1 - 1 = 0$ . No improvement — the $B$ is still stuck with an $A$ . Why this step? A split only helps if it separates differing labels; here $B$ still shares a child with an $A$ .
Case (ii): a no-op / degenerate split. One child holds all $4$ samples, the other is empty. Child error $= 1 + 0 = 1$ , gain $= 0$ . Why this step? An empty child means the split did nothing — training error cannot rise (worst case it stays equal), but it need not fall. This is the degenerate/zero-gain case exams love.

Verify: in both cases total child error $= 1 =$ parent error, so gain $= 0$ (never negative). A split's training-error gain is always $\geq 0$ , but can be exactly $0$ . ✓ Gain (i) = 0, Gain (ii) = 0.

Recall

Recall Quick self-test

Leaf with ${A, A, B}$ — prediction and error count? ::: Predict $A$ ; error $= 1$ . Leaf with ${X, X, Y, Y}$ — is prediction well-defined? ::: Loss is (both give error $2$ ); label picked by fixed tie-break convention. Regression leaf ${2, 4, 6}$ — prediction and SSE? ::: Mean $= 4$ ; SSE $= (2 - 4)^{2} + (4 - 4)^{2} + (6 - 4)^{2} = 8$ . Single-sample regression leaf — training error? ::: Exactly $0$ (perfect fit — overfitting limit). Tree with paths of edge-lengths $1, 2, 3, 3$ — depth? ::: $3$ (the max, not the average). Can a split raise training error? ::: No — it drops or stays flat; a no-op/empty-child split gives zero gain.

Connections

Gini impurity and entropy — turns the "how pure is this leaf" question (C2, C3, R1) into a number the splitter maximises gain on.
CART algorithm — the greedy loop that searches splits like X1 to pick the best one.
Overfitting and pruning — why the single-sample leaf (R2) and infinite staircase (G2) are dangers, and how to stop.
Random Forests — averaging many staircases (G2) to smooth the boundary.
Gradient Boosted Trees — stacking trees to fix leftover errors like the stuck $B$ in X1.
Bias-variance tradeoff — deep trees (R2) are low bias, high variance.

Worked examples — Decision tree structure and terminology