Introduction

A decision tree is the friendliest model in all of machine learning. It is just a flowchart of yes/no questions: Is the outlook sunny? Is the humidity high? You follow the branches until you reach a leaf, and the leaf tells you the answer — play or don't play. No matrices, no calculus, nothing you can't explain to a child.

That readability is exactly why people love trees. A bank can show a rejected applicant the precise chain of questions that led to "no." A doctor can audit every split. Unlike a neural network, a small tree is a thing you can read.

So here is the natural wish: given a table of examples, find the smallest, simplest tree that classifies them all correctly. Fewer questions means a clearer rule and less overfitting. How hard could building the best tree possibly be?

Grow a Tree

Here is a tiny dataset: each row is a day, and we want to predict whether to play tennis. Click a feature to split the current group on it. A good split sends the yes rows one way and the no rows the other, so each branch becomes purer.

<p class="hint">Each row is a day; we want to predict <b>Play</b> (✓) or not (✗). Click a feature button to <b>split</b> the highlighted group on it. Pure groups (all ✓ or all ✗) become leaves. Reading a tree is instant — finding the <i>smallest</i> tree is NP-hard.</p>
<table id="data" class="data"></table>
<div id="tree" class="tree"></div>
<div class="status" id="status">Pick a feature to split the root group.</div>
<div class="feats" id="feats"></div>
<div class="btns">
  <button id="greedy" type="button">Greedy step</button>
  <button id="optimal" type="button">Find smallest tree</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.data { border-collapse: collapse; font-size: .8rem; margin: .3rem 0 .7rem; }
