Decision Tree (ID3) Theory Guide

Rules & Common Mistakes

• Exam Trap: Never Reuse Categorical Features on the Same Path

  In basic ID3 trees, splitting on a feature like 'Weather' permanently crosses it off for that specific downward path only. A completely separate, parallel branch elsewhere in the tree can still use 'Weather' freely. Students constantly fail traces either by reusing a feature locally on the same path, or by mistakenly crossing it out globally for the entire tree.
• Exam Trick: Pure Nodes = Zero Math

  If a branch receives rows that are 100% 'Spam' or 100% any single class, do not waste exam time writing out the full log formula just to prove the answer is zero. A pure node has an entropy of exactly $0.0$ by definition. Simply state 'Pure Node = $0.0$ Entropy' on the paper, draw the leaf node, and move straight to the next branch.
• Exam Trap: The Unweighted Average Disaster

  The fastest way to lose marks on an Information Gain calculation is finding the left branch entropy, the right branch entropy, adding them together, and dividing by two. This is mathematically invalid. Each branch's entropy must be multiplied by its proportional weight — that branch's row count divided by the parent's total row count — before summing them into the final weighted average.
• Lab Trap: How to Handle Continuous Numbers

  Standard Information Gain cannot run directly on raw numbers like 'Salary' — every row would form its own unique branch, producing a useless, overfit tree. In a real lab environment, the algorithm sorts the values, scans for points where the class label changes, and tests those midpoints as binary threshold questions, such as 'Is Salary greater than 50k?'

Strengths, Weaknesses & When To Use It

When to use it:Decision Trees are the go-to algorithm whenever interpretability is non-negotiable. If a bank denies a loan or a hospital flags a patient as high-risk, the exact reasoning must be explainable. A Decision Tree hands back the precise sequence of rules that led to that decision. That said, on exams and in real-world competitions, bare Decision Trees are rarely deployed alone — they overfit too easily and are usually upgraded into Random Forests to fix stability issues.

Decision Tree vs. Random Forest

This is a classic exam question precisely because the two algorithms do not compete — one is built directly from the other. A Random Forest is simply an army of hundreds of Decision Trees forced to vote on a final answer collectively. Understanding exactly why data scientists abandoned single trees in favor of forests is the key to understanding modern ensemble learning as a whole.

• Memorization vs. Generalization: A single tree is a notorious overfitter — it perfectly memorizes the training data, including every noisy quirk and outlier, which causes it to fail badly on new, unseen data. A Random Forest builds each individual tree on a random subset of rows and features, then averages all the results together, mathematically canceling out the noise that any single tree latched onto.
• The Glass Box vs. The Black Box: A single Decision Tree is fully interpretable — the entire flowchart can be printed and traced to explain exactly why a specific prediction was made, step by step. A Random Forest sacrifices that transparency completely. It becomes an unreadable black box where hundreds of trees vote anonymously and no single tree's logic is authoritative on its own.
• The Butterfly Effect vs. Robustness: A single tree is highly unstable. Changing just a handful of training rows can flip which feature wins the root node, rewriting every single branch beneath it. A Random Forest easily absorbs those same small data changes, since any given fluctuation only affects a fraction of the hundreds of trees voting in the ensemble.
• Speed vs. Accuracy: A single Decision Tree trains almost instantly and demands very little memory, making it ideal for quick prototypes. A Random Forest requires significantly more RAM and CPU power to train hundreds of trees simultaneously across random data subsets. The trade-off is clear: sacrifice raw training speed in exchange for a substantial upgrade in real-world predictive accuracy.

Implementation Pseudocode

// DECISION TREE (ID3) — Recursive Partitioning by Information Gain
// Goal: recursively split the dataset by always choosing the feature
// that destroys the most uncertainty, measured by Information Gain.
// Stop splitting once a branch is pure or no features remain.

