XOR Ambush

A dataset's true label depends on the XOR of two binary features (label = 1 iff exactly one of feature A, feature B is 1). A standard greedy decision tree evaluates single-feature splits at the root using information gain. What happens?

Information gain automatically detects the pairwise interaction and splits on both features simultaneously at the root

Neither feature alone provides any information gain at the root, so the greedy tree may pick an uninformative or arbitrary first split before eventually recovering the pattern deeper down

The tree immediately identifies feature A as the perfect root split because it correlates with the label 50% of the time

The tree fails to build entirely since XOR relationships violate the axioms required for impurity measures