The structure of a decision tree emerges from a sequence of splitting decisions. At each internal node, the algorithm must answer a seemingly simple question: Which feature should we split on, and at what threshold? This choice—repeated recursively—determines everything about the resulting tree: its depth, its accuracy, its interpretability, and its generalization ability.

The challenge is that the space of possible splits is enormous. For a dataset with $d$ features and $N$ samples, each node potentially has $O(d \times N)$ candidate splits to evaluate. Making the wrong choice early can doom the entire subtree to suboptimal performance. Making the right choice requires a principled measure of split quality—a way to quantify how much a split improves our predictions.

This page lays the foundation for understanding split selection. We will explore what makes a good split, how to enumerate candidate splits, and the exhaustive search algorithm that decision trees use to find optimal splits. This sets the stage for the next topic: impurity measures like Gini and entropy that quantify split quality.

At each internal node of a decision tree, we face an optimization problem: find the split that best separates the data according to some criterion. Let us formalize this precisely.

Problem Formulation

Given:

• A set of samples $\mathcal{D}_v = {(\mathbf{x}_i, y_i)}$ at node $v$
• A feature space $\mathcal{X} \subseteq \mathbb{R}^d$ with $d$ features
• An impurity measure $\mathcal{I}(\cdot)$ that quantifies node "impurity"
• A gain function $\Delta(v, j, \theta)$ measuring improvement from splitting

Find: $$ (j^, \theta^) = \arg\max_{j \in {1, \ldots, d}, \theta \in \Theta_j} \Delta(v, j, \theta) $$

Where $\Theta_j$ is the set of candidate thresholds for feature $j$.

The Gain Function

The gain from a split measures how much it reduces impurity. For a split on feature $j$ at threshold $\theta$:

$$\Delta(v, j, \theta) = \mathcal{I}(\mathcal{D}_v) - \left( \frac{|\mathcal{D}_L|}{|\mathcal{D}_v|} \mathcal{I}(\mathcal{D}_L) + \frac{|\mathcal{D}_R|}{|\mathcal{D}_v|} \mathcal{I}(\mathcal{D}_R) \right)$$

Where:

• $\mathcal{D}_L = {(\mathbf{x}, y) \in \mathcal{D}_v : x_j \leq \theta}$ (left child samples)
• $\mathcal{D}_R = {(\mathbf{x}, y) \in \mathcal{D}_v : x_j > \theta}$ (right child samples)

The gain is the impurity of the current node minus the weighted average impurity of the children. A higher gain means a more valuable split.

Why Greedy Works

Despite being locally optimal, greedy splitting often produces near-optimal trees because:

1. Good early splits simplify later decisions: A feature that perfectly separates two classes at the root eliminates the need for complex downstream splits

2. Recursive refinement corrects mistakes: Even if an early split is suboptimal, subsequent splits can compensate by focusing on mislabeled regions

3. Pruning post-hoc: After growing a full tree greedily, pruning can remove suboptimal subtrees, partially recovering from greedy errors

4. Ensemble methods average out errors: Random Forests and boosting combine many greedy trees, reducing the impact of any single suboptimal split

Before optimizing, we must enumerate the set of candidate splits. For continuous features, what thresholds should we consider?

The Threshold Space

For a continuous feature $x_j$, we could theoretically split at any real-valued threshold $\theta \in \mathbb{R}$. However, only finitely many distinct splits produce different partitions of the training data.

Key insight: If threshold $\theta$ falls between consecutive sorted feature values $x_{j,(i)}$ and $x_{j,(i+1)}$, the resulting partition is identical to splitting at any other point in that interval.

Consequence: We only need to consider thresholds at the midpoints between consecutive unique values:

$$\Theta_j = \left{ \frac{x_{j,(i)} + x_{j,(i+1)}}{2} : i \in {1, \ldots, m_j - 1} \right}$$

Where $x_{j,(1)} < x_{j,(2)} < \cdots < x_{j,(m_j)}$ are the sorted unique values of feature $j$ in the current node's data, and $m_j$ is the number of unique values.

Algorithm: Generating Candidate Thresholds

function GenerateCandidateThresholds(feature_values):
    sorted_unique = Sort(Unique(feature_values))
    thresholds = []
    for i in range(len(sorted_unique) - 1):
        midpoint = (sorted_unique[i] + sorted_unique[i+1]) / 2
        thresholds.append(midpoint)
    return thresholds