FUNCTION buildTree(dataset, availableFeatures):

    // ============================================================
    // BASE CASE 1: All rows share the same label
    // ============================================================
    IF all rows in dataset have the same label:
        RETURN LeafNode(label = that shared label)
        // Pure node — entropy is 0.0, no further math needed.
    END IF

    // ============================================================
    // BASE CASE 2: No features left to split on
    // ============================================================
    IF availableFeatures is empty:
        RETURN LeafNode(label = MAJORITY_VOTE(dataset))
        // Out of questions to ask — predict whichever class is most common.

    // ============================================================
    // STEP 1: Calculate the Base Target Entropy
    // ============================================================
    P = COUNT rows in dataset WHERE label == Positive
    N = COUNT rows in dataset WHERE label == Negative
    baseEntropy = entropy(P, N)
    // This is the starting 'messiness' before testing any feature.

    // ============================================================
    // STEP 2: Test Every Feature, Every Value
    // ============================================================
    bestFeature = NULL
    bestGain    = -INFINITY

    FOR EACH feature IN availableFeatures:

        weightedEntropy = 0

        FOR EACH uniqueValue IN feature.uniqueValues:
            branchRows = FILTER dataset WHERE feature == uniqueValue
            p_i = COUNT branchRows WHERE label == Positive
            n_i = COUNT branchRows WHERE label == Negative

            branchEntropy = entropy(p_i, n_i)
            branchWeight  = COUNT(branchRows) / COUNT(dataset)

            weightedEntropy = weightedEntropy + (branchWeight * branchEntropy)
            // Exam Trap: Do NOT just add branch entropies and divide by
            // the number of branches. Each branch entropy must be scaled
            // by its row-count weight first, or the gain calculation is invalid.
        END FOR

        // --- STEP 3: Calculate Information Gain for this feature ---
        gain = baseEntropy - weightedEntropy

        IF gain > bestGain:
            bestGain    = gain
            bestFeature = feature
        END IF

    END FOR

    // ============================================================
    // STEP 4: Build the Split Node and Recurse
    // ============================================================
    node = SplitNode(feature = bestFeature)

    FOR EACH uniqueValue IN bestFeature.uniqueValues:
        subset = FILTER dataset WHERE bestFeature == uniqueValue

        remainingFeatures = COPY(availableFeatures)
        REMOVE bestFeature FROM remainingFeatures
        // Exam Trap: Always pass a COPY of the remaining features down
        // this specific branch. Removing bestFeature from the original
        // shared list would cross it out globally, blocking parallel
        // branches elsewhere in the tree from ever using it again.

        node.addBranch(uniqueValue, buildTree(subset, remainingFeatures))
    END FOR

    RETURN node

END FUNCTION

Time & Space Complexity

Decision Tree Exam Traps & FAQs

• What happens if two features have the exact same Information Gain?

  Mathematically, they are equally good — either choice produces a valid tree, even if it looks different from a classmate's. On an exam, pick either feature confidently. To stay safe and consistent, default to whichever one comes first alphabetically, and simply note the tie on the paper.

• I ran out of features to split on, but my leaf is still mixed. What do I do?

  This happens when the dataset has contradictory rows — identical feature values but different target labels. Splitting further is impossible at that point. Stop and apply a Majority Vote instead. If the leaf holds 2 'Spam' rows and 1 'Legit' row, simply label the leaf 'Spam' and move on.

• My exam asks for Gini Impurity instead of Entropy. Does the whole process change?

  The process stays exactly the same — only the starting formula changes. Instead of logarithms, Gini uses simple probabilities: $1-\sum p_i^2$. Base impurity, weighted feature impurity, and the final subtraction for gain all work identically. Gini is simply faster to calculate by hand on a written exam.

• How do I handle a row that has a missing value (?) for the feature I am testing?

  Written exams usually avoid this scenario entirely. If it does appear, the standard ID3 approach assigns that row the most common value for that feature within the current subset. Some lab variations instead simply ignore that specific row for the calculation and move forward.

• How do I calculate Entropy for a column with continuous numbers like Age or Salary?

  Raw numbers are never used directly in standard ID3. Sort the values, find every point where the target class changes, and treat those midpoints as binary threshold questions like 'Is Age greater than 25?' Calculate Information Gain for that binary split exactly like any categorical feature.