Why Measure Tree Complexity?
A regression tree represents a prediction rule by repeatedly splitting predictor space into regions and assigning a prediction to each terminal region. The number and arrangement of those regions affect how detailed the fitted function can be. Counting terminal nodes, internal nodes, and maximum depth gives three related but distinct descriptions of that structure.
These measurements describe the tree’s structure, not whether its predictions are accurate. A tree with many terminal nodes can represent a more finely divided partition than a small tree, while a deep path indicates that some observations are assigned by a long sequence of conditional decisions. The measures are aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus.
Counting Nodes and Measuring Depth
Start at the root, which contains the full predictor space before any split. If it is split, it becomes an internal node and its two children represent the resulting subregions. Either child may itself be split, creating more internal nodes and terminal regions. A node is counted once, regardless of how many observations fall into its region.
For a binary tree, let \(I\) be the number of internal nodes and \(L\) the number of terminal nodes. Every internal node has exactly two children; every terminal node has none. In particular, the root-only tree has \(I=0\), \(L=1\), and maximum depth 0.
This identity holds for every finite binary tree in which each split creates exactly two children. It is useful as a check on a node count, but it does not reveal where the nodes are located or how deep the tree is.
Why the Leaf–Internal-Node Identity Holds
A short count of the edges proves the identity. A tree with \(I+L\) total nodes has \(I+L-1\) edges: every node other than the root has exactly one edge connecting it to its parent. Alternatively, each of the \(I\) internal nodes contributes exactly two edges to its children, so the total number of edges is \(2I\). Equating these counts gives:
The same relationship can be understood by starting with a single terminal node. Each binary split turns one terminal node into an internal node and replaces it with two terminal nodes. Thus each split increases the number of leaves by one, so after \(I\) splits there are \(1+I\) leaves. Both arguments rely on the split having exactly two children; a structure with nodes that can have a different number of children need not satisfy this identity.
Worked Examples
Worked Example: Counting a Tree With an Uneven Shape
A hypothetical insurance severity tree first splits on annual mileage at the root. The low-mileage child is terminal. The high-mileage child is split on vehicle age; that split’s low-age child is terminal, and its high-age child is split on a claims-history score, producing two terminal children. Count the internal and terminal nodes and find the maximum depth.
Method. Record the split nodes and follow each root-to-leaf path. The common mistake to avoid is counting split operations but overlooking that each split also creates two child nodes.
The root mileage split is internal node 1 at depth 0. The high-mileage node is split on age, so it is internal node 2 at depth 1. The high-mileage, high-age node is split on claims history, so it is internal node 3 at depth 2. Therefore \(I=3\).
Now count the terminal nodes: the low-mileage child; the high-mileage, low-age child; and the two children created by the claims-history split. Thus \(L=1+1+2=4\). The deepest terminal nodes are reached after three edges from the root, so the maximum depth is 3.
Check. The identity gives \(L=I+1=3+1=4\), agreeing with the direct count. The tree has four terminal regions, three split nodes, and maximum depth 3.
Worked Example: Same Size, Different Maximum Depth
Compare two hypothetical trees, each with four terminal nodes. Tree A has a root split, and each of the root’s two children is split once. Tree B has a root split; its left child is terminal, while its right child is split, and that split’s right child is split once more. Find the number of internal nodes and maximum depth for each tree.
Method. Count internal nodes from the described splits, then count edges along the longest root-to-terminal path. The mistake to avoid is assuming that equal leaf counts imply equal depths.
For Tree A, the root and its two children are internal, so \(I_A=1+2=3\). Each child split produces two terminal children, giving four terminal nodes in total. Each root-to-leaf path has two edges, so the maximum depth is 2. The identity check is \(L_A=I_A+1=4\).
For Tree B, the root, its right child, and that child’s right child are internal, so \(I_B=3\). Its terminal nodes are the root’s left child, the right child’s left child, and the two children of the deepest split: \(L_B=1+1+2=4\). The deepest leaves are reached by three edges, so the maximum depth is 3. Again, \(L_B=I_B+1=4\).
Check. Both trees have four terminal regions and three internal nodes, but Tree B has greater maximum depth. The leaf count and internal-node count describe the tree’s total size; depth describes how unevenly those splits are arranged along paths.
Worked Example: Reconstructing Counts From Paths
A hypothetical pricing tree follows these rules. At the root, split on policy duration. Split the left child on a renewal indicator, leaving both of its children terminal. Split the right child on a coverage category; its left child is terminal and its right child is split on a risk score, producing two terminal children. Find \(I\), \(L\), and maximum depth.
Method. List each split node once, then enumerate the terminal nodes and count the longest path in edges. This avoids counting the two children of a split as additional split nodes unless they are themselves split.
The internal nodes are: the root (depth 0), its left child (depth 1), its right child (depth 1), and the right child’s right child (depth 2). Therefore \(I=4\).
The terminal nodes are the two children of the left-side renewal split, the left child of the right-side coverage split, and the two children of the risk-score split. Therefore \(L=2+1+2=5\). The deepest leaves are three edges from the root, so maximum depth is 3.
Check. Since \(I=4\), the identity requires \(L=I+1=5\), which matches the direct count. The tree has five terminal regions, four internal nodes, and maximum depth 3.
Interpreting the Three Measures
The three counts answer different questions. Terminal nodes count the regions for which the tree can provide terminal predictions. Internal nodes count the splits that define those regions. Maximum depth records the longest sequence of decisions needed to reach a prediction. For a binary tree, \(I\) and \(L\) are tied by \(L=I+1\), so they are not independent measures of total size. Maximum depth is not determined by that identity.
| Measure | What it counts or describes | What it does not tell you by itself |
|---|---|---|
| Terminal nodes \(L\) | The number of final regions and terminal predictions | How those regions are arranged across the tree |
| Internal nodes \(I\) | The number of split decisions | How many decisions lie on the longest path |
| Maximum depth | The longest root-to-terminal path, in edges | The total number of regions or splits |
More terminal nodes allow a tree to distinguish more regions of predictor space. This does not guarantee that every terminal node has a different numerical prediction: different regions can have equal fitted values. Nor does a larger count alone establish better predictive performance. Depth gives complementary structural information. A tree can be relatively deep but have few leaves if only one branch is repeatedly split, or have many leaves distributed across comparatively short paths.
Depth conventions must be stated. Here the root is at depth 0, and depth counts edges, not nodes. If a diagram labels the root as “level 1,” its terminal level number is one greater than the edge-based depth. For example, a terminal node at level 4 under that convention has depth 3. When interpreting a reported number, check which convention is being used.
Common Exam Trap
A frequent error is to report the number of internal nodes as the number of terminal regions. Consider a binary tree with five internal nodes. The wrong calculation is \(L=I=5\), which confuses split locations with the regions at the ends of the splits. The correct calculation is \(L=I+1=5+1=6\). A direct diagram count should also find six leaves. Another error is to infer maximum depth from the leaf count alone: Tree A and Tree B above both have four leaves, but their maximum depths differ.
Check Your Understanding
For each tree, use root depth 0 and report the requested counts. Check binary-tree counts with \(L=I+1\).
- A root is split once and both children are terminal. Find \(I\), \(L\), and maximum depth. (Answer: \(I=1\), \(L=2\), maximum depth \(=1\).)
- The root is split. Its left child is split into two terminal nodes, while its right child is terminal. Find all three measures. (Answer: \(I=2\), \(L=3\), maximum depth \(=2\).)
- A binary tree is perfectly balanced: the root is split, both children are split, and all four resulting children are terminal. Find \(I\), \(L\), and maximum depth. (Answer: \(I=3\), \(L=4\), maximum depth \(=2\).)
- A binary tree has six terminal nodes. How many internal nodes does it have, and can its maximum depth be determined from the leaf count alone? (Answer: \(I=5\); no, maximum depth is not determined by the leaf count alone.)
- The root is split. Its left child is split into two terminal nodes. Its right child is split; that split’s left child is terminal and its right child is split into two terminal nodes. Find \(I\), \(L\), and maximum depth. (Answer: \(I=4\), \(L=5\), maximum depth \(=3\).)