Module 6 · Trees & Ensembles from Scratch ⏱ 19 min

Build a Decision Tree

By the end of this lesson you will be able to:
  • Find the best split for a node by maximising information gain across every feature and threshold
  • Grow a tree recursively, stopping at pure leaves or a depth limit, predicting the majority class
  • Classify held-out examples the tree never saw during training

You can now read a tree, and you can score a single split. The one piece still missing is the loop that turns those two skills into a full grown tree. That loop is surprisingly short: at each node, either stop and predict, or find the best split, divide the data, and repeat on each half. Recursive splitting is the whole game, and once you see it written down it feels obvious — every subtree is just a smaller tree built by the exact same function. This lesson wires the split criterion from the last lesson into a recursive builder, caps how deep it may grow, and then does the thing that makes it machine learning rather than memorisation: it classifies examples it has never seen.

The build loop, in words

A node holds a pile of labelled examples. The builder asks one question: should I stop here? You stop for two reasons. First, the node is pure — every example shares one label, so there is nothing left to split, and the node becomes a leaf predicting that label. Second, you have hit a depth limit — a maximum number of questions you allow the tree to ask along any path — so you stop and predict the majority class even if the node is still a little mixed. If neither reason fires, you find the best split, partition the examples into a left and right half, and build a subtree on each half. That recursion bottoms out at pure leaves, and the depth limit guarantees it bottoms out even on messy data.

The best split for a clean dataset. Six points split perfectly at feature 0, threshold 4.5. Run it.
import math

def entropy(counts):
    total = sum(counts)
    h = 0.0
    for c in counts:
        if c == 0:
            continue
        p = c / total
        h -= p * math.log2(p)
    return h

def entropy_of_labels(labels):
    counts = {}
    for lab in labels:
        counts[lab] = counts.get(lab, 0) + 1
    return entropy(list(counts.values()))

def best_split(rows, labels):
    n = len(labels)
    parent = entropy_of_labels(labels)
    best_gain = -1.0
    best = None
    for feat in range(len(rows[0])):
        values = sorted(set(r[feat] for r in rows))
        for i in range(len(values) - 1):
            thr = (values[i] + values[i + 1]) / 2
            left = [labels[j] for j in range(n) if rows[j][feat] <= thr]
            right = [labels[j] for j in range(n) if rows[j][feat] > thr]
            if not left or not right:
                continue
            child = (len(left) / n) * entropy_of_labels(left) + (len(right) / n) * entropy_of_labels(right)
            gain = parent - child
            if gain > best_gain:
                best_gain = gain
                best = (feat, thr)
    return best

rows = [[2, 3], [3, 4], [1, 2], [6, 7], [7, 8], [8, 9]]
labels = ['a', 'a', 'a', 'b', 'b', 'b']
print(best_split(rows, labels))
flowchart TD
  N["a node with its labels"] --> Q["pure, or depth limit reached?"]
  Q -->|"yes"| L["make a leaf: majority class"]
  Q -->|"no"| S["find the best split"]
  S --> R["recurse on left and right halves"]
  R --> N
  style L fill:#166534,color:#fff
  style S fill:#3776ab,color:#fff
The build loop: at each node, stop (pure or depth limit) and make a leaf, or split and recurse on both halves. Every subtree is built by the same function.

When to stop, and what a leaf says

The stop conditions are where a tree's personality is set. Stop only at pure nodes and the tree will keep splitting until every leaf holds a single training example — perfectly accurate on the training data, and brittle on everything else. Stop earlier, at a depth limit, and the tree is forced to predict the majority class of an impure leaf, which trades a little training accuracy for predictions that generalise. The leaf's prediction is always the majority class of the examples that landed there: count the labels, return the most common one. Ties are broken by whichever class was counted first, which keeps the tree deterministic given the same data — an unglamorous detail that matters when you debug why two runs differ.

