Counting Tree Partitions by Leaf Budget

Why Count Tree Partitions?

A tree with a small number of leaves can still be chosen in many ways: its root split can use different coordinates and thresholds, and later splits depend on which observations reach each node. Counting the resulting partitions gives a way to describe the size of the candidate class on a particular finite sample. The count is also useful to keep distinct from the count of tree descriptions: several trees can induce exactly the same grouping of the observations.

We count partitions of the observed cases, not all possible rectangular regions in the feature space. In particular, two thresholds that place the same observations on the same sides of a split are indistinguishable for this count, even if the thresholds have different numerical values.

Definition: Let $x_1,\ldots,x_n\in\mathbb{R}^d$ be a fixed sample of feature vectors. An axis-aligned split at a node uses a coordinate $j\in\{1,\ldots,d\}$ and a threshold $t$, sending observations with $x_{ij}\le t$ to one child and observations with $x_{ij}>t$ to the other. The sample partition induced by a tree is the collection of nonempty groups of observation indices that reach its leaves. A leaf budget $L$ permits at most $L$ nonempty groups.

Throughout, empty branches are removed: a split that sends no observations to one child does not change the sample partition and can be pruned. Thus, every split in the reduced tree has two nonempty children. This convention makes the count a count of effective sample partitions, rather than of arbitrary thresholds or redundant nodes. There can be at most $n$ nonempty leaves, so set $L_*=\min(L,n)$.

How Many Splits Can a Node Make?

Suppose a node contains $m$ observations. For one coordinate, sort their feature values. A threshold that sends observations to both children can only separate the observations between two consecutive distinct values. There are at most $m-1$ such gaps. Repeating this argument over the $d$ coordinates gives at most $d(m-1)$ candidate split assignments on those observations, and hence at most $d(n-1)$ at any node in the tree.

The count is an upper bound, not necessarily the exact number. Tied coordinate values reduce the number of available gaps; different coordinates can also produce the same grouping. At the other extreme, counting all coordinate-gap choices independently at every node may count many choices that are impossible for the particular observations reaching that node. Both effects make the bound convenient but potentially loose.

Lemma: On a fixed set of $m\ge2$ observations in $\mathbb{R}^d$, the number of distinct nonempty two-child sample splits obtainable by an axis-aligned threshold is at most $d(m-1)$.

Proof. Fix a coordinate. If its $m$ values are sorted, a nonempty two-child split can occur only between consecutive distinct values. There are at most $m-1$ such positions. Each position determines at most one grouping of the observations on the two sides. Taking the union over $d$ coordinates gives at most $d(m-1)$ groupings; overlap between coordinates can only decrease the number. $\square$

Worked Example: Candidate Splits at a Node

A node contains $m=6$ observations with two features, so $d=2$. The lemma gives at most $2(6-1)=10$ distinct candidate sample splits. For instance, if the first feature has sorted values $1,2,2,5,7,9$, it has only four distinct-value gaps: after $1$, $2$, $5$, and $7$. If the second feature has six distinct values, it has five gaps. The total in this case is at most $4+5=9$, which is below the general bound of 10. Any split grouping repeated across the two coordinates would reduce the actual number further.

Counting Tree Shapes and Partitions

A reduced binary tree with $k$ leaves has exactly $k-1$ internal nodes. To see this, let $I$ be its number of internal nodes. Each internal node has two children, so the tree has $2I$ edges. A finite tree with $I+k$ nodes has $I+k-1$ edges. Equating these counts gives $2I=I+k-1$, hence $I=k-1$.

The number of ordered full binary tree shapes with $k$ leaves is the Catalan number $\mathrm{Cat}_{k-1}=\frac{1}{k}\binom{2k-2}{k-1}$. “Ordered” means the left and right child positions are distinguished, as they are for a threshold split. Once a shape is fixed, each of its $k-1$ internal nodes has at most $d(n-1)$ possible sample split assignments. Some assignments counted this way may be inconsistent with the observations that reach a node, but this only increases the bound.

Theorem: For $n\ge2$, $d\ge1$, and a leaf budget $L\ge1$, the number $N_{n,d}(L)$ of distinct sample partitions induced by axis-aligned trees is bounded by $$ N_{n,d}(L)\ \le\ \sum_{k=1}^{L_*}\mathrm{Cat}_{k-1}\,[d(n-1)]^{k-1}, \qquad L_*=\min(L,n). $$

Proof. First count trees with exactly $k$ nonempty leaves. Each reduced tree has $k-1$ internal nodes. There are $\mathrm{Cat}_{k-1}$ possible ordered shapes. For each fixed shape, expose the nodes in any fixed traversal order, such as root first and then recursively left subtree before right subtree. Given the observations reaching a node, its split has at most $d(n-1)$ possible sample assignments by the lemma. Thus there are at most $[d(n-1)]^{k-1}$ assignments to the internal nodes of that shape. This multiplication remains an upper bound even though the possible choices at a later node depend on earlier splits: for each partial assignment, the number of continuations at the next node is at most $d(n-1)$. Therefore the number of tree descriptions with $k$ leaves is at most $\mathrm{Cat}_{k-1}[d(n-1)]^{k-1}$. Every induced sample partition comes from at least one such tree, so the number of distinct partitions cannot exceed the number of descriptions. Summing over $k=1,\ldots,L_*$ proves the result. $\square$

