Decision Trees and Recursive Partitioning

A decision tree is a hierarchical model that partitions the input feature space $\mathcal{X} \subseteq \mathbb{R}^d$ into a set of disjoint axis-aligned regions $R_1, \dots, R_M$, and assigns a constant prediction $\hat{y}_m$ to every point falling in region $R_m$. Structurally, the tree is a rooted binary (or occasionally multi-way) tree in which every internal node stores a split rule of the form "feature $j$ $\le$ threshold $t$", and every leaf node stores a prediction — a class label or class-probability vector for classification, a real number (typically the mean of training targets in that region) for regression. The defining algorithmic technique is recursive partitioning, also called recursive binary splitting. Starting from the full training set at the root, the algorithm searches over all features and all candidate thresholds for the single split that best improves some impurity or loss criterion, applies that split to divide the data into two child nodes, and then repeats the entire search independently and recursively on each child. Because the algorithm commits to the locally best split at every step without reconsidering earlier choices, it is a greedy algorithm: it never backtracks to ask whether a different split earlier in the tree would have led to a better tree overall. The impurity criterion quantifies how "mixed" the labels are within a node. For classification, common choices are the Gini index $\text{Gini}(p) = \sum_k p_k(1-p_k)$ and entropy $-\sum_k p_k \log p_k$, both minimized at zero when a node is pure (all one class) and maximized when classes are equally mixed. For regression, the natural criterion is the residual sum of squares (variance) within a node. The tree's job at each split is to choose the feature and threshold that most reduces this impurity, weighted by the size of the resulting children — a quantity closely related to information gain, developed in depth elsewhere. Because splits are always of the form "one feature compared to one threshold," the resulting regions are always axis-aligned hyper-rectangles — a geometric property with real consequences for what shapes of decision boundary a tree can and cannot represent efficiently.

Building a tree requires two nested procedures: a routine that finds the best single split for a given node's data, and a routine that recursively applies this splitting until some stopping condition is met. Prediction, given a fitted tree, is simply a root-to-leaf walk following the split rules.

Finding the best split. For every candidate feature $j$ and every candidate threshold $t$ (in practice, the midpoints between consecutive sorted distinct values of feature $j$), the algorithm partitions the current node's samples into a left group ($x_j \le t$) and a right group ($x_j > t$), computes the impurity of each group, and combines them into a weighted impurity:

The split $(j^*, t^*)$ chosen is the one minimizing $Q(j,t)$, equivalently maximizing the impurity reduction relative to the parent node.

Recursive growth. Once the best split is found, the node's data is divided accordingly, and the same search-and-split procedure is invoked independently on each child. The recursion halts at a node — turning it into a leaf — when any of several stopping conditions holds: the node is already pure, it has fewer samples than a minimum threshold, the tree has reached a maximum depth, or no candidate split improves impurity by more than some tolerance. ``` function BUILD_TREE(D, depth):

# D: set of (x, y) training pairs at this node if STOPPING_CONDITION(D, depth): return LEAF(predict = AGGREGATE(D)) # majority class or mean target best_gain <- -infinity best_split <- None for each feature j in 1..d: sort D by feature j # O(n log n) per feature for each candidate threshold t (midpoints of adjacent sorted values): D_L, D_R <- partition D by (x_j <= t) if D_L empty or D_R empty: continue gain <- IMPURITY(D) - WEIGHTED_IMPURITY(D_L, D_R) if gain > best_gain: best_gain <- gain best_split <- (j, t, D_L, D_R) if best_gain <= 0: # no useful split found return LEAF(predict = AGGREGATE(D)) (j, t, D_L, D_R) <- best_split left_child <- BUILD_TREE(D_L, depth + 1) right_child <- BUILD_TREE(D_R, depth + 1) return NODE(feature = j, threshold = t, left = left_child, right = right_child)

function PREDICT(tree, x): if tree is a LEAF: return tree.predict if x[tree.feature] <= tree.threshold: return PREDICT(tree.left, x) else: return PREDICT(tree.right, x)