Grow the full tree. The root splits at feature 0, threshold 4.5; both children are pure leaves. Run it and read the structure.
import math

def entropy(counts):
    total = sum(counts)
    h = 0.0
    for c in counts:
        if c == 0:
            continue
        p = c / total
        h -= p * math.log2(p)
    return h

def entropy_of_labels(labels):
    counts = {}
    for lab in labels:
        counts[lab] = counts.get(lab, 0) + 1
    return entropy(list(counts.values()))

def best_split(rows, labels):
    n = len(labels)
    parent = entropy_of_labels(labels)
    best_gain = -1.0
    best = None
    for feat in range(len(rows[0])):
        values = sorted(set(r[feat] for r in rows))
        for i in range(len(values) - 1):
            thr = (values[i] + values[i + 1]) / 2
            left = [labels[j] for j in range(n) if rows[j][feat] <= thr]
            right = [labels[j] for j in range(n) if rows[j][feat] > thr]
            if not left or not right:
                continue
            child = (len(left) / n) * entropy_of_labels(left) + (len(right) / n) * entropy_of_labels(right)
            gain = parent - child
            if gain > best_gain:
                best_gain = gain
                best = (feat, thr)
    return best

def build_tree(rows, labels, depth=0, max_depth=3):
    counts = {}
    for lab in labels:
        counts[lab] = counts.get(lab, 0) + 1
    majority = max(counts, key=lambda k: counts[k])
    if len(set(labels)) == 1 or depth >= max_depth:
        return {'leaf': majority}
    feat, thr = best_split(rows, labels)
    left_idx = [j for j in range(len(rows)) if rows[j][feat] <= thr]
    right_idx = [j for j in range(len(rows)) if rows[j][feat] > thr]
    left = build_tree([rows[j] for j in left_idx], [labels[j] for j in left_idx], depth + 1, max_depth)
    right = build_tree([rows[j] for j in right_idx], [labels[j] for j in right_idx], depth + 1, max_depth)
    return {'feature': feat, 'threshold': thr, 'left': left, 'right': right}

rows = [[2, 3], [3, 4], [1, 2], [6, 7], [7, 8], [8, 9]]
labels = ['a', 'a', 'a', 'b', 'b', 'b']
print(build_tree(rows, labels, max_depth=3))

Why we cap the depth

Run that builder with no depth limit and a clean dataset and you get a tidy one-question tree. Run it on noisy, overlapping data and the same builder will keep splitting until every leaf is a single example — a tree so deep it has effectively memorised the training set, point by point. That is the central failure mode of decision trees, and it is the entire subject of the next lesson. The max_depth argument is the simplest defence: it draws a line and says beyond this many questions, stop and vote. A smaller depth forces broader, more robust leaves; a larger depth fits the training data more closely but risks fitting its noise. Choosing that number is a real decision, and later you will set it by measuring accuracy on data the tree did not train on.

flowchart LR
  D0["depth 0 root"] --> D1L["depth 1"]
  D0 --> D1R["depth 1"]
  D1R --> D2L["depth 2"]
  D1R --> D2R["depth 2"]
  D2L --> STOP["max depth: stop as a leaf"]
  style STOP fill:#b45309,color:#fff
A depth limit stops recursion early: once a path reaches max depth, that node becomes a leaf even if it is still mixed.
Train on six examples, then classify two HELD-OUT points the tree never saw. Press Run.
import math

def entropy(counts):
    total = sum(counts)
    h = 0.0
    for c in counts:
        if c == 0:
            continue
        p = c / total
        h -= p * math.log2(p)
    return h

def entropy_of_labels(labels):
    counts = {}
    for lab in labels:
        counts[lab] = counts.get(lab, 0) + 1
    return entropy(list(counts.values()))

