Decision Tree Regression from Scratch

Build a decision-tree regression model from scratch using the training rows trainX and their numeric targets trainY. Return one prediction for each row of queryX, in query order. Implement split selection, recursive construction and prediction traversal directly without a machine-learning or tree-fitting library.

For this exercise, assume all features and training targets are integers. Every training and query row has the same positive number of features. Repeated training rows remain separate sample occurrences.

At each node, consider every feature. Sort its distinct values among that node's samples and consider the midpoint between every two consecutive values as a split threshold. A sample goes left when its feature value is less than or equal to the threshold; otherwise, it goes right. Each candidate has two nonempty groups.

For a group G, its prediction is the arithmetic mean mean(G) of its targets, and its squared error is SSE(G) = sum((y - mean(G))^2). Choose the split minimizing SSE(left) + SSE(right). Use exact mathematical values for split comparisons. On equal errors, prefer the smaller feature index; if that also ties, prefer the smaller threshold.

The root has depth 0. A node becomes a leaf if its depth equals maxDepth, no valid split exists, or the best split does not strictly reduce the node's squared error. Otherwise, build both children using the same rules. Every leaf predicts the mean of all sample occurrences that reach it, including when their targets differ.

Traverse the fitted tree for each query using the same inclusive-left split rule and return the reached leaf's mean. Each prediction is judged with absolute tolerance 10^-6.

What the interview report shared

The report asks for a decision-tree regression model built from scratch. It does not disclose a dataset, split criterion, depth or stopping rule, tie convention, or training and prediction interface. The deterministic rules above define this practice version.