function STOPPING_CONDITION(D, depth): return (IMPURITY(D) == 0) # pure node or (|D| < min_samples_split) # too few samples or (depth >= max_depth) # depth limit reached ``` A subtlety worth making explicit: `IMPURITY(D)` for classification is typically Gini or entropy over the class distribution in `D`; for regression it is the variance of the target values in `D`, and `AGGREGATE` returns the mean rather than a majority vote. The algorithm is otherwise identical across both settings — this is why decision trees are often described as a single unified framework rather than two separate methods (CART, Classification and Regression Trees, was designed explicitly this way). The diagram below shows a tiny fitted tree alongside the feature-space partition it induces, making explicit that every leaf corresponds to exactly one axis-aligned rectangle.

Time complexity. At a single node containing $n$ samples and $d$ features, evaluating all candidate splits for one feature requires sorting that feature's values ($O(n \log n)$) and then a single linear scan accumulating class counts (or sum/sum-of-squares for regression) to evaluate impurity at each candidate threshold in $O(n)$ total. Across $d$ features this is $O(d \cdot n \log n)$ work per node. Summing over all nodes at a single depth level touches every training sample exactly once collectively (each sample lives in exactly one node per depth level), giving $O(d \cdot n \log n)$ work per level. With $D$ levels of depth, total training time is

If the tree is grown to full depth on non-degenerate data, $D = O(\log n)$ in the balanced case, giving $O(d\, n \log^2 n)$; in the worst case (highly unbalanced splits, e.g. one sample peeled off per level) $D = O(n)$, giving a much worse $O(d\, n^2 \log n)$. In practice, presorting each feature once at the root and reusing sorted order via masks through the recursion (rather than re-sorting at every node) is a standard optimization that removes the repeated $\log n$ factor, common in production implementations.

Space complexity. Storing the tree itself costs $O(\text{number of nodes})$, which is at most $O(n)$ since a tree grown to purity has at most $n$ leaves (each leaf must contain at least one sample). Auxiliary space during training for sorted indices is $O(n \cdot d)$.

Prediction complexity. A single prediction walks one root-to-leaf path, costing $O(\text{depth})$, which is $O(\log n)$ for a balanced tree and $O(n)$ in the worst case. This is why tree depth is not just a statistical concern (overfitting) but also a latency concern in deployed systems.

Correctness — in what sense is the greedy algorithm "correct"? Finding the globally optimal decision tree (the tree, among all trees of a given size, that minimizes training impurity) is known to be NP-hard even for simple impurity measures — the search space of possible partitions grows combinatorially with depth. Recursive partitioning does not solve this problem exactly; it is explicitly a greedy heuristic. Its "correctness" claim is therefore weaker and more honest: at each step, it computes the split that is provably optimal for that node in isolation, because the split search exhaustively enumerates every feature and every distinct threshold and evaluates the exact impurity reduction — there is no approximation within a single split decision. The invariant maintained throughout the recursion is: > At every node, the chosen split is the impurity-minimizing split among all axis-aligned single-feature thresholds, given the data that has already been routed to that node by earlier splits. This invariant guarantees local optimality at each decision but not global optimality of the resulting tree, since an early split that looks locally weak might have enabled a much stronger downstream split that the greedy algorithm never considers. The practical justification for using greedy search anyway is computational: exhaustive search over all possible tree structures of depth $D$ is exponential in $D$, while greedy recursive partitioning is polynomial, as derived above — an enormous, usually decisive, efficiency gain for a small, well-documented loss in optimality.

Monotonic impurity decrease. One can prove that impurity is non-increasing as splits accumulate: since the algorithm only accepts a split when $Q(j,t) < \text{Impurity}(\text{parent})$ (equivalently `best_gain > 0`), every accepted split strictly decreases weighted impurity, and impurity is bounded below by zero. This guarantees the recursion terminates (impurity cannot decrease forever) and that training-set impurity is a non-increasing function of tree depth — the formal reason why an unconstrained tree can always be driven to zero training error (each leaf reduced to single-sample purity), which is precisely the mechanism behind decision-tree overfitting.