def best_split(rows, labels):
    n = len(labels)
    parent = entropy_of_labels(labels)
    best_gain = -1.0
    best = None
    for feat in range(len(rows[0])):
        values = sorted(set(r[feat] for r in rows))
        for i in range(len(values) - 1):
            thr = (values[i] + values[i + 1]) / 2
            left = [labels[j] for j in range(n) if rows[j][feat] <= thr]
            right = [labels[j] for j in range(n) if rows[j][feat] > thr]
            if not left or not right:
                continue
            child = (len(left) / n) * entropy_of_labels(left) + (len(right) / n) * entropy_of_labels(right)
            gain = parent - child
            if gain > best_gain:
                best_gain = gain
                best = (feat, thr)
    return best

def build_tree(rows, labels, depth=0, max_depth=3):
    counts = {}
    for lab in labels:
        counts[lab] = counts.get(lab, 0) + 1
    majority = max(counts, key=lambda k: counts[k])
    if len(set(labels)) == 1 or depth >= max_depth:
        return {'leaf': majority}
    feat, thr = best_split(rows, labels)
    left_idx = [j for j in range(len(rows)) if rows[j][feat] <= thr]
    right_idx = [j for j in range(len(rows)) if rows[j][feat] > thr]
    left = build_tree([rows[j] for j in left_idx], [labels[j] for j in left_idx], depth + 1, max_depth)
    right = build_tree([rows[j] for j in right_idx], [labels[j] for j in right_idx], depth + 1, max_depth)
    return {'feature': feat, 'threshold': thr, 'left': left, 'right': right}

def classify(tree, row):
    if 'leaf' in tree:
        return tree['leaf']
    if row[tree['feature']] <= tree['threshold']:
        return classify(tree['left'], row)
    return classify(tree['right'], row)

rows = [[2, 3], [3, 4], [1, 2], [6, 7], [7, 8], [8, 9]]
labels = ['a', 'a', 'a', 'b', 'b', 'b']
tree = build_tree(rows, labels, max_depth=3)
print(classify(tree, [2, 2]))
print(classify(tree, [9, 9]))
flowchart LR
  TR["training examples"] --> B["build the tree"]
  B --> T["the learned tree"]
  H["held-out test example"] --> C["classify"]
  T --> C
  C --> P["predicted label"]
  style B fill:#3776ab,color:#fff
  style P fill:#166534,color:#fff
The machine-learning loop: build the tree from training examples, then classify held-out examples through the same tree.

The point: predict the unseen

Those last two classify calls are the whole purpose of the exercise. The points [2, 2] and [9, 9] were never in the training set, yet the tree routes them correctly — small first feature to class a, large to class b — because it learned the rule the training data illustrated, not the training data itself. That gap, between fitting what you saw and predicting what you did not, is the definition of generalisation, and it is what separates a model from a lookup table. A tree small enough to generalise is useful; a tree deep enough to memorise is not. Measuring that difference, honestly, on data held back from training is the subject of the evaluation module — but the structure that makes it possible is the one you just built.

Exercise

What does this print? The root tests feature 0 against 4.5; the right child tests feature 1 against 8.5.

def classify(tree, row):
    if 'leaf' in tree:
        return tree['leaf']
    if row[tree['feature']] <= tree['threshold']:
        return classify(tree['left'], row)
    return classify(tree['right'], row)

tree = {
    'feature': 0, 'threshold': 4.5,
    'left': {'leaf': 'a'},
    'right': {
        'feature': 1, 'threshold': 8.5,
        'left': {'leaf': 'b'},
        'right': {'leaf': 'c'}
    }
}

print(classify(tree, [9, 7]))
Exercise

Write best_split(rows, labels) that returns the (feature, threshold) maximising information gain, as a tuple. rows is a list of equal-length feature lists; labels is the parallel list of classes. Try every feature and the midpoint between each pair of sorted unique values; skip a threshold that puts everything on one side. The entropy helpers are provided.

import math

def entropy(counts):
    total = sum(counts)
    h = 0.0
    for c in counts:
        if c == 0:
            continue
        p = c / total
        h -= p * math.log2(p)
    return h

