Walk me through exactly how a decision tree chooses a split at each node.

How to think about it

The short answer

At a node, a decision tree tries every eligible (feature, threshold) pair, scores the two resulting groups by their weighted impurity, and chooses the pair that gives the largest impurity reduction. That choice is greedy: after splitting, the tree repeats the same process independently in each child and never goes back to reconsider the parent split.

The interviewer is usually testing whether you understand what “best split” actually means. It does not mean the split with the highest immediate accuracy, nor the split that produces the best possible complete tree. It means the split that makes the current node’s children as pure as possible according to the chosen criterion.

What the tree is measuring

Suppose a node contains a set of training rows. A feature is one input column, such as age or account balance. A threshold is a candidate cut on that feature, such as balance <= 500.

For a numeric feature, a binary tree creates two children:

• the left child receives rows whose feature value is less than or equal to the threshold;
• the right child receives rows whose feature value is greater than the threshold.

The tree evaluates the impurity of the parent and the impurity that would remain in both children.

For classification, a common criterion is Gini impurity, which measures how mixed the class labels are:

Gini(S) = 1 - sum(p_k^2)

Here, p_k is the fraction of rows in node S belonging to class k. A node containing only one class has Gini impurity of zero. A node split evenly between two classes has Gini impurity of 0.5.

For a proposed split, the weighted child impurity is:

Weighted impurity = (n_L / n) * I(L) + (n_R / n) * I(R)

n is the number of rows in the parent, n_L and n_R are the row counts in the left and right children, and I is the chosen impurity function.

The improvement, often called impurity decrease or gain, is:

Gain = I(parent) - Weighted impurity

The parent impurity is the same for every candidate at that node. Therefore, maximizing gain is equivalent to minimizing the weighted impurity left in the children.

For regression, the same structure applies, but impurity is usually based on variance or squared error rather than class mixing. A good regression split makes the target values within each child more similar. A regression leaf normally predicts the mean target value of the rows that reach it.

A complete numerical example

Imagine five loan applications. The feature x is a numeric risk score, and y is the observed outcome: zero means no default and one means default.

x	y
0.5	0
1.0	0
2.5	0
3.5	1
4.0	1

At the root, there are three zeros and two ones. The parent Gini impurity is:

1 - (3/5)^2 - (2/5)^2 = 0.48

The distinct feature values are already sorted. The only useful thresholds are the midpoints between adjacent values:

0.75, 1.75, 3.0, and 3.75

There is no point testing a threshold of 2.2 instead of 2.4 if both thresholds put exactly the same rows on each side. The midpoint is simply a convenient representative of that gap.

Candidate threshold	Left labels	Right labels	Weighted child impurity	Gain
0.75	0	0, 0, 1, 1	0.40	0.08
1.75	0, 0	0, 1, 1	0.2667	0.2133
3.0	0, 0, 0	1, 1	0.00	0.48
3.75	0, 0, 0, 1	1	0.30	0.18

The threshold 3.0 wins because it creates two pure children. Its gain is the full parent impurity, 0.48.

A small scikit-learn example makes the result concrete:

from sklearn.tree import DecisionTreeClassifier, export_text
import numpy as np

X = np.array([[2.5], [1.0], [3.5], [0.5], [4.0]])
y = np.array([0, 0, 1, 0, 1])

tree = DecisionTreeClassifier(max_depth=2, criterion="gini")
tree.fit(X, y)

print(export_text(tree, feature_names=["x"]))

The output is:

|--- x <= 3.00
|   |--- class: 0
|--- x >  3.00
|   |--- class: 1

Notice that max_depth=2 is a ceiling, not an order to grow two complete levels. Both children are already pure, so there is no useful reason to split them again.

What happens inside a real tree builder

At each node, the implementation follows roughly this sequence.

First, it identifies the rows that reached the node and checks stopping conditions. The node may already be pure. It may contain fewer rows than min_samples_split, or splitting it might violate min_samples_leaf. The maximum depth may also have been reached.

Next, it determines which features and thresholds are eligible. A simple exact algorithm sorts the values of each numeric feature at that node, skips duplicate values, and considers the gaps between consecutive distinct values. If a feature has N distinct values, there are at most N - 1 threshold candidates.

It then scans the candidates. Efficient implementations update class counts as the threshold moves from left to right instead of rebuilding both child nodes from scratch for every threshold. That turns each feature scan into a linear pass after the values are ordered.

For every candidate, it calculates the weighted child impurity and keeps the best one seen so far. If two candidates have exactly the same score, the tie is resolved by implementation details such as feature order, threshold order, or randomization.

Finally, it commits to the winning split, partitions the rows, and repeats the process on the left and right children. If no candidate achieves the required minimum improvement, the node becomes a leaf.

