Decision Tree best split (assemble a minimal tree)

Implement three functions:

def find_best_split(input: np.ndarray, labels: np.ndarray) -> tuple[int, float, float] | None:
    """Search every feature/threshold, return (feature, threshold, gain) or None."""

def build_tree(input: np.ndarray, labels: np.ndarray, max_depth: int) -> dict:
    """Recursively assemble a tree using find_best_split() at every node."""

def predict_tree(tree: dict, input: np.ndarray) -> np.ndarray:
    """Walk the tree from root to leaf for every row of input."""

• find_best_split tries every feature, and for each feature every midpoint between consecutive sorted unique values as a candidate threshold, input[:, feature] <= threshold vs. > threshold. A midpoint between two adjacent present values always puts at least one sample on each side, by construction.
• build_tree stops and returns a leaf when max_depth reaches 0, fewer than 2 samples remain, the node is already pure (01-gini-impurity's gini_impurity is 0), or find_best_split returns None (no split improves anything).
• A leaf's prediction is the majority class among its samples.
• Reuse 01-gini-impurity and 02-information-gain rather than reimplementing them.