Why can a decision tree's greedy split search produce a globally suboptimal tree?
answer
- one decision at a time, never revisited
- best now can be worst overall
- an interaction hides from a single cut
- XOR gives exactly zero gain
- exact optimum is NP-hard
basics
~20 sA tree's splits are each chosen to minimise impurity at that node alone, with no lookahead, so the locally best cut can foreclose a better pair of cuts beneath it. Finding the globally optimal tree is NP-hard.
solid answer
~50 sTree growth is a sequence of irrevocable local decisions. At the root the learner picks whichever single cut drops impurity most, then never reconsiders it - even if a slightly worse root would have unlocked two excellent children. The pathological case is a pure interaction: with a binary target equal to the XOR of two balanced binary features, splitting on either feature alone leaves both children at 50/50, so the impurity gain is exactly zero, yet a two-level tree separates the classes perfectly. Constructing the optimal tree by exhaustive search is NP-hard, so no mainstream learner attempts it. In practice you live with it: let the tree grow past a zero-gain node rather than stopping there, and lean on ensembles, which randomise the candidate features at each split so different trees take different roots and collectively recover interactions the single greedy path missed.
go deeper
Remember one fact: the tree picks the best split available right now and never goes back to change it, so the finished tree is not guaranteed to be the best possible tree.
Be able to construct the counterexample - a target equal to the XOR of two features gives exactly zero impurity gain on either feature alone, yet a depth-two tree is perfect - and explain why the score cannot see it.
Show you have diagnosed this in real work: suspecting an interaction when accuracy jumps only at depth two, resisting a stop-on-zero-gain rule, and choosing between an explicit combined feature and an ensemble.
Own the modelling-strategy call. Decide when a single interpretable greedy tree is the right artefact despite its suboptimality, when the problem justifies an exact optimal-tree formulation, and how to stop teams reading a greedy tree's shape as a causal account.
## What "greedy" means here Recursive partitioning makes one decision at a time and never revisits it. At each node it evaluates every candidate cut, scores each by the size-weighted impurity of the children it would create, keeps the best, and recurses into both children independently. Nothing in that loop asks what the *grandchildren* would look like, and nothing ever backtracks. The objective being optimised is the impurity drop **at this node**, not the quality of the finished tree. ## Why not just search for the best tree? Because you cannot afford it. Constructing an optimal binary decision tree is NP-hard - a result established in the 1970s - and the search space grows explosively: every node multiplies the number of feature-times-threshold choices by everything the subtrees below might do. Greedy growth reduces this to a manageable per-node scan, and empirically it produces good trees on most data. The greediness is a deliberate, well-understood trade of optimality for tractability, not an oversight. ## The failure mode, concretely Take 100 rows, two balanced binary features `A` and `B`, 25 rows in each combination, and a target `y = A XOR B`. The parent node is 50/50, Gini `0.5`. - Split on `A`: the `A = 0` child holds 25 rows with `y = 0` and 25 with `y = 1` - still 50/50, Gini `0.5`. Same for the other child. Weighted child impurity `0.5`, **gain exactly zero**. - Split on `B`: identical, **gain exactly zero**. No single split helps at all, yet splitting on `A` and then on `B` inside each child yields four perfectly pure leaves. The signal is entirely in the interaction, and a one-step-ahead score cannot see it. If the learner is configured to stop when no split achieves a positive impurity decrease, it will emit a stump and declare both features useless. A milder, far more common version: consider a semiconductor yield tree where the root split lands on chamber temperature because that single variable separates the pass rate best on its own. The real physics might be that temperature only matters in combination with gas flow, and a root split on flow - marginally worse in isolation - would have produced two children in which temperature becomes decisive. The greedy learner cannot know that, because it never looks two moves ahead. ## Practical consequences - **A zero-gain feature is not a useless feature.** Reading the root's chosen feature as "the strongest predictor" is a mistake; it is only the strongest *marginal* predictor at that node under that impurity measure. - **Stopping the instant no split improves impurity is risky** on data with interactions, because that is exactly the situation the greedy score cannot detect. Growing further and cutting back afterwards is safer. - **Run-to-run instability at the root** compounds this: two nearly-tied candidate cuts mean the entire subtree below can differ between fits. - **Reported structure is not an explanation.** Because the path taken depends on which cut won a near-tie, reading a single tree's shape as the causal story of the data over-reads it. ## What actually helps 1. **Grow deeper, then cut back.** Let the tree pass through nodes with negligible immediate gain instead of halting there, and reduce the tree afterwards. 2. **Ensembles.** Averaging many trees that each consider a random subset of features per split means different trees are forced into different roots; interactions that the single greedy path skipped appear in some members, and the aggregate recovers them. Sequential boosting attacks the same problem from the other side, by fitting each new tree to what the current ensemble still gets wrong. 3. **Give the interaction to the model directly.** If domain knowledge says two variables only matter jointly, an explicitly constructed combined variable turns an invisible interaction into a single axis the greedy search can see. 4. **Lookahead, cautiously.** Scoring pairs of consecutive splits solves the textbook XOR case, but the candidate set is squared, and the deeper search can fit noise as readily as structure. It is a research technique, not a default. 5. **Optimal-tree solvers.** For small feature counts and shallow depth limits, exact formulations can find the provably best tree. They do not scale to wide tabular data, but they are the honest answer to "can it be done properly?". ## How to answer in an interview Name the mechanism (one node at a time, no lookahead, no backtracking), give the XOR example with the zero gain, cite NP-hardness as the reason nobody does better exactly, and finish with the mitigation you would actually reach for - growing past zero-gain nodes and using an ensemble rather than hand-tuning a single tree.
- Does adding one level of lookahead fix the problem?It fixes the textbook two-feature interaction, because scoring pairs of consecutive cuts reveals a gain that neither cut shows alone. But the candidate set is squared, so training cost jumps, and the deeper search finds noisy pairings as readily as real ones - so it can raise variance. It also only pushes the horizon out by one level; three-way interactions are still invisible.
- How do ensembles of trees partly compensate for greedy split selection?By making different trees take different paths. When each split may only consider a random subset of features, the marginally-best feature is often unavailable, so some trees are forced to root on a feature that only pays off in combination. Averaging across the collection recovers structure any single greedy path would have missed. Boosting does it differently, by growing each new tree against the errors the current ensemble still makes.
- A candidate feature shows zero impurity gain at the root. What would you conclude?Only that it carries no marginal signal at that node under that impurity measure. It may be decisive once conditioned on another variable - the XOR case is the extreme illustration. I would let the tree grow past that node rather than stopping, check whether accuracy jumps at depth two or three, and test an explicit interaction term before writing the feature off.
saying these in an interview costs you the question
- Claims the tree finds the optimal partition of the feature space
- Says a feature with zero root gain carries no information
- Assumes the root feature is by definition the strongest predictor
- Proposes exhaustive tree search without knowing it is NP-hard
- Suggests lookahead everywhere without counting the cost