Decision Trees

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?

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">{{hint}}</p>
<table id="data" class="data"></table>
<div id="tree" class="tree"></div>
<div class="status" id="status">{{status_pick_feature}}</div>
<div class="feats" id="feats"></div>
<div class="btns">
  <button id="greedy" type="button">{{btn_greedy}}</button>
  <button id="optimal" type="button">{{btn_optimal}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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 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.

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.

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."