Tree Structure

Decision trees are one of the most intuitive and powerful constructs in machine learning. Unlike the opaque weight matrices of neural networks or the abstract hyperplanes of SVMs, decision trees provide a transparent, interpretable model that mirrors how humans naturally reason about decisions—through a series of sequential, hierarchical choices.

Consider how a physician diagnoses a patient: Is there a fever? If yes, is there a cough? If yes, is it productive or dry? Each question refines the diagnosis, narrowing down possibilities until a conclusion is reached. This is precisely how a decision tree operates—a cascade of binary decisions that partition the feature space into regions of homogeneous predictions.

Understanding the structural anatomy of decision trees is foundational to everything that follows: splitting criteria, growing algorithms, pruning strategies, and the ensemble methods (Random Forests, Gradient Boosting) that dominate modern machine learning competitions.

A decision tree is a supervised learning model that represents a function mapping input features to output predictions through a hierarchical tree structure. Formally, a decision tree $T$ consists of:

$$T = (V, E, r, \phi, \psi)$$

Where:

• $V$: Set of vertices (nodes) partitioned into internal nodes $V_I$ and leaf nodes $V_L$, such that $V = V_I \cup V_L$
• $E$: Set of edges connecting parent nodes to child nodes
• $r \in V_I$: The root node (unique node with no parent)
• $\phi: V_I \rightarrow \mathcal{F} \times \Theta$: A splitting function assigning each internal node a feature and threshold
• $\psi: V_L \rightarrow \mathcal{Y}$: A prediction function assigning each leaf node an output value

The tree is directed (edges flow from root toward leaves), acyclic (no loops), and rooted (exactly one root node). For binary decision trees, each internal node has exactly two children, creating a binary branching structure.

The Prediction Path:

Given an input vector $\mathbf{x} \in \mathcal{X}$, prediction proceeds by traversing the tree from root to leaf:

1. Start at root node $r$
2. At each internal node $v$ with split function $\phi(v) = (f_j, \theta)$:
   • If $x_j \leq \theta$, proceed to left child
   • If $x_j > \theta$, proceed to right child
3. Continue until reaching a leaf node $\ell \in V_L$
4. Return prediction $\psi(\ell)$

This process partitions the feature space $\mathcal{X}$ into $|V_L|$ disjoint regions, each corresponding to a unique root-to-leaf path.

Every decision tree comprises three fundamental node types, each serving a distinct purpose in the prediction process. Understanding these roles is essential for grasping tree mechanics.

The Root Node

The root node is the entry point of every decision tree—the starting position from which all predictions flow. It possesses several unique properties:

• No parent: The root is the only node without an incoming edge
• Universal coverage: Every training example passes through the root
• Maximum impurity context: Before any splits, the root contains the full diversity of the training data
• First split importance: The feature selected at the root is often the most discriminative for the overall prediction task

In mathematical terms, if the training set is $\mathcal{D} = {(\mathbf{x}i, y_i)}{i=1}^{N}$, the root node contains all $N$ samples. The split at the root creates the most impactful information gain because it operates on the maximum possible sample set.

Internal Nodes (Decision Nodes)

Internal nodes are the decision-makers of the tree. Each internal node:

