Node (decision tree)

See also: Machine learning terms

What is a node in a decision tree?

A node is the basic building block of a decision tree: it is a single point in the tree that is either a condition (an internal node that tests a feature and branches) or a leaf (a terminal node that holds a prediction). Google's Decision Forests glossary states the definition in five words: a node is "any condition or leaf" ^[1]. Every non-leaf node contains a condition and every leaf node contains a prediction, so the whole tree is just a hierarchy of those two kinds of nodes wired together by branches, and inference works by routing one example from the root at the top down to exactly one leaf at the bottom ^[1][2].

In machine learning, nodes are the structural unit of the tree. They are what the learning algorithm creates while growing the tree, what pruning trims away, and what the inference path walks. Everything a decision tree "knows" about a problem is stored across its nodes, either as conditions (for splits) or as values (for predictions). Google's glossary draws the line precisely: "Unlike a condition, a leaf doesn't perform a test. Rather, a leaf is a possible prediction" ^[1].

Decision tree nodes are usually grouped into three roles:

Scroll sideways for more →

The distinction between an internal node and the root is structural rather than semantic: the root is just the unique internal node with no parent ^[2]. Some references therefore treat "internal node" as a superset that includes the root.

What are the types of nodes?

Root node

The root node is the topmost node and the entry point for inference. Google's Decision Forests course notes that "decision trees are usually represented with the root (the first node) at the top," the reverse of a botanical tree ^[2]. It has no incoming edge and represents the first split applied to the full training set. From the root, branches lead either to other internal nodes that apply more refined conditions, or directly to leaves if the tree is shallow. In a stump (a tree of depth one), the root is the only internal node, and its two children are both leaves.

Internal node

An internal node is any non-leaf node. It holds a condition, sometimes called a split or a test, that compares one or more features of an input to a threshold or a set membership rule. Google's glossary defines a condition as "any node that performs a test" ^[1]. Each internal node has one incoming edge from its parent and two or more outgoing edges to its children. Most popular implementations, including CART, use strict binary trees, so internal nodes have exactly two children, one for the True branch and one for the False branch. Google notes that decision forests typically use binary trees because non-binary conditions raise the risk of overfitting, and any non-binary condition can be emulated with several binary ones ^[3].

Conditions inside internal nodes come in two broad flavors. Google's course frames the split this way: "An axis-aligned condition involves only a single feature. An oblique condition involves multiple features" ^[3].

Scroll sideways for more →

Conditions are also classified by how many branches leave the node. "Conditions with two possible outcomes (for example, true or false) are called binary conditions," while "non-binary conditions have more than two possible outcomes" ^[3]. Because axis-aligned splits only care about the order of feature values, decision trees do not require feature scaling or normalization. This is one practical reason they remain popular in tabular settings: you can mix integers, floats, and one-hot indicators without preprocessing.

Leaf node

A leaf node has no outgoing edges. It is where the inference path stops and a prediction is returned. The form of that prediction depends on the task:

• Classification: the leaf stores either a single class label (the majority class among training samples that reached it) or a probability vector over classes.
• Regression: the leaf stores a numeric value, typically the mean of the target variable over training samples that reached it.
• Survival, quantile, or ranking trees: the leaf stores a small model or summary statistic appropriate to the task, such as a Kaplan-Meier curve or a quantile estimate.

In the scikit-learn implementation, leaves and internal nodes share the same array layout. A node is identified as a leaf when its left child id equals its right child id, both set to -1, indicating that there is no further split ^[8]. The value array at that node holds the prediction.

How are nodes organized and how does inference route through them?

Inference is the process of pushing one example through the nodes until it reaches a prediction. Google's course describes the mechanism in one sentence: "Inference of a decision tree model is computed by routing an example from the root (at the top) to one of the leaf nodes (at the bottom) according to the conditions" ^[2]. The glossary names the chain of nodes that an example touches the inference path: "during inference, the route a particular example takes from the root to other conditions, terminating with a leaf" ^[1]. Starting at the root, the model evaluates the condition stored at each internal node, follows the branch that matches the example, and stops as soon as it lands on a leaf, whose stored value is the output.

How does the tree decide what to put in each node?

Decision trees are built greedily, from the root down, in a procedure often called top-down induction of decision trees (TDIDT) ^[5]. At each node, the learner scans candidate splits and picks the one that improves a chosen impurity or loss criterion the most. The classic criteria are:

Scroll sideways for more →

For a numeric feature, the standard trick for finding the best threshold is to sort the feature values and test thresholds halfway between consecutive sorted values ^[4]. This makes the per-feature split search run in O(n log n) time. Across m features and n samples, the full training of a single decision tree typically runs in O(m n log^2 n) time ^[5].

The tree keeps growing recursively. At each child node the learner repeats the same search on the subset of samples that reached that child. Growth stops when one of the stopping conditions fires, such as a maximum depth, a minimum number of samples per node, a minimum impurity decrease, or perfect purity. When growth stops at a node, that node becomes a leaf and a prediction is computed and stored ^[4].

What learning algorithms build the nodes?

Several well known algorithms differ mainly in how they choose conditions, how they handle different data types, and whether they prune.

Scroll sideways for more →

These algorithms produce different trees on the same data, but they all manipulate the same three node roles. The choice of algorithm mostly changes what a condition can look like and how aggressively the tree is grown.

