Implement Decision Tree Function

HardPython

Problem

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.

Constraints

1 <= len(features) <= 200
1 <= len(features[0]) <= 20
features is rectangular and labels has the same length as features
Each label is 0 or 1
0 <= max_depth <= 20
2 <= min_samples_split <= 200

Function Signature

def build_decision_tree(features, labels, max_depth, min_samples_split):

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.