Number of candidate thresholds per feature:

• Maximum: $N - 1$ (if all values are unique)
• Typical: Much smaller if feature values repeat
• For discrete features encoded as integers: Often very few unique values

For each candidate split, we must compute its gain. This involves partitioning the samples and calculating impurity for both children. Understanding the mechanics reveals opportunities for computational optimization.

Naive Split Evaluation

Given a node with samples $\mathcal{D}_v$ and candidate split $(j, \theta)$:

function EvaluateSplit(samples, feature_j, threshold):
    left_samples = [sample for sample in samples if sample.x[j] <= threshold]
    right_samples = [sample for sample in samples if sample.x[j] > threshold]
    
    impurity_left = ComputeImpurity(left_samples)
    impurity_right = ComputeImpurity(right_samples)
    
    n_total = len(samples)
    n_left = len(left_samples)
    n_right = len(right_samples)
    
    weighted_child_impurity = (n_left/n_total) * impurity_left + 
                               (n_right/n_total) * impurity_right
    
    gain = ComputeImpurity(samples) - weighted_child_impurity
    return gain

Computational Cost Analysis

Per-split evaluation cost:

• Partitioning samples: $O(|\mathcal{D}_v|)$ comparisons
• Computing impurity for each child: $O(|\mathcal{D}_{\text{child}}|)$
• Total: $O(|\mathcal{D}_v|)$ per split

Total per node:

• Candidates: $O(d \times |\mathcal{D}_v|)$ in worst case
• Per candidate: $O(|\mathcal{D}_v|)$
• Total: $O(d \times |\mathcal{D}_v|^2)$

This quadratic cost in samples per feature is problematic for large datasets. Fortunately, there's a better way.

Efficient Sorted Sweep

By sorting samples by feature value once, we can evaluate all thresholds for that feature in a single pass:

Key observation: As threshold increases, samples move from right child to left child one at a time. We can update impurity incrementally rather than recomputing from scratch.

Algorithm:

function EfficientSplitSearch(samples, feature_j):
    # Sort samples by feature value
    sorted_samples = Sort(samples, key=lambda s: s.x[j])
    
    # Initialize: all samples in right child
    left_stats = EmptyStats()
    right_stats = ComputeStats(sorted_samples)
    
    best_gain = -infinity
    best_threshold = None
    
    for i in range(len(sorted_samples) - 1):
        sample = sorted_samples[i]
        
        # Move sample from right to left
        left_stats.Add(sample)
        right_stats.Remove(sample)
        
        # Only evaluate if this creates a distinct split
        if sorted_samples[i].x[j] == sorted_samples[i+1].x[j]:
            continue  # Same value, skip duplicate threshold
        
        # Compute gain from incremental stats
        gain = ComputeGainFromStats(left_stats, right_stats)
        
        if gain > best_gain:
            best_gain = gain
            best_threshold = (sorted_samples[i].x[j] + sorted_samples[i+1].x[j]) / 2
    
    return best_threshold, best_gain

Improved complexity:

• Sorting: $O(|\mathcal{D}_v| \log |\mathcal{D}_v|)$
• Sweep: $O(|\mathcal{D}_v|)$ with $O(1)$ incremental updates
• Per feature: $O(|\mathcal{D}_v| \log |\mathcal{D}_v|)$
• Total: $O(d \times |\mathcal{D}_v| \log |\mathcal{D}_v|)$

This is a dramatic improvement over the naive $O(d \times |\mathcal{D}_v|^2)$ approach.

At each node, the decision tree algorithm performs an exhaustive search over all features and all candidate thresholds to find the optimal split. Let us trace through this process in detail.

Complete Split Selection Algorithm

function FindBestSplit(node):
    if StoppingConditionMet(node):
        return None  # Make this a leaf
    
    best_gain = -infinity
    best_feature = None
    best_threshold = None
    
    for feature_j in range(d):  # For each feature
        # Efficient sorted sweep for this feature
        threshold, gain = EfficientSplitSearch(node.samples, feature_j)
        
        if gain > best_gain:
            best_gain = gain
            best_feature = feature_j
            best_threshold = threshold
    
    if best_gain <= 0:  # No beneficial split found
        return None
    
    return (best_feature, best_threshold)

Stopping Conditions

The exhaustive search is not performed when stopping conditions are met:

