Exact Tree SHAP for a Small Tree in C++

July 2026 · 18 min read

The easiest way to implement Tree SHAP correctly is to start with the definition. For a tiny tree with only a few features, enumerate every coalition, evaluate the tree when only that coalition is known, and average each feature's marginal contribution.

Tree Representation

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

struct Node {
    bool leaf = false;
    int feature = -1;
    double threshold = 0.0;
    double value = 0.0;
    int cover = 0;
    Node *left = nullptr, *right = nullptr;
};

Evaluate with Missing Features

If a split feature is known, follow the row's branch. If it is missing, average both branches by training cover. This gives the coalition value for the row.

double eval_coalition(Node* n,
                      const vector<double>& x,
                      const vector<int>& known) {
    if (n->leaf) return n->value;
    if (known[n->feature]) {
        return x[n->feature] < n->threshold
             ? eval_coalition(n->left, x, known)
             : eval_coalition(n->right, x, known);
    }
    double wl = (double)n->left->cover / n->cover;
    double wr = (double)n->right->cover / n->cover;
    return wl * eval_coalition(n->left, x, known)
         + wr * eval_coalition(n->right, x, known);
}

Exact Shapley Loop

vector<double> exact_tree_shap(Node* root,
                               const vector<double>& x,
                               int m) {
    vector<double> phi(m, 0.0);
    int full = 1 << m;

    for (int j = 0; j < m; ++j) {
        for (int mask = 0; mask < full; ++mask) {
            if (mask & (1 << j)) continue;
            int s = __builtin_popcount((unsigned)mask);
            double weight = 1.0 / m / (double)tgamma(m) *
                            tgamma(s + 1) * tgamma(m - s);

            vector<int> known0(m, 0), known1(m, 0);
            for (int k = 0; k < m; ++k) known0[k] = (mask >> k) & 1;
            known1 = known0;
            known1[j] = 1;

            double without = eval_coalition(root, x, known0);
            double with = eval_coalition(root, x, known1);
            phi[j] += weight * (with - without);
        }
    }
    return phi;
}