1. Receives samples from its parent node (a subset of the parent's samples)
2. Applies a split criterion based on a feature and threshold: "Is $x_j \leq \theta$?"
3. Routes samples to child nodes based on the split decision

The splitting function at internal node $v$ can be represented as:

$$\text{split}v(\mathbf{x}) = \begin{cases} \text{left} & \text{if } x{j(v)} \leq \theta(v) \ \text{right} & \text{if } x_{j(v)} > \theta(v) \end{cases}$$

Where $j(v)$ is the feature index and $\theta(v)$ is the threshold for node $v$.

Critical properties of internal nodes:

• Sample subset: Each internal node operates on a strict subset of its parent's samples (except root)
• Monotonic refinement: As depth increases, nodes contain fewer samples but more homogeneous labels
• Local optimization: Each split is chosen to maximize information gain at that node, given available samples
• Feature reuse allowed: The same feature can be used at multiple nodes (important for capturing nonlinear relationships)

Leaf Nodes (Terminal Nodes)

Leaf nodes are where predictions are made. They have no children and no split criterion—only a prediction value:

For Classification: $$\psi(\ell) = \text{mode}{y_i : (\mathbf{x}i, y_i) \in \mathcal{D}\ell}$$

The leaf predicts the majority class among training samples that reached it. Alternatively, it can output class probabilities: $$P(Y = k | \mathbf{x} \in \ell) = \frac{|{i : y_i = k, \mathbf{x}i \in \ell}|}{|\mathcal{D}\ell|}$$

For Regression: $$\psi(\ell) = \frac{1}{|\mathcal{D}\ell|} \sum{(\mathbf{x}i, y_i) \in \mathcal{D}\ell} y_i$$

The leaf predicts the mean of target values for training samples that reached it.

Critical properties of leaf nodes:

• No further splitting: Leaves represent terminal decisions
• Region ownership: Each leaf "owns" a hypercube region in feature space
• Purity goal: Ideally, all samples in a leaf share the same label (classification) or similar values (regression)
• Prediction origin: Every prediction the tree makes originates from exactly one leaf

Edges are the connections between nodes that define the tree's structure and the flow of samples. In a decision tree, edges carry both structural and semantic meaning.

Edge Semantics

Each edge represents a split outcome—the result of evaluating a node's split criterion:

• Left edge: Corresponds to the condition "$x_j \leq \theta$" (feature value at or below threshold)
• Right edge: Corresponds to the condition "$x_j > \theta$" (feature value above threshold)

This binary split convention is standard in CART but can vary in other tree implementations. The key insight is that edges encode logical constraints on feature values.

The Path as Conjunction

The sequence of edges from root to any node forms a path, and each path represents a conjunction (AND) of conditions. For a sample to reach a particular leaf, it must satisfy all conditions along the path:

$$\text{Path to leaf } \ell: (x_{j_1} \leq \theta_1) \land (x_{j_2} > \theta_2) \land \cdots \land (x_{j_d} \leq \theta_d)$$

This conjunction defines the axis-aligned hyperrectangle in feature space that the leaf represents.

Branches and Subtrees

A branch is the collection of all nodes and edges reachable from a given internal node. Equivalently, it is the subtree rooted at that node.

Branch properties:

1. Self-contained prediction: Any branch can function as an independent decision tree for the feature subspace it covers
2. Nestedness: The branch of any node is a subset of its parent's branch
3. Pruning unit: When we prune a tree, we replace an entire branch with a leaf

Branch depth and coverage relationship:

As we descend deeper into the tree:

• Branch size (number of descendant nodes) decreases
• Sample coverage (training samples in the branch) decreases
• Prediction specificity increases
• Feature space region becomes smaller and more refined

This trade-off is fundamental to tree behavior: deeper branches make more specific predictions on smaller regions, risking overfitting but capturing complex patterns.

Three fundamental metrics characterize a decision tree's structure: depth, height, and size. These metrics directly relate to model complexity, computational cost, and generalization ability.

Depth of a Node

The depth of a node is the number of edges from the root to that node:

$$\text{depth}(v) = \begin{cases} 0 & \text{if } v = r \text{ (root)} \ \text{depth}(\text{parent}(v)) + 1 & \text{otherwise} \end{cases}$$

Depth interpretation:

• Depth 0: Root node (no conditions applied yet)
• Depth 1: First-level splits (one condition applied)
• Depth $d$: Nodes requiring exactly $d$ conditions to reach

A sample's prediction complexity is proportional to the depth of the leaf it reaches—each edge traversal is one feature comparison.

Height (Maximum Depth)

The height of a tree is the maximum depth among all nodes, equivalently the longest path from root to any leaf:

$$\text{height}(T) = \max_{v \in V} \text{depth}(v)$$

Height bounds the worst-case prediction complexity and is the primary hyperparameter for controlling tree complexity in practice (via max_depth constraints).

Height-complexity relationship:

A tree of height $h$ can have at most $2^h$ leaves, creating up to $2^h$ distinct prediction regions.

Tree Size

Size can refer to different measures:

1. Node count: Total number of nodes $|V| = |V_I| + |V_L|$
2. Leaf count: Number of terminal nodes $|V_L|$ (equivalent to number of distinct predictions)
3. Split count: Number of internal nodes $|V_I| = |V_L| - 1$ (for binary trees)

For a complete binary tree of height $h$:

• Total nodes: $2^{h+1} - 1$
• Internal nodes: $2^h - 1$
• Leaf nodes: $2^h$

For practical decision trees, the structure is rarely complete. Imbalanced data leads to asymmetric trees where some branches terminate early while others grow deep.

Size-generalization principles:

• Smaller trees generalize better (fewer parameters, lower variance)
• Each leaf requires at least some samples to estimate its prediction reliably
• The ratio of samples to leaves bounds the variance of predictions
• For $N$ samples, having more than $N/k$ leaves (for small $k$) typically causes overfitting

The geometric interpretation of decision trees reveals their fundamental mechanism: trees are hierarchical partitioning schemes that recursively divide the feature space into axis-aligned hyperrectangles.

Axis-Aligned Splits

Each split in a decision tree creates a hyperplane perpendicular to one feature axis. For a split on feature $j$ at threshold $\theta$:

• The hyperplane is defined by ${\mathbf{x} : x_j = \theta}$
• This hyperplane is parallel to all other feature axes
• The split bisects the current region into two sub-regions

In 2D, these are vertical and horizontal lines. In 3D, these are planes perpendicular to axes. In $d$ dimensions, these are $(d-1)$-dimensional hyperplanes.

Constraint: Axis-alignment

Decision trees can only split perpendicular to feature axes. They cannot create diagonal decision boundaries directly. This is both a limitation and a source of interpretability:

• Limitation: Capturing diagonal patterns (like $x_1 + x_2 > 5$) requires multiple splits, creating a staircase approximation
• Advantage: Each split is interpretable as a simple feature threshold

From Tree to Partition

Every decision tree induces a partition of the feature space. Formally:

$$\mathcal{X} = \bigsqcup_{\ell \in V_L} R_\ell$$

Where:

• $\bigsqcup$ denotes disjoint union
• $R_\ell$ is the hyperrectangle corresponding to leaf $\ell$
• Each $R_\ell$ is defined by the conjunction of conditions along the path from root to $\ell$

Region definition:

For a leaf $\ell$ reached by path $p_1, p_2, \ldots, p_d$ (where each $p_i$ is a split decision):

$$R_\ell = {\mathbf{x} \in \mathcal{X} : \bigwedge_{i=1}^{d} \text{condition}_i(\mathbf{x})}$$

Each $R_\ell$ is a hyperrectangle (box) because:

• Each condition constrains exactly one feature dimension
• Conditions on the same feature compound to intervals: $a_j \leq x_j \leq b_j$
• The intersection of interval constraints creates an axis-aligned box

Partition Properties

Completeness: Every point in the feature space belongs to exactly one region. There are no gaps or overlaps.

Homogeneity Goal: Each region ideally contains samples of only one class (classification) or similar target values (regression). This is the purity objective that drives splitting.

Prediction Constancy: Within each region, the prediction is constant—the predicted value for the corresponding leaf.

Refinement Hierarchy: Each split refines the partition, breaking one region into two. The partition becomes progressively finer as tree depth increases.

Decision trees are implemented using binary tree data structures, and understanding this implementation reveals important properties about memory layout, traversal efficiency, and prediction complexity.

Array-Based Representation

The most common implementation uses a compact array representation where nodes are stored in level-order:

• Node at index $i$ has:
  • Left child at index $2i + 1$
  • Right child at index $2i + 2$
  • Parent at index $\lfloor(i-1)/2\rfloor$

Per-node storage:

Node {
    feature_index: int     // Which feature to split on (-1 for leaf)
    threshold: float       // Split threshold (unused for leaf)
    value: float[]         // Prediction value(s) for the node
    n_samples: int         // Number of training samples in node
    impurity: float        // Node impurity (Gini, entropy, MSE)
}

This array layout provides:

• O(1) child and parent access
• Cache-efficient traversal
• Simple serialization for model persistence

Memory Complexity

For a tree with $|V|$ nodes and $C$ classes (for classification):

Per-node memory:

• Feature index: 4 bytes
• Threshold: 8 bytes (double precision)
• Class counts/value: $C \times 8$ bytes
• Sample count: 4 bytes
• Impurity: 8 bytes

Total memory: $O(|V| \cdot (C + k))$ where $k$ is constant overhead.

For typical binary classification ($C = 2$), each node requires approximately 48 bytes. A tree with 1000 nodes requires ~48 KB.

Prediction Complexity

Time complexity: $O(\text{height})$ per prediction

• Each prediction traverses one root-to-leaf path
• At each internal node: one comparison, one child pointer follow
• Independent of feature dimensionality

Batch prediction: $O(N \cdot \text{height})$ for $N$ samples

• Excellent for parallelization (each sample independent)

Feature access pattern:

• Non-contiguous feature access (different features at each level)
• May cause cache misses for high-dimensional data

Unlike binary search trees where balance is actively maintained for efficiency, decision trees grow naturally based on data properties, often resulting in highly unbalanced structures. Understanding this distinction is crucial for anticipating tree behavior.

What Causes Imbalance?

Class imbalance: When one class dominates, splits may consistently favor one direction, creating long chains. The minority class samples get repeatedly split to achieve purity, while majority class regions terminate early.

Feature correlations: If splitting features are correlated with specific outcomes, the tree may develop deep paths for one outcome type.

Data distribution: Non-uniform feature distributions create uneven splits. A feature with outliers may generate extremely small regions for those outliers.

Stopping conditions: When minimum sample requirements are met for one branch before another, that branch terminates while others continue growing.

Implications for Model Behavior

Prediction latency variation: In highly unbalanced trees, some samples traverse 3 nodes while others traverse 30. This creates variable prediction times—problematic for real-time systems requiring consistent latency.

Overfitting risk: Deep paths in unbalanced trees often have very few training samples, leading to high-variance predictions. A path with 50 splits but only 5 samples is almost certainly overfit.

Interpretation difficulty: While shallow branches yield simple rules, deep branches become convoluted. A rule with 20 conditions is practically uninterpretable.

Memory inefficiency: Array-based storage for very unbalanced trees wastes space on empty nodes in the implicit structure.

Balance Metrics

Height-to-leaf-count ratio: $$\text{Balance ratio} = \frac{\text{height}}{\log_2(\text{leaf count})}$$

• Ratio = 1: Perfectly balanced full binary tree
• Ratio > 2: Moderately unbalanced
• Ratio > 4: Highly unbalanced (potential issue)

Depth variance: The variance of leaf depths indicates how consistent path lengths are.