1. Maximum depth reached: If node depth equals max_depth parameter
2. Minimum samples: If node has fewer samples than min_samples_split
3. Pure node: If all samples have the same label (impurity = 0)
4. Minimum gain: If no split achieves positive gain (or below threshold)
5. Minimum samples per leaf: If any split would create a child with fewer than min_samples_leaf samples

These conditions prevent overfitting by limiting tree complexity.

Tie-Breaking

When multiple splits achieve the same gain (common for discrete features), implementations typically:

• Choose the feature with the smallest index (deterministic)
• Choose randomly among tied splits (adds variance but can help ensembles)
• Choose based on secondary criteria (e.g., more even sample distribution)

Decision trees handle different feature types through variations of the splitting mechanism. Understanding these variations is essential for proper feature engineering.

Continuous Features

For continuous features, splits are threshold-based: $$\text{condition: } x_j \leq \theta$$

As discussed, optimal thresholds are found via sorted sweep over midpoints between consecutive values. This is the standard CART approach.

Ordinal Features

Ordinal features (e.g., education level: high school < bachelor's < master's < PhD) are treated identically to continuous features. The sorted sweep respects the natural ordering, and threshold splits preserve ordinal relationships.

$$\text{if education} \leq \text{bachelor's} \Rightarrow {\text{high school, bachelor's}} \text{ vs } {\text{master's, PhD}}$$

Nominal (Categorical) Features

Nominal features have no natural ordering (e.g., color: red, blue, green). Two approaches exist:

Approach 1: One-hot encoding (CART-style)

Convert to binary features and use standard threshold splits:

• color_red ∈ {0, 1}
• color_blue ∈ {0, 1}
• color_green ∈ {0, 1}

Splits become: "Is color_red ≤ 0.5?" (equivalently: "Is it not red?")

Pros: Conceptually simple, works with standard algorithm Cons: Creates many features; splits can only isolate one category at a time

Approach 2: Subset splits (ID3/C4.5-style)

Consider all possible subsets of categories: $$\text{condition: } x_j \in S \text{ vs } x_j \notin S$$

For a feature with $k$ categories, there are $2^{k-1} - 1$ possible subset splits.

Pros: Can find optimal groupings; single split can separate multiple categories Cons: Exponential in number of categories; computationally expensive for $k > 10$

Binary Features

Binary features (0/1, true/false) are trivial: only one possible split exists: $$x_j \leq 0.5 \Leftrightarrow x_j = 0$$

Either this split is beneficial (applied) or not (feature ignored at this node).

Missing Values

Missing values pose a challenge: which child should a sample with $x_j = \text{NaN}$ follow?

CART approach (surrogate splits):

• Find the best split as usual (ignoring missing values)
• Find secondary features whose splits correlate with the primary split
• When a sample is missing the primary feature, use the best surrogate

XGBoost/LightGBM approach (default direction):

• During training, try sending missing values left AND right
• Choose whichever direction reduces impurity more
• Store this choice; use it during prediction

Before diving into formal impurity measures (next page), let's build intuition about what makes a split good.

The Goal: Homogeneous Children

A perfect split completely separates classes:

• Left child: 100% class A
• Right child: 100% class B

Both children are pure (impurity = 0). The split has maximum gain.

A useless split preserves the parent's class distribution in both children:

• Parent: 50% A, 50% B
• Left child: 50% A, 50% B
• Right child: 50% A, 50% B

Children are just as impure as parent. The split has zero gain.

Visual Intuition

Consider a 2D classification problem where we want to separate red and blue points:

Case 1: Good split

• Before split: mixed red and blue points in a region
• After split on $x_1$: left region is mostly red, right region is mostly blue
• Both children are more pure than parent → high gain

Case 2: Bad split

• Before split: mixed red and blue points in a region
• After split on $x_1$: left region is still mixed, right region is still mixed
• Children are as impure as parent → low/zero gain

Case 3: Unbalanced split

• Split creates one tiny pure child and one large mixed child
• Tiny child contributes little to weighted average (small $n_L/n$)
• Large mixed child dominates → gain is small
• This is why good splits tend to be balanced in size

We have established a comprehensive understanding of how decision trees select splits. Let us consolidate the key concepts:

What's next:

We now understand how splits are searched and what makes a split valuable at an intuitive level. The next critical question is: How do we quantify split quality precisely? The following pages explore leaf predictions, recursive partitioning, and the interpretability properties that make decision trees uniquely valuable in machine learning.