The Seedling Sorter

A greenhouse sorts young tomato plants into three bins: "sell", "grow" (keep growing) and "compost". Each plant is measured as [height_cm, leaf_count]. Instead of writing the sorting rules by hand, the team wants a decision tree grown from past plants, with stopping rules so it can't keep splitting until it has memorised every plant.

Growing the tree. All training rows start at the root, which is at depth 0. At every node:

1. Stop and make a leaf if any of these holds:
   • every row in the node has the same label (the node is pure),
   • the node's depth equals max_depth,
   • the node has fewer than min_samples_split rows,
   • no split is possible, because each feature has only one value across the node's rows.
2. Otherwise, split on the best question. For each feature, sort the distinct values that feature takes in this node, and try a threshold halfway between each neighbouring pair. Rows with value <= threshold go left, the rest go right. Keep the split with the lowest score (defined below).
3. Grow both children the same way, one level deeper.

A split's score is the weighted Gini impurity of its two groups:

Here $n_L$ and $n_R$ count the rows sent each way, $n$ counts the node's rows, and $p$ is a label's share of the rows in that group. Treat two scores within $10^{-9}$ of each other as a tie, and break ties by taking feature 0 before feature 1, then the smaller threshold.

A leaf predicts the label held by most of its rows. If two labels tie for most, it predicts the one that comes first alphabetically.

Task: write grow_and_predict(X_train, y_train, X_test, max_depth, min_samples_split). Grow the tree, then return a tuple (predictions, leaves):

• predictions: the predicted label for each row of X_test, in order. A row goes left at a node when its value is <= that node's threshold.
• leaves: the number of leaves in the finished tree.

There, a height split at 3 and a leaf-count split at 1.5 both score 0, so the tie rule picks height. The new plant has height $3 \le 3$, so it goes left.