At a classification leaf, the prediction is usually the majority class. The predicted class probabilities are the class proportions in that leaf. At a regression leaf, the prediction is generally the mean target value.

If rows have sample weights, ordinary counts are replaced by weighted counts. A row with weight 10 influences impurity ten times as much as a row with weight 1. Class weights have the same practical effect: they can change which split wins because they change the objective being optimized.

Common misconception: the tree does not directly optimize accuracy

A split can improve Gini impurity without improving the final classification accuracy at that node. Conversely, a split that looks attractive under accuracy may leave class probabilities badly mixed.

This matters especially with imbalanced data. If 95 of 100 rows belong to class zero, a leaf predicting zero already has 95 percent accuracy. Gini still examines how the minority examples are distributed, but it is not optimizing recall, F1 score, revenue, or the cost of a false negative. Those are separate business or evaluation objectives.

The senior-level caveat: this is greedy, not globally optimal

The root split is selected using only the immediate impurity decrease. The algorithm does not ask whether a weaker split would unlock spectacular splits two levels later.

The classic example is XOR:

• (0, 0) has class zero;
• (0, 1) has class one;
• (1, 0) has class one;
• (1, 1) has class zero.

A split on either individual feature leaves one zero and one one in each child, so the immediate gain is zero. Yet a deeper tree can represent XOR by splitting on one feature and then splitting on the other. If the implementation requires a positive impurity decrease, it may stop at the root and fail to discover that structure.

This is why a single tree is easy to understand but not guaranteed to find the best possible tree. Ensembles such as random forests and gradient-boosted trees reduce the practical impact of one unlucky greedy choice, but they do not turn the underlying split search into a global optimizer.

A standard tree is also axis-aligned: each split uses one feature at a time. It can represent a diagonal boundary such as x1 + x2 = 10, but usually only by building a staircase of many rectangular regions. Oblique-tree variants can split on combinations of features, but that is a different algorithm.

What changes in production

The textbook description says “try every feature and every threshold.” Real implementations often narrow that search.

A random forest may consider only a random subset of features at each node. Histogram-based algorithms put continuous values into bins and test bin boundaries instead of every exact midpoint. This is faster, but the selected threshold is approximate. Native categorical-tree implementations may consider category groupings, while other libraries require numeric encodings.

Categorical variables deserve care. The classic sklearn.tree.DecisionTreeClassifier expects numeric input. One-hot encoding gives each category its own binary split. Ordinal encoding, such as mapping red to zero, blue to one, and green to two, creates an artificial order that the tree may exploit even though no such order exists. Libraries with native categorical support use their own category-splitting strategy.

At one node containing m rows and d considered features, sorting every feature costs roughly O(d * m log m), followed by an O(d * m) scan. The total cost for a complete tree depends on how many nodes are created, how balanced they are, and whether sorted values or histograms are reused. A deep, unbalanced tree can be much more expensive than a shallow balanced one.

A failure mode appears quickly when the tree is allowed to keep splitting noise. The first symptom is often a training accuracy of 100 percent alongside a much worse validation score, plus a tree with hundreds or thousands of tiny leaves. A deep tree with min_samples_leaf=1 can memorize individual examples. Typical remedies are a depth limit, a larger minimum leaf size, a minimum impurity decrease, or post-training cost-complexity pruning selected with validation data.

Feature importance has a related trap. Impurity-based importance sums the gains attributed to features, but it can favor continuous or high-cardinality features because they offer more candidate cut points. Treat that importance as a description of the fitted tree, not proof that a feature is causal or even reliably predictive. Validate it with held-out data and, where appropriate, permutation-based analysis.

What they’ll ask next

Why are thresholds placed at midpoints?
Any threshold between the same two adjacent observed values creates the same left and right memberships. The midpoint is a simple representative. Values equal to the threshold are assigned according to the implementation’s inequality convention, usually to the left.

How does the choice change for regression?
The search over features and thresholds is the same. The score changes from class impurity to a reduction in weighted variance or squared error. A split wins when the target values become more homogeneous within the two children.

Why not choose the split that gives the best final validation accuracy?
A tree is normally grown using a local training objective, not repeated validation searches at every node. Searching over complete tree structures would be far more expensive and would make the validation set part of the fitting procedure. Instead, the tree uses a criterion such as Gini or squared error, then controls complexity with depth, leaf-size constraints, pruning, or ensembles.

Say this in the interview

“At each node, I evaluate each eligible feature and threshold, compute the weighted impurity of the two resulting children, choose the pair with the largest impurity decrease, and recurse greedily until a stopping rule or lack of useful gain turns the node into a leaf.”