Recursive Partitioning

Decision trees are not designed by hand—they are grown from data through an elegant algorithmic process called recursive partitioning. This process embodies the classic divide-and-conquer paradigm: split the problem into smaller subproblems, solve each recursively, and combine the results.

At the heart of recursive partitioning is a beautifully simple idea: given a set of samples at a node, find the best way to split them into two groups, then repeat on each group until some stopping condition is met. This recursive refinement naturally builds the hierarchical tree structure we've studied.

Understanding recursive partitioning is essential because:

1. It explains why trees look the way they do—the algorithm's choices manifest in tree structure
2. It reveals where complexity costs arise—key for understanding training time
3. It shows how hyperparameters control growth—depth limits, sample constraints, etc.
4. It is the foundation for understanding ensembles—Random Forests and Boosting build on this process

The essence of recursive partitioning is captured in a deceptively simple recursive function. Let's build it step by step.

Core Algorithm Structure

function BuildTree(samples, depth):
    // Create a node for these samples
    node = CreateNode(samples)
    
    // Check stopping conditions
    if ShouldStop(samples, depth):
        node.prediction = ComputeLeafPrediction(samples)
        return node  // This is a leaf
    
    // Find the best split
    (feature, threshold) = FindBestSplit(samples)
    
    if NoGoodSplitFound(feature, threshold):
        node.prediction = ComputeLeafPrediction(samples)
        return node  // No improvement possible; make leaf
    
    // Partition samples
    left_samples = {s ∈ samples : s.x[feature] ≤ threshold}
    right_samples = {s ∈ samples : s.x[feature] > threshold}
    
    // Recurse on children
    node.feature = feature
    node.threshold = threshold
    node.left = BuildTree(left_samples, depth + 1)
    node.right = BuildTree(right_samples, depth + 1)
    
    return node

// Entry point
root = BuildTree(all_training_samples, depth=0)

The Recursive Insight

The algorithm's power comes from its recursive structure:

1. Base case: When stopping conditions are met, create a leaf with a prediction
2. Recursive case: Split the samples and recursively build subtrees for each partition
3. Combination: Attach the child subtrees to the current node

Each recursive call operates on a subset of the parent's samples. The samples are never copied—typically indices are passed, pointing into the original dataset.

Execution Flow

Consider a tiny dataset with 100 samples:

1. BuildTree(samples[0:100], depth=0) — Root node, all samples

   • Best split: feature 2, threshold 3.5
   • Left: 40 samples, Right: 60 samples

2. BuildTree(samples[0:40], depth=1) — Left child

   • Best split: feature 0, threshold 1.2
   • Left: 15 samples, Right: 25 samples

3. BuildTree(samples[0:15], depth=2) — Left-left grandchild

   • Stopping condition met (depth = max_depth)
   • Return leaf with prediction

4. Returns continue, building right subtrees...

The algorithm proceeds depth-first, fully constructing the left subtree before starting the right subtree.

Without stopping conditions, recursive partitioning would continue until every leaf contains a single sample—massive overfitting. Stopping conditions (also called pre-pruning or early stopping) control tree complexity during growth.

Standard Stopping Conditions

1. Maximum Depth (max_depth)

if depth >= max_depth:
    return CreateLeaf(samples)

The most direct complexity control. Limits the tree to at most $2^{\text{max_depth}}$ leaves.

2. Minimum Samples to Split (min_samples_split)

if len(samples) < min_samples_split:
    return CreateLeaf(samples)

Nodes with fewer samples than this threshold become leaves. Prevents tiny splits.

3. Minimum Samples per Leaf (min_samples_leaf)

if len(left_samples) < min_samples_leaf OR len(right_samples) < min_samples_leaf:
    skip this split (try next best, or make leaf if none valid)

Ensures each child will have sufficient samples. Often more important than min_samples_split.

4. Minimum Impurity Decrease (min_impurity_decrease)

if gain < min_impurity_decrease:
    return CreateLeaf(samples)

Only split if the improvement exceeds a threshold. Prevents marginal/noise-driven splits.

5. Pure Node

if all samples have the same label (classification) OR
   variance(targets) ≈ 0 (regression):
    return CreateLeaf(samples)

No split can improve a pure node. This is always checked in practice.

6. Maximum Leaf Nodes (max_leaf_nodes)

// Global constraint across entire tree
if current_leaf_count >= max_leaf_nodes:
    stop growing

Direct control over tree complexity. Requires best-first growth to use effectively (otherwise, depth-first would fill leaves unevenly).

