A regression tree considers a numeric feature with n distinct values at a node. Describe how the best split point is found, give the cost of scanning that feature naively and after sorting, and give the total cost of building a depth-d tree on n rows and p features.

A regression tree considers a numeric feature with n distinct values at a node. Describe how the best split point is found, give the cost of scanning that feature naively and after sorting, and give the total cost of building a depth-d tree on n rows and p features.

Approach: Write the split criterion as the drop in the sum of squared deviations, then note that scanning candidate thresholds in sorted order lets both child sums be updated in constant time.

Sorting a feature costs O(n log n) and the scan over all n - 1 candidate thresholds then costs O(n) using running prefix sums, so a depth-d tree costs O(p * n log n + d * p * n) when the sort order is computed once and reused. The split criterion for regression is the reduction in total squared error, sum_left (y - mean_left)^2 + sum_right (y - mean_right)^2, and because each child's sum of squares is determined by the count, the sum of y and the sum of y^2, moving the threshold one row at a time updates both sides in constant time. Recomputing each candidate from scratch instead gives O(n^2) per feature per node, the naive cost. Each level of the tree touches every row exactly once across all its nodes, so a level costs O(p*n) after sorting. Histogram implementations bucket each feature into a fixed number of bins, typically 256, cutting the per-node scan to O(p * bins), which is what makes gradient boosting on millions of rows tractable. A categorical feature with k levels has 2^{k-1} - 1 possible partitions, so implementations sort categories by their target mean and scan that order instead.

Follow-up: For a binary classification tree with Gini impurity, can the same prefix-sum trick be used, and what statistics must be maintained per candidate threshold?

Key concepts: split criterion, prefix sums, sorting cost, variance reduction.