Neel Mishra
← All Posts
From Scratch · C++ · Machine Learning · Decision Trees

A Decision Tree Classifier in C++

June 2026 · 20 min read

This sub-series builds the decision-tree family from scratch in plain C++, with no machine-learning library, just the standard library. The theory and the animations live in the companion Machine Learning · Decision Trees series; here the goal is working, compilable code. This first part implements a classification tree: Gini impurity, the best-split search, recursive growth, and prediction. The finished program reaches 97% test accuracy on a synthetic dataset and is about a hundred lines.

Representing the Data

A dataset is a feature matrix and a label vector. Rows are samples, columns are features; labels are integer class ids $0, 1, \dots, K-1$.

#include <bits/stdc++.h>
using namespace std;
using Matrix = vector<vector<double>>;   // X[i][f] = feature f of sample i

A node is either an internal node holding a (feature, threshold) test, or a leaf holding a predicted class:

struct Node {
    bool leaf = false;
    int feature = -1;       // which feature this node tests
    double threshold = 0;   // split point:  x[feature] < threshold goes left
    int prediction = -1;    // class label, for leaves
    Node *L = nullptr, *R = nullptr;
};

Gini Impurity

The split criterion is the Gini impurity of a set of labels. With $p_k$ the fraction of points in class $k$,

$$G = \sum_{k} p_k\,(1 - p_k) = 1 - \sum_k p_k^2.$$

It is $0$ for a pure node and largest for an even mix. Computed from class counts:

static double gini(const vector<int>& counts, int n) {
    if (n == 0) return 0;
    double g = 1.0;
    for (int c : counts) { double p = (double)c / n; g -= p * p; }
    return g;
}

The Best Split: a Sorted Sweep

To split a node, every candidate threshold on every feature is scored by the size-weighted Gini of the two children, and the split with the largest impurity drop wins. The efficient way is to sort the points by a feature once and then move the threshold left to right, updating per-class counts in $O(1)$ per step. For each feature $f$:

int D = X[0].size();
double bestGain = 0; int bestFeat = -1; double bestThr = 0;
for (int f = 0; f < D; ++f) {
    vector<int> ord = idx;                                    // indices at this node
    sort(ord.begin(), ord.end(),
         [&](int a, int b){ return X[a][f] < X[b][f]; });    // sort by feature f
    vector<int> left(K, 0), right = cnt;                      // class counts each side
    for (int t = 0; t + 1 < n; ++t) {
        int i = ord[t];
        left[y[i]]++; right[y[i]]--;                          // one point crosses over
        if (X[ord[t]][f] == X[ord[t + 1]][f]) continue;       // no split inside a tie
        int nl = t + 1, nr = n - nl;
        double wg = (double)nl / n * gini(left, nl)
                  + (double)nr / n * gini(right, nr);
        double gain = parentGini - wg;
        if (gain > bestGain) {
            bestGain = gain; bestFeat = f;
            bestThr = (X[ord[t]][f] + X[ord[t + 1]][f]) / 2;
        }
    }
}

The threshold loop above only scores gaps between adjacent distinct observed values. It never loops from the minimum feature value to the maximum feature value. For implementation details such as duplicate values, huge ranges, safe midpoint calculation, missing values, and minimum leaf sizes, see Decision Tree Threshold Search & Edge Cases.

Growing the Tree

The recursion stops when a node is pure, too small, or at the depth limit, in which case it becomes a leaf labelled with the majority class. Otherwise it takes the best split and recurses on each side.

struct DecisionTree {
    int maxDepth, minSamples, K;
    Node* root = nullptr;
    DecisionTree(int md, int ms, int k) : maxDepth(md), minSamples(ms), K(k) {}

    Node* build(vector<int> idx, const Matrix& X, const vector<int>& y, int depth) {
        Node* nd = new Node();
        vector<int> cnt(K, 0);
        for (int i : idx) cnt[y[i]]++;
        int n = idx.size();
        double parentGini = gini(cnt, n);

        // stopping rules -> leaf with the majority class
        if (depth >= maxDepth || n < minSamples || parentGini == 0) {
            nd->leaf = true;
            nd->prediction = max_element(cnt.begin(), cnt.end()) - cnt.begin();
            return nd;
        }

        /* ... best-split sweep from above, filling bestFeat / bestThr ... */

        if (bestFeat < 0) {                 // no useful split found
            nd->leaf = true;
            nd->prediction = max_element(cnt.begin(), cnt.end()) - cnt.begin();
            return nd;
        }
        nd->feature = bestFeat; nd->threshold = bestThr;
        vector<int> li, ri;
        for (int i : idx) (X[i][bestFeat] < bestThr ? li : ri).push_back(i);
        nd->L = build(li, X, y, depth + 1);
        nd->R = build(ri, X, y, depth + 1);
        return nd;
    }