7. Maximum Features (max_features)

Not a stopping condition per se, but limits features considered at each split:

features_to_try = RandomSample(all_features, max_features)
best_split = FindBestSplit(samples, features_to_try)

Used in Random Forests to decorrelate trees. Can lead to earlier stopping if no good split is found among sampled features.

Let's present the full recursive partitioning algorithm with all practical details included.

Production-Grade Pseudocode

class DecisionTree:
    def __init__(self, max_depth, min_samples_split, min_samples_leaf,
                 min_impurity_decrease, max_features):
        self.config = store all hyperparameters
        self.root = None
    
    def fit(self, X, y):
        self.n_features = X.shape[1]
        self.n_classes = len(unique(y))  // for classification
        self.root = self._build_tree(X, y, sample_indices=range(len(y)), depth=0)
    
    def _build_tree(self, X, y, sample_indices, depth):
        node = Node()
        node.n_samples = len(sample_indices)
        node.impurity = compute_impurity(y[sample_indices])
        
        // Compute prediction value for this node (used if it becomes a leaf)
        node.value = compute_prediction(y[sample_indices])
        
        // Check stopping conditions
        if self._should_stop(node, depth, y[sample_indices]):
            node.is_leaf = True
            return node
        
        // Find best split
        best_feature, best_threshold, best_gain = self._find_best_split(
            X, y, sample_indices
        )
        
        if best_gain <= self.config.min_impurity_decrease:
            node.is_leaf = True
            return node
        
        // Perform the split
        left_indices, right_indices = self._partition(
            X, sample_indices, best_feature, best_threshold
        )
        
        // Check min_samples_leaf constraint
        if len(left_indices) < self.config.min_samples_leaf or 
           len(right_indices) < self.config.min_samples_leaf:
            node.is_leaf = True
            return node
        
        // Record split information
        node.is_leaf = False
        node.feature = best_feature
        node.threshold = best_threshold
        
        // Recurse
        node.left = self._build_tree(X, y, left_indices, depth + 1)
        node.right = self._build_tree(X, y, right_indices, depth + 1)
        
        return node
    
    def _should_stop(self, node, depth, labels):
        if depth >= self.config.max_depth:
            return True
        if node.n_samples < self.config.min_samples_split:
            return True
        if node.impurity == 0:  // Pure node
            return True
        return False

The recursive nature of tree building has practical implications for memory and system limits.

Call Stack Depth

Each recursive call to _build_tree adds a frame to the call stack:

• Stack depth = current node depth + 1
• Maximum stack depth = tree height + 1

Typical limits:

• Python default recursion limit: 1,000
• Most systems can handle: 10,000+ with increased limit
• Practical trees rarely exceed depth 50

Stack frame contents:

• Function arguments (X, y, indices, depth)
• Local variables (node, best_split, left/right indices)
• Return address

For a tree of depth $h$, peak stack usage is $O(h)$ frames.

Iterative Alternatives

To avoid stack overflow for very deep trees, implementations can use explicit stacks:

def build_tree_iterative(X, y):
    root = create_pending_node(all_indices, depth=0, parent=None, is_left=None)
    stack = [root]
    
    while stack:
        node = stack.pop()
        
        if should_stop(node):
            finalize_as_leaf(node)
            continue
        
        feature, threshold = find_best_split(node.indices)
        
        if no_good_split:
            finalize_as_leaf(node)
            continue
        
        left_indices, right_indices = partition(node.indices, feature, threshold)
        
        node.feature = feature
        node.threshold = threshold
        
        node.left = create_pending_node(left_indices, node.depth+1, node, True)
        node.right = create_pending_node(right_indices, node.depth+1, node, False)
        
        stack.append(node.right)  # Push right first (LIFO = depth-first left)
        stack.append(node.left)
    
    return root

This achieves the same depth-first traversal without recursive calls.

Understanding the computational cost of recursive partitioning helps predict training time and identify bottlenecks.

Per-Node Cost

At each node with $n$ samples:

1. Compute node statistics: $O(n)$ — scan samples for impurity, class counts
2. Check stopping conditions: $O(1)$
3. Find best split: $O(d \cdot n \log n)$ — for $d$ features, using sorted sweep
4. Partition samples: $O(n)$ — separate left and right indices

Total per-node: $O(d \cdot n \log n)$

The dominant cost is finding the best split.

Total Training Cost

Key observation: Each sample passes through exactly one node at each level. If the tree has height $h$, each sample is processed in $O(d \log n)$ per level, across $h$ levels.