The theorem counts trees first and partitions second. The map from a tree description to its induced sample partition need not be one-to-one. Consequently, the theorem is an upper bound even if the tree-description count itself were exact.

Worked Example: A General Bound for Eight Observations

Suppose $n=8$, $d=3$, and $L=3$. Here $L_*=3$, and the maximum split count per internal node is $d(n-1)=3(7)=21$. For exactly one leaf there is one partition. For exactly two leaves, there is one ordered shape and at most 21 split choices. For exactly three leaves, there are $\mathrm{Cat}_2=2$ shapes, each with two internal nodes, and at most $21^2$ split assignments. Therefore $$ N_{8,3}(3)\le 1+21+2(21^2) =1+21+882 =904. $$ This is a valid, deliberately generous bound. In an actual sample, a root split leaves fewer than eight observations at each child, so the second split usually has fewer than 21 choices. Moreover, distinct tree descriptions can induce the same partition.

An Exact Count in One Dimension

In one dimension, every leaf corresponds to an interval, so the observations in each leaf form a consecutive block in sorted order. If the $n$ observed feature values are distinct, a partition into $k$ nonempty blocks is determined by choosing $k-1$ of the $n-1$ gaps between consecutive observations. Every such choice can be realized by a threshold tree: split at one chosen gap, then recursively split the resulting interval groups at their remaining chosen gaps.

Worked Example: Six Distinct Values and Three Leaves

Let the six one-dimensional observations have distinct sorted values $x_{(1)}<x_{(2)}<\cdots<x_{(6)}$. There are five gaps, and a three-leaf partition chooses two of them. Hence the exact number of partitions into exactly three nonempty leaves is $$ \binom{5}{2}=\frac{5\cdot4}{2\cdot1}=10. $$ For example, choosing the gaps after $x_{(2)}$ and $x_{(4)}$ gives the three blocks $\{x_{(1)},x_{(2)}\}$, $\{x_{(3)},x_{(4)}\}$, and $\{x_{(5)},x_{(6)}\}$. A root split at either chosen gap, followed by a split of the child containing the other gap, realizes this partition. The same argument realizes every pair of gaps, and different pairs give different blocks, confirming the exact count.

Split Order Can Change the Tree Without Changing the Partition

The order of splits matters to a tree’s structure because each split determines which observations are available for later splits. But a different order need not change the final sample partition. The following example shows why counting split sequences as though each produced a new partition can overcount.

Worked Example: Two Split Orders, One Sample Partition

Take four feature vectors $(0,0),(0,1),(1,0),(1,1)$ in $\mathbb{R}^2$, and use threshold $0.5$ whenever splitting either coordinate. In the first tree, split on the first coordinate at the root, then split on the second coordinate within each child. The four leaves contain, respectively, $(0,0)$, $(0,1)$, $(1,0)$, and $(1,1)$.

In the second tree, split on the second coordinate at the root, then split on the first coordinate within each child. The leaves again contain exactly those four singleton groups. The root coordinate and the sequence of internal splits differ, but both trees induce the same partition of the four observation indices into singletons. Thus, this partition has at least two tree descriptions.

This distinction is important when interpreting the bound. It controls the number of possible partitions from above, not the number of unique geometric tree structures or the number of different numerical thresholds. For learning theory, the finite-sample partition count is a useful measure of how many groupings a tree class can produce; it is not by itself a count of all predictors, since leaf values can vary even when the partition is fixed.

Common Mistake: Treating Every Split Sequence as a New Partition

Wrong reasoning: “If I can describe many different orders of coordinate splits, then I have that many distinct partitions.” The four-point example shows the problem: switching the order of the two coordinate splits produced a different tree description but the same grouping of observations.

Correction: To bound the number of partitions, it is safe to count tree descriptions and use that count as an upper bound, because every partition is represented by a tree. But it is not safe to claim that this upper bound is an exact partition count. Duplicate descriptions of the same partition can make it loose. Similarly, the number of internal nodes for $k$ leaves is $k-1$, not $k$; the split-choice factor should be raised to $k-1$.

Key takeaway: With $k$ leaves, a reduced binary tree has $k-1$ effective splits. There are at most $d(n-1)$ sample split choices at each internal node and $\mathrm{Cat}_{k-1}$ ordered shapes, giving a convenient upper bound on the number of partitions. Different split orders can represent the same partition, so this count need not be sharp.

Check Your Understanding

Use the distinction between a tree description and its induced sample partition in your answers.

Why can a node containing $m$ observations have no more than $d(m-1)$ distinct nonempty sample splits?
A reduced binary tree has five nonempty leaves. How many internal nodes does it have, and why?
For $n=10$, $d=2$, and exactly two leaves, what upper bound does the split-counting argument give?
In one dimension with seven distinct observations, how many partitions into four nonempty interval blocks are possible?
Why is counting tree descriptions a valid upper-bound strategy, even when different split orders lead to the same partition?