Implement Decision Tree Function

Qlik Sense can use decision-tree logic to explain binary outcomes in an analytics dataset. Implement a simplified CART classifier that recursively selects the numerical feature split with the largest reduction in Gini impurity.

Formal Specification

Implement build_decision_tree(features, labels, max_depth, min_samples_split).

• features is a list of n rows, where each row contains p numeric feature values.
• labels is a list of n binary integers, 0 or 1.
• Return a nested dictionary. A leaf is { "prediction": label }. A split node is { "feature": i, "threshold": t, "left": ..., "right": ... }.
• Send values <= threshold left and values > threshold right.
• Consider thresholds halfway between consecutive distinct sorted values. On equal gain, keep the first feature and threshold encountered.

Stop when the node is pure, reaches max_depth, contains fewer than min_samples_split rows, or has no split with positive gain. A tied leaf prediction is 0.