PART 2 • CORE MACHINE LEARNING • LEVEL 09
Decision Trees & Random Forests
Turn data into explainable questions, measure every split mathematically and combine randomized trees into a stable ensemble. Learn the complete path from one decision node to production-ready forest reasoning.
Mock score ≥ 70?
Projects ≥ 2?
Not Placed
Placed
Review
RANDOM FORESTMany diverse trees → one reliable vote
LEARNING OUTCOMES
By the End of This Level, You Can
QUICK REVISION
Six Ideas to Bring Forward
A tree repeatedly divides data; a forest reduces the instability of one tree.
A measurable input considered for a split.
A rule that sends samples left or right.
How mixed the target values are.
The impurity removed by a candidate split.
Train diverse models and combine them.
Control complexity using unseen folds.
CONCEPT 01
A Decision Tree Is a Hierarchy of Questions
Each internal node tests a feature; each leaf produces a prediction.
Contains the complete training subset and selects the opening split.
Further separates the subset reaching that branch.
Represents true/false or a categorical route.
Stores a class distribution or numeric target estimate.
A decision tree maps a feature vector through a sequence of if–else conditions. The root sees every training sample. Each split creates child regions, and recursion continues until a stopping condition is met. A classification leaf normally predicts its majority class and can expose class proportions as probabilities. A regression leaf usually predicts the mean target value in that region.
A placement tree may first test mock score, then projects, before predicting placed or not placed.
Interviewers frequently ask you to translate a small tree into readable if–else code.
A tree branch describes an association learned from data; it does not automatically prove a causal relationship.
CONCEPT 02
Recursive Partitioning Builds Rectangular Regions
Each split divides one current region into smaller, more homogeneous regions.
Search current node
Evaluate allowed feature–threshold pairs.
Choose maximum gain
Keep the split producing the purest weighted children.
Repeat independently
Grow left and right subtrees on their own subsets.
Standard CART-style trees use axis-aligned questions such as score ≤ 70. One question creates two regions. Later questions operate only inside a selected region, so the final feature space is divided into rectangles or hyperrectangles. The greedy algorithm chooses the best immediate split at every node rather than searching every possible complete tree.
After separating low scores, the high-score branch can split again using project count without affecting the low-score branch.
Know why greedy growth is computationally practical but does not guarantee the globally smallest or best tree.
A later split does not redraw the complete feature space; it divides only the samples that reach its node.
CONCEPT 03
Gini Impurity Measures Class Mixing
Gini is zero when every sample in a node belongs to one class.
Gini(S) = 1 − Σ pᵢ²1 − 1² − 0² = 01 − .5² − .5² = .51 − .8² − .2² = .32For each class, square its proportion and add the results. Subtracting from one gives the probability that two labels sampled according to the node distribution would differ. In binary classification, maximum Gini is 0.5 at an even split; with more classes, its maximum approaches one.
For six placed and two not placed students, Gini = 1 − (6/8)² − (2/8)² = 0.375.
Gini calculations are common written-test questions because they are quick and reveal whether you understand proportions.
Gini impurity is not the same as the Gini coefficient used in inequality analysis.
CONCEPT 04
Entropy and Information Gain
Entropy measures uncertainty; gain measures how much a split removes.
ENTROPY
→H(S) = −Σ pᵢ log₂pᵢPure binary node: 0 bit
Balanced binary node: 1 bit
INFORMATION GAIN
Gain = H(parent) − Σ (|child|/|parent|)H(child)Larger positive gain means greater reduction in uncertainty.
Entropy is the expected information needed to identify a node’s class. A pure node has no uncertainty, while a balanced binary node has one bit. To evaluate a split, calculate each child’s entropy, weight it by the fraction of samples entering that child, and subtract the weighted result from parent entropy.
If a parent entropy of 1 is split into two perfectly pure equal children, weighted child entropy is 0 and information gain is 1.
Be able to compare entropy and Gini: both favor purity and often choose similar splits, but their formulas and scales differ.
Do not average child impurities equally unless the child nodes contain equal numbers of samples.
CONCEPT 05
How Candidate Thresholds Are Generated
Sorted feature values reveal the meaningful places where a decision can change.
42, 55, 68, 72, 9048.5, 61.5, 70, 81gain(feature, threshold)argmax gainFor a numeric feature, predictions change only when a threshold passes a training value. Efficient implementations sort values and evaluate boundaries between adjacent distinct values, often prioritizing boundaries where labels change. Every candidate is assessed using the weighted impurity of its resulting children.
Between observed scores 68 and 72, threshold 70 creates exactly the same partition as any value strictly between them.
A from-scratch best-split problem tests sorting, loops, counting and careful weighted arithmetic.
A threshold is usually not restricted to an observed value; a midpoint cleanly represents the boundary.
CONCEPT 06
Regression Trees Reduce Target Variance
Instead of class impurity, regression splits minimize squared prediction error.
ŷleaf = mean(y in leaf)The mean minimizes squared error inside the region.
SSE = Σ(yᵢ − ȳnode)²Measures remaining numeric variation.
SSEparent − SSEleft − SSErightSelect the largest decrease in squared error.
A regression tree uses the same recursive splitting structure but works with continuous targets. Each candidate split is judged by how much it reduces within-node squared error or variance. Every terminal region predicts a constant value, so a single regression tree creates a piecewise-constant function.
If salaries [3, 4, 9, 10] split into [3,4] and [9,10], two tight leaves have much lower error than one mean of 6.5.
Explain why regression-tree predictions do not naturally extrapolate beyond observed target patterns.
Classification criteria such as Gini should not be applied directly to continuous targets.
CONCEPT 07
Stopping Rules Control Tree Complexity
Unrestricted growth can create nearly pure training leaves and poor generalization.
Directly caps the longest root-to-leaf path.
Blocks splitting very small nodes.
Ensures each leaf has a minimum sample count.
Controls overall partition count.
Especially important for forest diversity.
Rejects tiny improvements.
Pre-pruning stops growth before every training detail is captured. Depth controls interaction complexity, while minimum-sample settings prevent fragile decisions based on tiny groups. These are hyperparameters and must be selected using validation data, not the final test set.
A leaf containing one student can memorize an exception; requiring ten samples makes its estimate more stable.
In interviews, connect deep trees with low training bias and high variance.
Maximum depth is not “the number of nodes”; a binary depth-d tree can contain many nodes.
CONCEPT 08
Post-Pruning Removes Weak Branches
Grow a larger tree, then trade training fit for structural simplicity.
COMPLEX TREELow training error
✂Many branches may explain noise.
COST-COMPLEXITY OBJECTIVE
→Rα(T) = R(T) + α|leaves(T)|Penalty α rewards smaller trees.
VALIDATED SUBTREEBetter generalization
Choose α through cross-validation.
Cost-complexity pruning assigns a penalty to every leaf. When α is zero, fit dominates; as α grows, additional leaves must justify themselves through enough error reduction. A pruning path provides candidate subtrees, and cross-validation selects the complexity with the strongest unseen performance.
A three-sample branch that improves training accuracy by one case may disappear when its complexity penalty exceeds that benefit.
Know the difference between pre-pruning controls and post-pruning with ccp_alpha.
Pruning is not selected by looking for the highest training score; that favors the unpruned tree.
CONCEPT 09
Categorical Values, Missing Data and Pipelines
The tree may not need scaling, but it still needs a reliable feature pipeline.
Axis-aligned trees are generally unaffected by monotonic scaling because order and possible partitions stay unchanged. However, categorical features must match the implementation’s supported representation, and missing values need explicit handling unless the estimator has native missing-value logic. Put every learned transformation inside a pipeline to prevent leakage and keep inference consistent.
Changing age from years to months changes thresholds numerically but preserves the ordering and equivalent partitions.
“Trees do not require scaling” does not mean “trees require no preprocessing.”
Integer-encoding unordered categories can introduce an artificial order if the estimator treats the codes as numeric.
CONCEPT 10
Feature Importance Needs Careful Interpretation
Importance ranks model usage—not scientific cause.
Fast and built into many tree implementations, but biased toward features with many split opportunities.
Evaluates how performance changes when one feature’s information is disrupted.
Trace its path or use validated explanation tools while respecting feature dependence.
Mean decrease in impurity adds the weighted gains credited to a feature across a fitted tree or forest. Permutation importance instead shuffles a feature and measures validation-score deterioration. Correlated features can share or substitute importance, so rankings require domain knowledge, stability checks and cautious language.
If attendance and study hours carry similar information, shuffling either alone may cause only a moderate score drop.
A strong answer distinguishes global model importance from local prediction explanation.
High importance does not prove that changing the feature will cause the prediction target to change in the real world.
CONCEPT 11
Bagging Reduces Variance Through Resampling
Each tree sees a different bootstrap version of the training data.
ORIGINAL DATAn samples
⇢BOOTSTRAP 1
A B B D F FBOOTSTRAP 2
A A C E E FBOOTSTRAP 3
⇢B C C D E FAGGREGATEVote / average
A bootstrap sample draws n records with replacement from n training records. Some rows appear repeatedly and others are omitted. A high-variance learner is fitted independently to each resample, and predictions are averaged or voted. Averaging reduces variance most effectively when individual models are accurate enough and their errors are not perfectly correlated.
One unstable tree may change after a few records move, while the majority of 200 diverse trees usually changes much less.
Explain why bagging mainly attacks variance rather than systematically removing bias.
Bootstrap samples are not disjoint folds; they overlap and contain duplicate records.
CONCEPT 12
Random Forests Add Feature Randomness
Restricting features at each split decorrelates the trees.
Create a different training sample per tree.
Only a random subset competes for the split.
Each learner captures a different view.
Classification votes; regression averages.
Pure bagging can produce very similar trees when one dominant feature wins most root splits. Random forests restrict the candidate feature set at every node, forcing alternative signals to participate. This typically reduces correlation between trees and improves the variance reduction gained from averaging.
If mock score is dominant, some trees may be forced to begin with projects or attendance and learn complementary rules.
Know that max_features is sampled for every split—not once for the entire forest.
A random forest is more than many identical trees; diversity is central to its benefit.
CONCEPT 13
Out-of-Bag Evaluation Uses Omitted Samples
Every bootstrap tree leaves some training records unused.
≈ 63.2%Unique samples expected inside one bootstrap sample
≈ 36.8%Records left out and available as OOB cases for that tree
Aggregate OOB votesEvaluate each record using only trees that did not train on it
The probability that a record is not selected in n draws is (1−1/n)ⁿ, approaching e⁻¹ ≈ 0.368. For each training record, collect predictions from trees whose bootstrap samples excluded it. Aggregating these predictions produces an internal generalization estimate without creating a separate validation split.
A row may train trees 1, 3 and 5 but be evaluated by trees 2, 4 and 6 where it was out-of-bag.
OOB score is useful, but cross-validation may still be preferred for careful model comparison and tuning.
OOB evaluation is not based on one fixed 36.8% holdout; the omitted set differs for every tree.
CONCEPT 14
Single Tree or Forest?
Choose based on the need for interpretability, stability, latency and accuracy.
DECISION FACTOR
DECISION TREE
RANDOM FOREST
Interpretability
One path is easy to inspect
Many paths need aggregate explanation
Variance
Often high
Usually lower through averaging
Prediction cost
One root-to-leaf traversal
Traverse every selected tree
Non-linearity
Strong axis-aligned interactions
Combines many different partitions
Scaling
Usually unnecessary
Usually unnecessary
Best use
Transparent rules or a compact baseline
Strong general-purpose tabular baseline
A shallow tree offers a direct rule system but can underfit. A deep tree captures interactions yet changes easily with the sample. A random forest sacrifices single-tree transparency and adds memory and latency, but often produces stronger and more stable tabular predictions. Selection must be based on validated performance plus deployment constraints.
Use a depth-three tree when policy requires a short auditable rule; use a forest when predictive stability is more important.
Answer algorithm-comparison questions using data type, bias–variance, interpretability, scaling and inference cost.
A forest is not guaranteed to beat every tuned alternative on every dataset; validation remains necessary.
CODEBHAVYA PREMIUM VISUALIZER
LIVE EXPERIMENTDecision Split Laboratory
Change the feature, threshold and criterion. Watch samples move into child nodes and verify every impurity calculation.
INTERACTIVE LEARNING
🎬 Decision Tree Training — Visual Flow
The builder repeats the same search separately inside every non-terminal node.
Begin with the records that reached this node.
Try permitted features and thresholds.
Compare parent impurity with weighted children.
Store the best rule and divide the records.
Make a leaf or repeat inside each child.
CODEBHAVYA PREMIUM VISUALIZER
LIVE ENSEMBLERandom Forest Voting Laboratory
Generate a seeded forest, inspect randomized rules and see how diversity changes the ensemble prediction.
PROGRAM TRACING
Trace Best-Threshold Search from Scratch
Follow candidate thresholds, left/right partitions, weighted Gini and every best-gain update.
Press Next to execute the first statement.
EXPRESSION
—OUTPUT
Waiting for print(...)
Step 0 of 0
CORE ALGORITHM
Decision Tree and Random Forest Logic
Use this compact view for revision before coding or interviews.
- Send training records to the root.
- Generate valid feature–threshold candidates.
- Calculate parent and weighted-child impurity.
- Store the candidate with maximum gain.
- Partition records into child nodes.
- Repeat until a stopping rule is reached.
- Store a prediction distribution in each leaf.
- Create a bootstrap row sample for every tree.
- At every node, sample a feature subset.
- Choose the best split among only those features.
- Grow the tree using configured stopping rules.
- Repeat independently for many trees.
- Vote for classification or average for regression.
- Optionally aggregate out-of-bag predictions.
PROGRAMMING PROBLEMS
💻 CodeBhavya Tree & Forest Challenges
Solve each problem first. Viewing the model program reduces the recorded score.
Progress
KNOWLEDGE CHECK
Test Your Tree and Forest Understanding
Select answers, then check to see your choice, the correct answer and its explanation.
Not checked yet
PLACEMENT CHECKPOINT
Choose the Right Explanation in Interviews
Strong candidates connect the mechanism with its practical consequence.
Recursive partitions can isolate noise and tiny sample groups, producing high variance.
Bootstrap and feature randomness create diverse trees whose averaged errors are more stable.
Monotonic scaling preserves ordering and therefore preserves equivalent axis-aligned partitions.
Every training row can be evaluated using only trees whose bootstrap samples omitted it.
Split selection and importance describe predictive association under the observed data.
Depth, leaf support, feature sampling, tree count and class-related settings using validation.
INTERVIEW PREPARATION
🎤 Decision Trees & Random Forests — Interview Questions
Answer aloud before opening each explanation.
KEY TAKEAWAY
From One Greedy Rule to a Stable Ensemble
Decision trees make local greedy partitions that are easy to follow but naturally unstable.
Impurity criteria identify useful splits, complexity controls protect generalization, and random forests reduce variance through row and feature randomness. Always validate the complete pipeline and interpret importance as model evidence—not causal truth.
EXTRA TIPS
Six Practical Habits
Begin with a shallow tree and inspect whether its rules make domain sense.
Tune minimum leaf support, not only maximum depth.
Use stratified validation when classification classes are imbalanced.
Increase forest size until validation stability and latency reach a sensible balance.
Compare impurity importance with permutation importance on held-out data.
Fix random seeds for reproducibility, then test stability across several seeds.
EXTRA PRACTICE
✍️ Questions for Independent Revision
- 01
Calculate Gini impurity for class counts [7, 3].
- 02
Calculate entropy for a perfectly balanced binary node.
- 03
Explain why child impurities must be weighted by sample counts.
- 04
Generate candidate midpoints from values [2, 5, 9, 10].
- 05
Trace a query through a three-level tree and state its leaf probability.
- 06
Compare max_depth and min_samples_leaf as overfitting controls.
- 07
Explain cost-complexity pruning using the role of α.
- 08
Why does a regression tree produce piecewise-constant predictions?
- 09
Derive why about 36.8% of records are OOB for one large bootstrap sample.
- 10
Explain how random feature selection reduces tree correlation.
- 11
Compare impurity-based and permutation importance.
- 12
Design a leakage-safe forest pipeline for mixed tabular data.