multicollinearity resulting in high variance Section 8.7.1 of Elements of Statistical Learning talks about high variance in a classification tree due to high correlation between features. What is the intuition behind this? I would think that high correlation between, say two of your features, features is just like having one less feature. How would that result in overfitting / high variance?
 A: First, some definitions. Consider outcome variable, $Y$, and predictors, $X_1, \ldots, X_p$. The regression tree algorithm iteratively splits the units $i = 1, \ldots, n$ into subgroups based on predictor values. Every split creates two subgroups, called nodes, and any unsplit node is called terminal. For unit $i$ in terminal node $t$, where $N_t$ represents the set of units in $t$, the tree-predicted value for unit $i$ is $\hat{Y}_i = \frac{1}{|N_t|}\sum_{i \in N_t} Y_i$. At each iteration, the deviance for the tree $T$, dev($T$) $ = \sum_i\left(\hat{Y}_i - Y_i\right)^2$, is determined before splitting. Then, every possible split on every variable is considered, and the split that results in the largest decrease in deviance is selected. Typically smoothing is imposed via cost-complexity pruning by adding a term to the deviance that is something like $\lambda |T|$, where $|T|$ is the number of terminal nodes in $T$, and $\lambda$ is a tuning-parameter selected, for example, by cross-validation. 
Now, back to your question. What is the intuition for why trees with highly correlated predictors are more variable than trees with, say, uncorrelated predictors? This has to do with the splitting at each iteration. If two predictors, let's say $X_1$ and $X_2$ are highly correlated, then it won't make much difference in terms of reduction in deviance which one is selected. In the raw sample, it may be that $X_1$ is selected as the first split (with $X_2$ a very close second because of the high correlation). Now consider a bootstrap sample of the data. It would be easy to imagine that in the bootstrap sample the balance shifts so that the first split now favors $X_2$ instead of $X_1$, with $X_1$ a close second. These splits then have consequences for all subsequent splits made by the algorithm and end up with trees that look quite different, even if predictions are not that different. 
Whereas, if the variables were uncorrelated, it is less likely that a minor perturbation to the data will cause a major shift in the order in which variables are split upon. The caveat is that single trees are highly variable no matter the correlation structure. This is why bagging, boosting, and random forests are so useful. You can read more about those methods in ESL as well.
Just noticed you asked about classification trees and I responded in terms of regression trees. The answer is still relevant; you would need to use a different deviance function for classification though like Gini index or cross entropy.
A: In their example,they have one determining feature (x1) and each of the five features has high correlation to the others.
The correlation means that lots of different splits will work on the (small) training data (not just splitting on x1). However, they won't work on the test data.( If the features were perfectly correlated, it would not matter)
