Tree Applications

Decision Trees

What is a Decision Tree?

A decision tree makes predictions by asking a sequence of yes/no questions about the data, one per internal node, until it reaches a leaf that holds the answer. To classify a new example, start at the root, follow the branch that matches its features, and repeat at each node down to a leaf — the leaf's label is the prediction. The appeal is that the tree itself is readable: the path from root to leaf is a plain-language explanation of the decision.

How Does It Work?

Building the tree from data is a greedy, recursive process. At each node, every possible way of splitting the remaining data on a feature is scored by how well it separates the classes — the standard measure is Gini impurity, which is 0 for a perfectly pure group (every example the same class) and higher the more mixed a group is. The split chosen is whichever one minimizes the weighted impurity of the two resulting groups.

That same scoring process then repeats independently inside each of the two new groups, splitting further and further until a stopping condition is met — usually that a group is already pure, or a maximum depth is reached, or too few examples remain to split meaningfully. The result is a tree where each split is locally optimal, even though the overall tree isn't guaranteed to be the single best possible tree for the data.

Predicting "play outside?" from temperature — two splits fully separate the classes

Algorithm Steps

Compute the impurity of the current node's data (how mixed the classes are)
If the data is already pure, or a stopping condition (max depth, minimum samples) is met, make this node a leaf labeled with the majority class
Otherwise, find the best split:
- Try splitting on candidate thresholds for the available feature(s)
- For each candidate, compute the weighted impurity of the two resulting groups
- Keep whichever split minimizes that weighted impurity
Recurse into the left and right groups independently, building each subtree the same way

Time Complexity

Time Complexity: O(n · f · log n) to build, where n is the number of samples and f the number of features — each level considers every feature and threshold across roughly n samples.
Space Complexity: O(n) for the tree in the worst case (one leaf per sample), though depth limits keep real trees far smaller.

Time Complexity Analysis

Decision trees are valued for being interpretable — a doctor, loan officer, or engineer can read the exact chain of thresholds that led to a prediction, unlike many other models. They're rarely used alone at the state of the art, but they're the building block of ensemble methods like Random Forests and Gradient Boosted Trees, which combine many decision trees to trade away some interpretability for substantially better accuracy.

Daily DSA Challenge by Scale Engineer

Watch a decision tree greedily split a dataset to separate its classes

Enter a dataset and build a decision tree

Decision Tree

Build a tree to see it appear here

Decision node (?)RootLeaf color = predicted class

Test Your Knowledge before moving forward!

Decision Trees Quiz

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

Decision Tree Implementation

// Gini impurity: 0 when a set is pure (all one class), higher when mixed.
function gini(labels) {
  const counts = {};
  labels.forEach((l) => (counts[l] = (counts[l] || 0) + 1));
  const n = labels.length;
  let impurity = 1;
  Object.values(counts).forEach((c) => {
    const p = c / n;
    impurity -= p * p;
  });
  return impurity;
}

function majorityLabel(labels) {
  const counts = {};
  labels.forEach((l) => (counts[l] = (counts[l] || 0) + 1));
  return Object.entries(counts).sort((a, b) => b[1] - a[1])[0][0];
}

// Tries every midpoint between consecutive distinct values, keeping whichever
// split minimizes the weighted Gini impurity of the two resulting groups.
function bestSplit(data) {
  const values = [...new Set(data.map((d) => d.value))].sort((a, b) => a - b);
  let best = null;

  for (let i = 0; i < values.length - 1; i++) {
    const threshold = (values[i] + values[i + 1]) / 2;
    const left = data.filter((d) => d.value <= threshold);
    const right = data.filter((d) => d.value > threshold);
    if (left.length === 0 || right.length === 0) continue;

    const weighted =
      (left.length / data.length) * gini(left.map((d) => d.label)) +
      (right.length / data.length) * gini(right.map((d) => d.label));

    if (!best || weighted < best.weighted) best = { threshold, weighted, left, right };
  }
  return best;
}

// Recursively splits the data on whichever threshold most reduces impurity.
function buildTree(data, depth = 0, maxDepth = 4) {
  const labels = data.map((d) => d.label);

  if (new Set(labels).size === 1 || depth >= maxDepth || data.length < 2) {
    return { isLeaf: true, prediction: majorityLabel(labels) };
  }

  const split = bestSplit(data);
  if (!split) return { isLeaf: true, prediction: majorityLabel(labels) };

  return {
    isLeaf: false,
    threshold: split.threshold,
    left: buildTree(split.left, depth + 1, maxDepth),
    right: buildTree(split.right, depth + 1, maxDepth),
  };
}

function predict(tree, value) {
  if (tree.isLeaf) return tree.prediction;
  return value <= tree.threshold ? predict(tree.left, value) : predict(tree.right, value);
}

// Usage example
const data = [
  { value: 45, label: "No" }, { value: 70, label: "Yes" }, { value: 90, label: "No" },
];
const tree = buildTree(data);
predict(tree, 72); // "Yes"

Done With the Learning

Mark Decision Trees as done and view it on your dashboard

Explore Other Tree Topics

Huffman Coding

Heap Sort

Syntax Trees

Tree Diameter

Level-order Traversal

Structure & Properties