Tree Topology, Split Rules, and Leaf Counts

Topology and Split Rules

A tree-based estimator is built by repeatedly dividing an input region into two parts. To reason about what the tree can represent, separate two ingredients: topology, which records which nodes are connected, and split rules, which specify how an input is sent from a node to one of its children. The topology determines how many terminal regions there are; the rules determine the geometry of those regions.

Let the root domain be \(A_0\subseteq\mathbb{R}^d\), where \(d\) is the number of input coordinates. A node in the tree represents the region reached by inputs that have followed the path from the root to that node. At an internal node, one coordinate is compared with a threshold. The comparison sends an input to one of two children.

The convention assigning equality to the left child makes the rule unambiguous, including when an input coordinate equals a threshold. The labels “left” and “right” describe the two branches; they do not mean that the resulting regions must look left and right in a drawing. The topology can be recorded without split rules, and split rules can be attached to a fixed topology afterward.

From Paths to Cells

A leaf corresponds to a path that starts at the root and ends at that leaf. Every internal node on the path contributes one inequality: a left turn contributes \(x_{j_v}\le t_v\), and a right turn contributes \(x_{j_v}>t_v\). The leaf cell is the part of \(A_0\) satisfying all the inequalities on its path. Thus a cell is an intersection of the root domain with coordinate-threshold constraints. Its description need not involve every coordinate, and repeated splits on the same coordinate can impose several bounds on that coordinate.

For example, after first restricting a coordinate to \(x_1\le 2\), a later split on that same coordinate at 5 cannot create two nonempty children within that region: every input already satisfies \(x_1\le 2\). A binary branching structure by itself therefore does not guarantee that all its leaf cells are nonempty. To obtain a partition into nonempty cells, each split must divide its current region into two nonempty parts. Even when some cells are empty, the topology still has its usual number of leaves.

The Leaf-Count Identity

For a finite full binary tree, each internal node contributes exactly two child connections. A second count of those connections gives a short proof of the relation between internal nodes and leaves.

Proof. A finite tree with \(S+L\) nodes has \(S+L-1\) edges: every node other than the root has exactly one edge connecting it to its parent. On the other hand, each of the \(S\) internal nodes has exactly two children, and leaves have none, so counting edges by their parent gives \(2S\) edges. Equating the two counts yields \(S+L-1=2S\), hence \(L=S+1\). \(\square\)

The theorem is topological: it does not depend on the coordinate dimension, the values of the thresholds, or the shape of the induced regions. It also gives the converse count \(S=L-1\). A tree with seven leaves must have six internal nodes if it is finite and full binary.

Why the Leaf Cells Form a Partition

The split convention ensures that each input follows exactly one path. At an internal node, the conditions \(x_j\le t\) and \(x_j>t\) are mutually exclusive, and together they cover every real value of \(x_j\). Applying that fact successively down the tree proves the partition property.

Proof. Start at the root. Its region is \(A_0\), so it covers the root domain. At any internal node with region \(A\), the child regions are \(A\cap\{x:x_j\le t\}\) and \(A\cap\{x:x_j>t\}\). They are disjoint because no real number is both at most \(t\) and greater than \(t\). Their union is \(A\), because every real number is either at most \(t\) or greater than \(t\). Replacing a node’s region by its two child regions therefore preserves both coverage and disjointness. Since the tree is finite, repeating this replacement until no internal nodes remain leaves precisely the leaf regions. They are disjoint and cover \(A_0\). If each split produces two nonempty regions, all resulting leaf cells are nonempty as well. \(\square\)

Depth and Shape

The number of leaves is not enough to specify the shape of a tree. Define the depth of a node as the number of edges on its path from the root, so the root has depth zero. The maximum depth \(D\) is the largest leaf depth. A tree may have many short paths and one long path, or it may branch evenly.

A useful bound follows from the branching structure: if the maximum depth is \(D\), then \(L\le 2^D\). To see this, at depth zero there is at most one node. Each node has at most two children, so by induction there are at most \(2^k\) nodes at depth \(k\). Every leaf is at one of the depths \(0,\ldots,D\), but the sharper leaf bound \(2^D\) follows by extending any leaf at depth less than \(D\) into a full binary subtree until depth \(D\); this does not decrease the number of leaves, and a full tree with all leaves at depth \(D\) has \(2^D\) leaves. Equivalently, the maximum is attained by the complete tree whose leaves all occur at depth \(D\). The bound concerns topology, not the sizes or balance of the cells.

Common Pitfalls and Why the Distinctions Matter

• Counting split rules rather than nodes. A threshold comparison at each internal node is one split, so \(S\) counts internal nodes, not branches or leaves. A full binary tree has \(2S\) child edges, but only \(S\) split nodes.
• Assuming every binary node creates two nonempty regions. The topology gives two children, but a threshold may place the entire parent region on one side. Check the split against the current region, not merely against the root domain.
• Assuming a leaf count describes the geometry. The identity \(L=S+1\) says nothing about threshold locations, cell widths, or whether different cells have similar sizes. Those depend on the split rules and the root domain.
• Forgetting the boundary convention. If both children were defined using non-strict inequalities, points on the threshold could be assigned twice. Assigning equality to one child avoids this ambiguity.

The topology–geometry distinction gives a compact way to describe a tree: list its internal-node connections, then attach a coordinate and threshold to each internal node. The resulting leaf cells are exactly the regions induced by those paths. This representation is useful whenever tree structure, number of terminal regions, and input-space subdivision need to be discussed separately.