Regression Trees - Splitting and decision rules

Question

I understand that a regression tree is built by splitting a node, such that the MSE for the label/output variable is minimized in each of the two resulting nodes. I have two questions about this:

1.) Is the search for the optimal split even dependent from the input variables? The MSE could be minimized through exhaustive search for two subsets which minimize the MSEs of the label in each of the subsets. No knowledge about input variables is needed for this. If this is the case, how are the decision rules for upcoming instances, for which an output should be predicted, set? How is it decided which feature to split at what point in order to obtain the split into the 2 subsets?

2.) Or does the algorithm run through all possible splits (split at each value of each feature once) and then chose the one with the minimal MSEs? This way the decision rule would be clear.

Answer 1

Short Answer:

1.Yes feature variables are needed for split. No the best 2 subsets for MSE reduction are not created. 2.Yes

Long answer:

Decision trees are greedy algorithms that choose a feature and split at each node and use that feature and cut to divide the data.

So as you mentioned in point 2 the tree starts building with all y values in the first node and iterates over all combinations for each feature and selects the best feature and value split to divide into 2 groups which are further split.

The termination conditions would be number of observations in the leaf node and/or the threshold for decrease in mse from in the split.