def entropy_of_labels(labels):
    counts = {}
    for lab in labels:
        counts[lab] = counts.get(lab, 0) + 1
    return entropy(list(counts.values()))

def best_split(rows, labels):
    n = len(labels)
    parent = entropy_of_labels(labels)
    best_gain = -1.0
    best = None
    # for each feature, for each midpoint threshold, compute gain and keep the max
    return best
Exercise

A leaf must predict the MAJORITY class of the labels that reached it, but this helper returns the LEAST common class instead. Fix it so an impure leaf predicts the class that appears most often.

def majority_label(labels):
    counts = {}
    for lab in labels:
        counts[lab] = counts.get(lab, 0) + 1
    return min(counts, key=lambda k: counts[k])
Exercise

Write build_tree(rows, labels, depth=0, max_depth=3) that returns a nested dict. Stop and return {'leaf': majority} when the labels are all one class OR depth >= max_depth; otherwise split with best_split, partition the rows by the threshold, and recurse on each side. An internal node is {'feature': feat, 'threshold': thr, 'left': ..., 'right': ...}. The split and entropy helpers are provided.

import math

def entropy(counts):
    total = sum(counts)
    h = 0.0
    for c in counts:
        if c == 0:
            continue
        p = c / total
        h -= p * math.log2(p)
    return h

def entropy_of_labels(labels):
    counts = {}
    for lab in labels:
        counts[lab] = counts.get(lab, 0) + 1
    return entropy(list(counts.values()))

def best_split(rows, labels):
    n = len(labels)
    parent = entropy_of_labels(labels)
    best_gain = -1.0
    best = None
    for feat in range(len(rows[0])):
        values = sorted(set(r[feat] for r in rows))
        for i in range(len(values) - 1):
            thr = (values[i] + values[i + 1]) / 2
            left = [labels[j] for j in range(n) if rows[j][feat] <= thr]
            right = [labels[j] for j in range(n) if rows[j][feat] > thr]
            if not left or not right:
                continue
            child = (len(left) / n) * entropy_of_labels(left) + (len(right) / n) * entropy_of_labels(right)
            gain = parent - child
            if gain > best_gain:
                best_gain = gain
                best = (feat, thr)
    return best

def build_tree(rows, labels, depth=0, max_depth=3):
    counts = {}
    for lab in labels:
        counts[lab] = counts.get(lab, 0) + 1
    majority = max(counts, key=lambda k: counts[k])
    # return a leaf if pure or depth-limited; otherwise split and recurse
    pass
Exercise

Write tree_depth(tree) returning how many questions deep the tree goes. A leaf has depth 0; an internal node has depth 1 + max(depth(left), depth(right)). This is the same recursive walk as classify, but it measures the structure instead of routing an example.

def tree_depth(tree):
    # a leaf is depth 0; otherwise 1 + the deeper of the two subtrees
    pass

Recap

  • best_split tries every feature and every midpoint threshold, scores each by information gain, and returns the highest-gain (feature, threshold) pair — the question the tree asks at that node.
  • build_tree recurses: return a {'leaf': majority} when the node is pure or the depth limit is hit; otherwise split, partition, and recurse on each half.
  • A leaf predicts the majority class of the labels that reached it; ties break by first-seen order, keeping the build deterministic.
  • max_depth is the simplest guard against memorising — earlier, broader leaves at the cost of a slightly looser fit.
  • Trees are greedy (each split is locally optimal and irreversible) and axis-aligned (each cut is on one feature).

You have built a working decision tree from entropy up. Next: turn it loose without a depth limit, watch it overfit, then tame it.

Checkpoint quiz

Why does build_tree stop and make a leaf when depth >= max_depth, even if the node is still mixed?

best_split returns (0, 4.5) for a node. What does the builder do with that?

Go deeper — technical resources