Balanced tree case (height $h \approx \log N$):

$$T_{\text{total}} = O\left( \sum_{\text{level }l=0}^{h} \text{(work at level } l) \right)$$

At each level, total samples across all nodes is $N$. Work per sample: $O(d \log N)$ (amortized sorting cost).

$$T_{\text{total}} = O(N \cdot d \cdot \log N \cdot h) = O(N \cdot d \cdot \log^2 N)$$

Unbalanced tree case (height $h \approx N$):

In the worst case (chain-like tree): $$T_{\text{total}} = O(N^2 \cdot d \cdot \log N)$$

This is why max_depth limits are important for training efficiency as well as generalization.

Memory Complexity

During training:

• Dataset: $O(N \cdot d)$ — feature matrix
• Labels: $O(N)$
• Index arrays: $O(N)$ — for tracking sample assignments
• Recursion stack: $O(h)$ frames

Final tree:

• Internal nodes: $O(|V_I|)$ each storing feature, threshold, pointers
• Leaf nodes: $O(|V_L|)$ each storing prediction values
• Total: $O(|V|)$ = $O(|V_L|)$ since $|V_I| = |V_L| - 1$

For a tree with $L$ leaves, memory is $O(L \cdot C)$ where $C$ is the cost per node.

Production implementations employ several optimizations to accelerate recursive partitioning.

Pre-sorting Features

Instead of sorting at each node, sort once at the root:

# At root:
for each feature j:
    sorted_indices[j] = argsort(X[:, j])

# At each node:
# Use sorted_indices to sweep through candidates without re-sorting

This converts $O(N \log N)$ sorting per node per feature to $O(N)$ traversal.

Trade-off: Requires $O(N \cdot d)$ storage for sorted indices.

Histogram-Based Splitting (LightGBM, XGBoost)

Bin continuous features into discrete buckets:

# Preprocessing:
bins[j] = create_bins(X[:, j], max_bins=256)
X_binned[:, j] = digitize(X[:, j], bins[j])

# At each node:
# Build histogram of gradient sums per bin (O(n))
# Find best split by scanning histogram (O(max_bins))

This reduces $O(n)$ per-feature to $O(\max_bins)$, dramatically faster for large $n$.

Parallel Split Finding

Splits for different features are independent:

# Parallel over features
best_splits = parallel_map(features, lambda j: find_best_split_for_feature(j))
best_overall = max(best_splits, key=lambda s: s.gain)

With $P$ processors and $d$ features, speedup is $\min(P, d)$.

Sample Caching

For computing impurity statistics, maintain running sums:

# Instead of recomputing from scratch:
class_counts = [count(y == k) for k in classes]  # O(n)

# Incrementally update:
class_counts[y[moved_sample]] -= 1  # O(1)
class_counts_other[y[moved_sample]] += 1  # O(1)

The sorted sweep algorithm exploits this for $O(1)$ instead of $O(n)$ per candidate threshold.

The recursive partitioning process creates a specific kind of partition with well-defined mathematical properties.

Sample Conservation

At each split: $$|\mathcal{D}{\text{left}}| + |\mathcal{D}{\text{right}}| = |\mathcal{D}_{\text{parent}}|$$

No samples are lost or duplicated. The partition is exhaustive and disjoint.

Impurity Monotonicity

After a split, the weighted average impurity of children is never greater than the parent's impurity:

$$\frac{n_L}{n} \mathcal{I}(\mathcal{D}_L) + \frac{n_R}{n} \mathcal{I}(\mathcal{D}_R) \leq \mathcal{I}(\mathcal{D})$$

This follows from the convexity of impurity measures (Gini, entropy).

Consequence: Impurity can only decrease (or stay constant) as we descend the tree. Leaves have minimal impurity given the data that reached them.

Path Uniqueness

Every sample follows exactly one path from root to leaf. The path is determined entirely by the sample's feature values and the thresholds along the way.

$$\text{path}(\mathbf{x}) = (r, v_1, v_2, \ldots, \ell)$$

Where each transition $v_i \to v_{i+1}$ is determined by: $$v_{i+1} = \begin{cases} v_i.\text{left} & \text{if } x_{j(v_i)} \leq \theta(v_i) \ v_i.\text{right} & \text{otherwise} \end{cases}$$

Hierarchical Refinement

Each level of the tree refines the previous level's partition:

• Level 0: Entire feature space (one region)
• Level 1: Two regions (after root split)
• Level 2: Up to four regions
• Level $l$: Up to $2^l$ regions

The partition becomes progressively finer as depth increases.