    void fit(const Matrix& X, const vector<int>& y) {
        vector<int> idx(X.size());
        iota(idx.begin(), idx.end(), 0);
        root = build(idx, X, y, 0);
    }
};
Why pass indices, not copies. Each node works on a list of row indices idx rather than copying feature rows. The split just partitions those indices into two smaller lists, so the whole tree never duplicates the data.

Prediction

Prediction walks the tree, following each node's test, until it reaches a leaf:

int predict(const vector<double>& x) const {
    Node* n = root;
    while (!n->leaf) n = (x[n->feature] < n->threshold) ? n->L : n->R;
    return n->prediction;
}

Running It

A quick main makes three Gaussian blobs in 2D (three classes), splits 80/20, trains, and reports accuracy:

int main() {
    mt19937 rng(42);
    normal_distribution<double> nd(0, 1.0);
    vector<array<double,2>> centers = {{0,0}, {4,4}, {0,5}};
    int K = 3, perClass = 120;
    Matrix X; vector<int> y;
    for (int c = 0; c < K; ++c)
        for (int i = 0; i < perClass; ++i) {
            X.push_back({centers[c][0] + nd(rng), centers[c][1] + nd(rng)});
            y.push_back(c);
        }
    // shuffle and split 80 / 20
    vector<int> p(X.size()); iota(p.begin(), p.end(), 0);
    shuffle(p.begin(), p.end(), rng);
    int ntr = 0.8 * X.size();
    Matrix Xtr, Xte; vector<int> ytr, yte;
    for (int k = 0; k < (int)p.size(); ++k) {
        if (k < ntr) { Xtr.push_back(X[p[k]]); ytr.push_back(y[p[k]]); }
        else        { Xte.push_back(X[p[k]]); yte.push_back(y[p[k]]); }
    }

    DecisionTree tree(/*maxDepth*/6, /*minSamples*/2, K);
    tree.fit(Xtr, ytr);

    auto acc = [&](const Matrix& Xs, const vector<int>& ys) {
        int ok = 0;
        for (size_t i = 0; i < Xs.size(); ++i) ok += (tree.predict(Xs[i]) == ys[i]);
        return 100.0 * ok / Xs.size();
    };
    printf("train acc = %.1f%%   test acc = %.1f%%\n", acc(Xtr, ytr), acc(Xte, yte));
}

Compiled with g++ -O2 -std=c++17, it prints:

train acc = 100.0% test acc = 97.2%

The tree fits the training set perfectly and generalizes to $97.2\%$ on held-out points. Pushing the depth higher and the data noisier would drive training accuracy to $100\%$ while test accuracy slips, which is the overfitting the theory predicts and the motivation for the next three parts.

Complete Program: Tie Everything Together

The snippets above are the moving parts. Here is the complete copy-paste version: data generation, train/test split, tree training, prediction, and accuracy reporting in one file.

#include <bits/stdc++.h>
using namespace std;

using Matrix = vector<vector<double>>;

struct Node {
    bool leaf = false;
    int feature = -1;
    double threshold = 0.0;
    int prediction = -1;
    Node *L = nullptr, *R = nullptr;
};

static double gini(const vector<int>& counts, int n) {
    if (n == 0) return 0.0;
    double g = 1.0;
    for (int c : counts) {
        double p = (double)c / n;
        g -= p * p;
    }
    return g;
}

struct DecisionTree {
    int maxDepth, minSamples, K;
    Node* root = nullptr;

    DecisionTree(int md, int ms, int k) : maxDepth(md), minSamples(ms), K(k) {}
    ~DecisionTree() { clear(root); }

    void clear(Node* n) {
        if (!n) return;
        clear(n->L);
        clear(n->R);
        delete n;
    }

    int majority_class(const vector<int>& counts) const {
        return max_element(counts.begin(), counts.end()) - counts.begin();
    }

    Node* make_leaf(const vector<int>& counts) const {
        Node* nd = new Node();
        nd->leaf = true;
        nd->prediction = majority_class(counts);
        return nd;
    }

