Decision tree structure and terminology: Question bank

Symbols used below, all inherited from the parent note and defined there: a node (a box in the flowchart), a split (dividing a node's samples), a leaf (childless node that predicts), depth (edges on the longest root-to-leaf path), and the test $x_{j} \leq t$ meaning "is feature number $j$ at most the threshold $t$ ?".

True or false — justify

Every node in a decision tree makes a decision.

False — only internal (decision) nodes split by asking a test; leaf nodes make no decision, they just output a prediction.

The root node holds only a single sample.

False — the root holds the entire training dataset before any split; leaves are where samples get thin.

A tree with 8 leaves must have depth 8.

False — depth counts edges on the longest path, not leaves. A perfectly balanced binary tree with 8 leaves has depth 3, since

2^{3} = 8

Every internal node in a standard CART tree has exactly two children.

True for binary CART — each test

x_{j} \leq t

? has a True and a False branch, so exactly two children; the parent note follows this convention.

A single decision tree can produce a smooth diagonal decision boundary.

False — axis-aligned tests

x_{j} \leq t

only cut lines perpendicular to an axis, so the boundary is a staircase; a diagonal needs ensembles or engineered features.

Predictions are constant inside each leaf's region.

True — each leaf owns one hyper-rectangle and outputs one value for the whole box, making the tree a piecewise-constant function.

Making a tree deeper always lowers test error.

False — deeper trees lower training error but eventually memorize noise (overfitting), so test error rises; this is the high-variance side of the Bias-variance tradeoff.

A branch and a leaf are two names for the same thing.

False — a branch is an edge (the True/False outcome of a test); a leaf is a node (the endpoint that predicts). One is a line, one is a box.

Pruning removes leaves to make a tree fit the training data better.

False — pruning removes subtrees to make the tree simpler, trading a little training accuracy for better generalization on unseen data.

Spot the error

"A regression leaf predicts the majority value of its samples."

Wrong — majority is for classification. A regression leaf predicts the mean, because the mean minimizes squared error

\sum (y_{i} - \overset{y}{^})^{2}

"The split

x_{1} + x_{2} \leq 5

is a normal CART test."

Wrong — that is an oblique (diagonal) test using two features at once. Standard CART splits are axis-aligned, testing one feature at a time like

x_{1} \leq 5

"Depth is the total number of nodes in the tree."

Wrong — depth is the number of edges on the longest root-to-leaf path, not a node count. A tree can have many nodes yet small depth.

"A leaf with labels

{A, A, B}

should predict

B

to be safe."

Wrong — predicting

B

misclassifies 2 samples while predicting the ==majority

A

== misclassifies only 1. Majority vote minimizes leaf errors.

"Every root-to-leaf path is a set of ORed conditions."

Wrong — a path is a chain of ANDed conditions ("Age ≤ 30 AND Income ≤ 40k"), because you must satisfy every test along the way to land in that leaf.

"The root is a special kind of leaf."

Wrong — the root is an internal node (it splits) unless the tree has depth 0. A leaf never splits; the root's whole job is the first split.

Why questions

Why must a leaf's prediction be a single constant rather than a formula?

Because a tree partitions space into boxes and assigns one value per box; that constant (majority class or mean) is what minimizes the leaf's training loss, keeping the model piecewise-constant and readable.

Why do we restrict splits to axis-aligned tests when diagonals seem more flexible?

Because testing one feature at a time makes the search cheap (sort each feature, try thresholds) and the rules human-readable ("IF Age ≤ 30"); flexibility is recovered later by averaging many trees.

Why does a very deep tree hurt generalization even though its training error is near zero?

Deep splits carve tiny regions around individual noisy points, so the tree memorizes flukes; training error drops to zero but the memorized noise doesn't repeat on test data, so test error climbs.

Why is the majority class the loss-minimizing prediction for a classification leaf?

Any label you pick is "wrong" for every sample not of that label; picking the largest group leaves the fewest samples mislabeled, minimizing

\sum 1 [y_{i} \neq = \overset{y}{^}]

Why is the mean the loss-minimizing prediction for a regression leaf?

Setting the derivative of

\sum (y_{i} - \overset{y}{^})^{2}

to zero gives

\overset{y}{^} = \frac{1}{∣ R _{ℓ} ∣} \sum y_{i}

, the mean; it's the single point closest (in squared distance) to all the leaf's targets.

Why do we care about depth as a complexity knob rather than, say, node color?

Depth caps the worst-case number of questions asked, which directly bounds how finely the tree can carve space — a natural handle on the bias-variance tradeoff.

Edge cases

What does a tree of depth 0 look like, and what does it predict?

It is a single leaf (root = leaf, no splits) that predicts the majority class (or overall mean) of the entire dataset — the simplest possible tree.

A leaf ends up with a perfect tie, e.g. labels

{A, A, B, B}

. What happens?

There is no strict majority, so the tie is broken by a convention (e.g. lowest class index or first seen); either choice misclassifies the same number of samples, so training loss is unaffected.

A candidate split sends all samples to one child and none to the other. Is it useful?

No — an empty child means the split separated nothing; the node's samples are unchanged, so no impurity is reduced and the split would never be chosen by CART.

What is the prediction of a leaf that somehow contains zero training samples?

It has no data to summarize, so it is degenerate; implementations either forbid empty leaves during growth or fall back to the parent node's prediction.

Two features are identical in the data. Can a split still work?

Yes — the tree just picks one of them to split on; the duplicate carries no extra information, so the boundary is unchanged whichever it uses.

A feature is constant (same value for every sample). Can it ever be split on?

No — every sample satisfies

x_{j} \leq t

or none does, so any threshold gives an empty child; the feature is useless for splitting and gets skipped.

Connections

Gini impurity and entropy — the loss that decides which trap-free split to make.
CART algorithm — the procedure that avoids the empty/degenerate splits above.
Overfitting and pruning — the cure for the "deeper is better" trap.
Bias-variance tradeoff — why depth is the key complexity dial.