.data th, .data td { border: 1px solid #cdd9e3; padding: 3px 7px; text-align: center; }
.data th { background: #e8eef3; color: #1d3557; }
.data td.play-y { color: #0a7d33; font-weight: 700; }
.data td.play-n { color: #c92f3c; font-weight: 700; }
.tree { margin: .4rem 0; font: 600 13px ui-monospace, monospace; white-space: pre; line-height: 1.5; min-height: 2em; }
.node-pure-y { color: #0a7d33; }
.node-pure-n { color: #c92f3c; }
.node-split { color: #1d3557; }
.node-open { color: #b5651d; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.feats { display: flex; gap: .4rem; flex-wrap: wrap; margin: .4rem 0; }
.feats button { font: 600 13px system-ui; padding: .3rem .7rem; border: 1px solid #1d3557;
                background: #fff; color: #1d3557; border-radius: 8px; cursor: pointer; }
.feats button:hover { background: #e8eef3; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .5rem; }
.btns button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
               background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.btns button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── A tiny "play tennis" dataset. Features are binary (0/1); label is play (0/1).
// Goal: build a tree of feature-splits whose leaves are all pure (one label).
// Greedy (ID3/CART) picks the split with highest INFORMATION GAIN at each node.
// The SMALLEST consistent tree is NP-hard to find (Hyafil & Rivest, 1976), so
// here we brute-force it over all feature orderings to contrast the two.
const FEATURES = ['Sunny', 'Windy', 'Humid'];
// rows: [Sunny, Windy, Humid, play].  An XOR-ish pattern on Sunny/Windy: the
// greedy info-gain heuristic splits Humid first (highest single-step gain) and
// ends with 5 leaves, but the optimal Sunny->Windy ordering needs only 4 — a tiny live proof that "best question now" != "smallest tree overall".
const ROWS = [
  [0, 0, 0, 0], // overcast, calm,  dry   -> no
  [1, 0, 0, 1], // sunny,    calm,  dry   -> yes
  [0, 1, 0, 1], // overcast, windy, dry   -> yes
  [1, 1, 0, 0], // sunny,    windy, dry   -> no
  [0, 0, 1, 0], // overcast, calm,  humid -> no
];

// ── information theory helpers ────────────────────────────────────────────
function entropy(idx) {
  const n = idx.length; if (!n) return 0;
  const p = idx.filter(i => ROWS[i][3] === 1).length / n;
  if (p === 0 || p === 1) return 0;
  const q = 1 - p;
  return -(p * Math.log2(p) + q * Math.log2(q));
}
function splitOn(idx, f) {
  return [idx.filter(i => ROWS[i][f] === 0), idx.filter(i => ROWS[i][f] === 1)];
}
function infoGain(idx, f) {
  const [a, b] = splitOn(idx, f), n = idx.length;
  return entropy(idx) - (a.length / n) * entropy(a) - (b.length / n) * entropy(b);
}
const pure = idx => idx.length === 0 || idx.every(i => ROWS[i][3] === ROWS[idx[0]][3]);

// ── count leaves of the smallest consistent tree by trying feature orderings ─
function buildOrdered(idx, order) {
  if (pure(idx)) return 1; // a single leaf
  for (const f of order) {
    const [a, b] = splitOn(idx, f);
    if (a.length && b.length) return buildOrdered(a, order) + buildOrdered(b, order);
  }
  return idx.length; // no useful split: each row its own leaf (worst case)
}
function permutations(arr) {
  if (arr.length <= 1) return [arr];
  const out = [];
  arr.forEach((x, i) => permutations(arr.slice(0, i).concat(arr.slice(i + 1)))
    .forEach(p => out.push([x, ...p])));
  return out;
}
function smallestLeafCount() {
  let best = Infinity, tried = 0;
  for (const order of permutations([0, 1, 2])) { tried++; best = Math.min(best, buildOrdered(ROWS.map((_, i) => i), order)); }
  return { best, tried };
}

// ── interactive state: a partial tree the user grows by clicking features ───
let root;
function freshRoot() { return { idx: ROWS.map((_, i) => i), split: null, kids: null }; }

// pick the first open (unsplit, impure) node, depth-first.
// NOTE: split can be 0 (feature index), so compare against null explicitly.
function firstOpen(node) {
  if (!node) return null;
  if (node.split === null && !pure(node.idx)) return node;
  if (node.kids) return firstOpen(node.kids[0]) || firstOpen(node.kids[1]);
  return null;
}
function applySplit(node, f) { node.split = f; const [a, b] = splitOn(node.idx, f);
  node.kids = [{ idx: a, split: null, kids: null }, { idx: b, split: null, kids: null }]; }

function renderData() {
  const t = document.getElementById('data');
  let h = fmt('<tr><th>Day</th>%map%<th>Play</th></tr>', { map: FEATURES.map(f => '<th>' + f + '</th>').join('') });
  ROWS.forEach((r, i) => {
    h += '<tr><td>' + (i + 1) + '</td>' + r.slice(0, 3).map(v => '<td>' + (v ? 'Y' : 'N') + '</td>').join('') +
      '<td class="play-' + (r[3] ? 'y' : 'n') + '">' + (r[3] ? '✓' : '✗') + '</td></tr>';
  });
  t.innerHTML = h;
}
function leafCount(node) { if (!node.kids) return 1; return leafCount(node.kids[0]) + leafCount(node.kids[1]); }
function renderTree() {
  const lines = [];
  (function walk(node, prefix, label) {
    if (pure(node.idx)) {
      const y = node.idx.length && ROWS[node.idx[0]][3] === 1;
      lines.push('<span class="node-pure-' + (y ? 'y' : 'n') + '">' + prefix + label + (y ? '✓ Play' : '✗ No play') + ' [' + node.idx.length + ']</span>');
      return;
    }
    if (node.split === null) {
      lines.push(fmt('<span class="node-open">%prefix%%label%? group of %length% (needs a split)</span>', { prefix: prefix, label: label, length: node.idx.length }));
      return;
    }
    lines.push('<span class="node-split">' + prefix + label + FEATURES[node.split] + '?</span>');
    walk(node.kids[0], prefix + '  ', 'N→ ');
    walk(node.kids[1], prefix + '  ', 'Y→ ');
  })(root, '', '');
  document.getElementById('tree').innerHTML = lines.join('\n');
}
function renderFeats() {
  const open = firstOpen(root); const box = document.getElementById('feats'); box.innerHTML = '';
  if (!open) return;
  FEATURES.forEach((name, f) => {
    const [a, b] = splitOn(open.idx, f);
    if (!a.length || !b.length) return; // useless split here
    const btn = document.createElement('button');
    btn.textContent = fmt('Split on %name% (gain %infoGain%)', { name: name, infoGain: infoGain(open.idx, f).toFixed(2) });
    btn.addEventListener('click', () => { applySplit(open, f); refresh(); });
    box.appendChild(btn);
  });
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls || ''); }
function refresh() {
  renderTree(); renderFeats();
  const open = firstOpen(root);
  if (!open) setStatus(fmt('Done! Your tree has %leafCount% leaves. All groups are pure.', { leafCount: leafCount(root) }), 'ok');
  else setStatus(fmt('Split the highlighted group of %length% days.', { length: open.idx.length }), '');
}

function greedy() {
  const open = firstOpen(root);
  if (!open) { setStatus(fmt('Tree already complete ( %leafCount% leaves).', { leafCount: leafCount(root) }), 'ok'); return; }
  let bestF = -1, bestG = -1;
  FEATURES.forEach((_, f) => { const [a, b] = splitOn(open.idx, f);
    if (a.length && b.length) { const g = infoGain(open.idx, f); if (g > bestG) { bestG = g; bestF = f; } } });
  if (bestF < 0) { setStatus('No useful split here.', ''); return; }
  applySplit(open, bestF); refresh();
  console.log('Greedy chose', FEATURES[bestF], 'with info gain', bestG.toFixed(3));
}
function optimal() {
  const { best, tried } = smallestLeafCount();
  setStatus(fmt('Smallest possible tree has %best% leaves (checked %tried% feature orderings).', { best: best, tried: tried }), 'ok');
  console.log('Optimal-leaf brute force:', best, 'leaves over', tried, 'orderings');
}

document.getElementById('greedy').addEventListener('click', greedy);
document.getElementById('optimal').addEventListener('click', optimal);
document.getElementById('reset').addEventListener('click', () => { root = freshRoot(); refresh(); });
root = freshRoot(); renderData(); refresh();
Result
Console

Press Greedy step and the builder picks the feature with the highest information gain — the locally best question right now. It is fast and usually good. But "best question right now" is not the same as "smallest tree overall." Press Find smallest tree to brute-force every ordering of questions: the count of trees explodes as features grow, which is exactly why no one does this in practice.

The Real Complexity

The honest answer: finding the best tree is brutally hard.

  • Reading a tree is trivial — follow the branches, one comparison per node.
  • Brute force tries every way to order and nest the questions. The number of distinct trees grows faster than exponentially in the number of features, so this is hopeless beyond a handful of columns.
  • It's NP-hard. In 1976, Laurent Hyafil and Ronald Rivest proved that constructing an optimal binary decision tree — the smallest one consistent with the data — is NP-complete. There is (almost certainly) no efficient algorithm that always returns the minimal tree.
  • So we cheat, on purpose. Classic learners like ID3, C4.5 and CART build the tree greedily: at each node they pick the single split with the highest information gain (or lowest Gini impurity) and never look back. Fast, readable, and usually close — but with no guarantee it is the smallest tree.

That is the punchline: the model prized for being simple to read is, underneath, an instance of the same intractability behind P vs NP. The greedy heuristic is not laziness — it is the rational response to a problem we cannot solve exactly at scale.

Where It Matters

Even though we never build the optimal tree, greedy trees are everywhere — because "readable rules from a table" is exactly what most real data looks like:

  • Credit and risk scoring: a tree gives a regulator-friendly, auditable chain of reasons for each approval or denial.
  • Medical triage and diagnosis: clinical decision rules are literally small decision trees that a person can follow at the bedside.
  • Random forests and gradient boosting: the best off-the-shelf models for tabular data are ensembles of greedy trees (XGBoost, LightGBM), trading the readability of one tree for accuracy.
  • Feature insight: which question the tree asks first tells you which variable matters most.

Learn why the optimal tree is hard and you understand a recurring pattern in machine learning: when the exact problem is NP-hard, a fast greedy heuristic plus an ensemble often beats chasing the perfect answer. The same tension appears in clustering and many other learning tasks.

Conclusion

Decision trees hide a quiet irony: the model we choose because it is simple to read is built on a problem we cannot solve. Finding the smallest tree that fits the data is NP-hard (Hyafil & Rivest, 1976), so every tree you have ever trained was grown by a greedy shortcut, one locally-best question at a time.

And it works beautifully. The next time a tree gives you a clean, explainable rule, remember that it is not the optimal rule — it is a clever approximation, dodging P vs NP with information gain. In machine learning, "good enough, and fast" usually wins over "perfect, and impossible."

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/decision-trees/Content licensed under CC BY-NC 4.0.