    Node* build(const vector<int>& idx,
                const Matrix& X,
                const vector<int>& y,
                int depth) {
        vector<int> cnt(K, 0);
        for (int i : idx) cnt[y[i]]++;

        int n = (int)idx.size();
        double parentGini = gini(cnt, n);
        if (depth >= maxDepth || n < 2 * minSamples || parentGini == 0.0) {
            return make_leaf(cnt);
        }

        int D = (int)X[0].size();
        double bestGain = 1e-12;
        int bestFeat = -1;
        double bestThr = 0.0;

        for (int f = 0; f < D; ++f) {
            vector<int> ord = idx;
            sort(ord.begin(), ord.end(),
                 [&](int a, int b) { return X[a][f] < X[b][f]; });

            vector<int> left(K, 0), right = cnt;
            for (int t = 0; t + 1 < n; ++t) {
                int row = ord[t];
                left[y[row]]++;
                right[y[row]]--;

                double cur = X[ord[t]][f];
                double nxt = X[ord[t + 1]][f];
                if (cur == nxt) continue;        // no threshold inside duplicate values

                int nl = t + 1, nr = n - nl;
                if (nl < minSamples || nr < minSamples) continue;

                double weighted =
                    (double)nl / n * gini(left, nl) +
                    (double)nr / n * gini(right, nr);
                double gain = parentGini - weighted;

                if (gain > bestGain) {
                    bestGain = gain;
                    bestFeat = f;
                    bestThr = cur + (nxt - cur) / 2.0; // safer midpoint
                }
            }
        }

        if (bestFeat < 0) return make_leaf(cnt);

        vector<int> leftIdx, rightIdx;
        for (int i : idx) {
            if (X[i][bestFeat] < bestThr) leftIdx.push_back(i);
            else rightIdx.push_back(i);
        }

        Node* nd = new Node();
        nd->feature = bestFeat;
        nd->threshold = bestThr;
        nd->L = build(leftIdx, X, y, depth + 1);
        nd->R = build(rightIdx, X, y, depth + 1);
        return nd;
    }

    void fit(const Matrix& X, const vector<int>& y) {
        clear(root);
        vector<int> idx(X.size());
        iota(idx.begin(), idx.end(), 0);
        root = build(idx, X, y, 0);
    }

    int predict(const vector<double>& x) const {
        Node* n = root;
        while (!n->leaf) {
            n = (x[n->feature] < n->threshold) ? n->L : n->R;
        }
        return n->prediction;
    }
};

double accuracy(const DecisionTree& tree, const Matrix& X, const vector<int>& y) {
    int ok = 0;
    for (size_t i = 0; i < X.size(); ++i) {
        ok += (tree.predict(X[i]) == y[i]);
    }
    return 100.0 * ok / X.size();
}

int main() {
    mt19937 rng(42);
    normal_distribution<double> noise(0.0, 1.0);
    vector<array<double, 2>> centers = {{{0, 0}, {4, 4}, {0, 5}}};

    int K = 3, perClass = 120;
    Matrix X;
    vector<int> y;

    for (int c = 0; c < K; ++c) {
        for (int i = 0; i < perClass; ++i) {
            X.push_back({centers[c][0] + noise(rng), centers[c][1] + noise(rng)});
            y.push_back(c);
        }
    }

    vector<int> order(X.size());
    iota(order.begin(), order.end(), 0);
    shuffle(order.begin(), order.end(), rng);

    int nTrain = (int)(0.8 * X.size());
    Matrix Xtrain, Xtest;
    vector<int> ytrain, ytest;

    for (int k = 0; k < (int)order.size(); ++k) {
        int i = order[k];
        if (k < nTrain) {
            Xtrain.push_back(X[i]);
            ytrain.push_back(y[i]);
        } else {
            Xtest.push_back(X[i]);
            ytest.push_back(y[i]);
        }
    }

    DecisionTree tree(/*maxDepth*/6, /*minSamples*/2, K);
    tree.fit(Xtrain, ytrain);

    cout << fixed << setprecision(1);
    cout << "train acc = " << accuracy(tree, Xtrain, ytrain) << "%\n";
    cout << "test acc  = " << accuracy(tree, Xtest, ytest) << "%\n";
    return 0;
}

Compile and run it with:

g++ -O2 -std=c++17 decision_tree.cpp && ./a.out

With the seed above, the complete guarded version prints:

train acc = 99.3% test acc = 97.2%

What's Next

The same skeleton, with the impurity swapped for squared error, gives a regression tree (Regression Tree). Averaging many such trees over bootstrap samples gives a random forest (Random Forest), and adding trees in sequence gives gradient boosting and AdaBoost (Boosting).