How does pruning remove nodes to improve generalization?

A fully grown tree can keep splitting until each leaf holds a single training sample. The result fits the training set perfectly but typically suffers from overfitting ^[7]. Pruning is the process of removing nodes or whole subtrees to produce a smaller, more general model. There are two timing strategies.

Pre-pruning (early stopping)

Pre-pruning halts growth during construction. Common stop rules include:

• maximum tree depth,
• minimum number of samples required to split a node,
• minimum number of samples in a leaf,
• minimum impurity decrease threshold,
• maximum number of leaves.

Pre-pruning is computationally cheap because the tree never grows beyond its final size. The main drawback is the horizon effect: a split that looks weak on its own may unlock useful splits one or two levels deeper, and pre-pruning will never discover them because it stops too early ^[7].

Post-pruning

Post-pruning lets the tree grow fully and then trims it back. Several specific procedures are in use:

Scroll sideways for more →

In scikit-learn, cost-complexity pruning is exposed through the ccp_alpha parameter on DecisionTreeClassifier and DecisionTreeRegressor: larger values prune more aggressively, and the cost_complexity_pruning_path method returns the sequence of effective alphas ^[9].

What attributes does a node store in practice?

Most decision tree libraries store nodes as parallel arrays so that traversal is cache friendly. The scikit-learn Tree object is a good reference. For every node id i, it tracks ^[8]:

Scroll sideways for more →

A node is a leaf when its left and right children are both -1 ^[8]. Walking the tree from the root and applying the condition at each internal node lets you reconstruct the path that an example takes and explain the prediction.

Example: routing one sample through the nodes

Suppose a small CART model predicts whether a loan will default using two features, income and credit_score. The tree might look like this:

Root: income < 30000?
  True  -> Internal: credit_score < 600?
              True  -> Leaf: predict "default"
              False -> Leaf: predict "no default"
  False -> Internal: credit_score < 720?
              True  -> Leaf: predict "no default"
              False -> Leaf: predict "no default"

For an applicant with income = 45000 and credit_score = 690, inference visits three nodes: the root (False branch), the internal node testing credit score (True branch), and a leaf. The leaf's value, "no default", is the prediction. Three nodes were touched, two of them internal and one of them a leaf.

This is the entire computational story of a decision tree: walk from the root, apply the condition stored at each internal node, take the matching branch, and stop when you hit a leaf ^[2].

Why does the node abstraction matter?

The node level is also where most engineering knobs live. Tuning a decision tree mostly means tuning what conditions are allowed at internal nodes and when leaves are created:

• max_depth, min_samples_split, min_samples_leaf, and min_impurity_decrease are pre-pruning controls on internal nodes.
• max_leaf_nodes limits how many leaves the tree may end up with.
• criterion chooses how an internal node scores candidate splits.
• ccp_alpha controls post-pruning.
• max_features restricts which features an internal node may consider for its split, which is central to random forests.

In ensemble methods such as random forests, gradient boosted trees, and extra trees, the same node concept carries over. Each tree in the ensemble is built from the same internal-node-and-leaf machinery, and the ensemble's prediction is just an aggregation over the leaves reached in every tree.

Explain like I'm 5 (ELI5)

Think of playing 20 Questions to guess an animal. Each question you ask is a node. The first question is the root node. The follow-up questions are internal nodes. When you finally say, "It's a giraffe," that final answer is a leaf node. A decision tree does the same thing with data: it keeps asking yes-or-no questions about a row of numbers until it reaches a leaf, and the leaf gives the answer.

References

1. Google for Developers, Machine Learning Glossary: Decision Forests, entries for "node (decision tree)," "leaf," "condition," and "inference path." https://developers.google.com/machine-learning/glossary/df ↩
2. Google for Developers, Decision Forests course, "Decision trees" page. https://developers.google.com/machine-learning/decision-forests/decision-trees ↩
3. Google for Developers, Decision Forests course, "Types of conditions" page. https://developers.google.com/machine-learning/decision-forests/conditions ↩
4. Google for Developers, Decision Forests course, "Growing decision trees" page. https://developers.google.com/machine-learning/decision-forests/growing ↩
5. Wikipedia, "Decision tree learning." https://en.wikipedia.org/wiki/Decision_tree_learning ↩
6. Wikipedia, "Decision tree." https://en.wikipedia.org/wiki/Decision_tree
7. Wikipedia, "Decision tree pruning." https://en.wikipedia.org/wiki/Decision_tree_pruning ↩
8. scikit-learn documentation, "Understanding the decision tree structure." https://scikit-learn.org/stable/auto_examples/tree/plot_unveil_tree_structure.html ↩
9. scikit-learn documentation, "Post pruning decision trees with cost complexity pruning." https://scikit-learn.org/stable/auto_examples/tree/plot_cost_complexity_pruning.html ↩
10. Breiman, L., Friedman, J., Olshen, R., and Stone, C. (1984). *Classification and Regression Trees*. Wadsworth.
11. Quinlan, J. R. (1986). "Induction of Decision Trees." *Machine Learning*, 1(1), 81 to 106.
12. Quinlan, J. R. (1993). *C4.5: Programs for Machine Learning*. Morgan Kaufmann.