Consider a small dataset for predicting whether a customer churns, using two features: tenure (months) and monthly charges ($).

The root node contains 6 samples: 3 "Yes", 3 "No". Using Gini impurity, $\text{Gini}(\text{root}) = 1 - (0.5^2 + 0.5^2) = 0.5$.

Step 1 — evaluate splits on Tenure. Sorted tenure values: 1, 2, 3, 24, 30, 40. Candidate thresholds are midpoints: 1.5, 2.5, 13.5, 27, 35. Consider threshold $t = 13.5$ (Tenure $\le 13.5$): left group = {A, B, E} all "Yes" ($\text{Gini}=0$); right group = {C, D, F} all "No" ($\text{Gini}=0$). Weighted impurity:

This is a perfect split — impurity drops from 0.5 to 0, a gain of 0.5, the maximum possible.

Step 2 — evaluate splits on Monthly charges (for comparison). Sorted values: 30, 40, 45, 90, 95, 100. Threshold $t=67.5$: left = {C, E, D} → labels {No, Yes, No}, Gini $= 1 - ((2/3)^2 + (1/3)^2) = 0.444$; right = {A, B, F} → {Yes, Yes, No}, Gini $=0.444$. Weighted impurity $Q = 0.444$, gain only $0.5 - 0.444 = 0.056$ — far worse than the Tenure split.

Step 3 — select best split. The algorithm scans all thresholds on both features (and would continue checking 1.5, 2.5, 27, 35 on Tenure and the remaining thresholds on Monthly Charges), but none beats the perfect gain of 0.5 found at Tenure $\le 13.5$. The root split is therefore Tenure $\le 13.5$.

Step 4 — recurse. Both resulting children ({A,B,E} and {C,D,F}) are already pure (Gini $=0$), so `STOPPING_CONDITION` triggers immediately for each, and they become leaves: "Tenure $\le 13.5$ → predict Churn = Yes" and "Tenure $> 13.5$ → predict Churn = No". The final tree has depth 1 with two leaves — despite two candidate features, the algorithm needed only one split to perfectly classify this training set, illustrating how a single well-chosen threshold can dominate the search even when other features look superficially informative. A held-out customer with Tenure = 15, Monthly charges = 85 would be routed right at the root (15 > 13.5) and predicted No churn — notice this prediction ignores the high monthly charge entirely, since the tree never needed that feature on the training data, a reminder that trees only use features that improved impurity on the data they were built from.

The recursive-partitioning idea for prediction was formalized independently by statisticians in the 1960s–80s, converging on the algorithms still taught today.

Decision trees underpin some of the most heavily used machine learning software in production today, largely as components of ensembles rather than as standalone models. Gradient-boosted tree libraries such as XGBoost, LightGBM, and CatBoost — workhorses of tabular-data competitions and industrial systems for fraud detection, click-through-rate prediction, and credit risk scoring — build hundreds or thousands of shallow trees sequentially, each correcting the errors of the last. Random forests, used widely in bioinformatics, remote sensing, and recommendation systems, average many independently grown deep trees to control variance. Standalone single trees remain popular wherever regulatory or human interpretability requirements demand an explicit, auditable decision path, such as clinical decision support tools and certain credit-approval pipelines. The core mechanics described here — split search, impurity reduction, recursive growth, and the overfitting risk of unconstrained depth — are exactly the mechanics that later articles refine: quantifying split quality with Entropy and Information Gain, controlling tree complexity through Tree Pruning and Complexity Control, and reducing variance by combining many trees via Bagging and the Bootstrap.

Ask the tutor: How does changing the impurity measure from Gini to entropy actually change which splits a decision tree chooses in practice?