What is the VC dimension of a decision tree with k splits in two dimensions? Let us say the model is CART and the only allowed splits are parallel to the axes.
So for one split we can order 3 points in a triangle and then for any labeling of the points we could get perfect prediction (i.e.: shattered points)
But what about 2 splits, or any general k?
I'm not sure this is a question with a simple answer, nor do I believe it is a question that even needs to be asked about decision trees.
Consult Aslan et al., Calculating the VC-Dimension of Trees (2009). They address this problem by doing an exhaustive search, in small trees, and then providing an approximate, recursive formula for estimating the VC dimension on larger trees. They then use this formula as part of a pruning algorithm. Had there been a closed-form answer to your question, I am sure they would have supplied it. They felt the need to iterate their way through even fairly small trees.
My two cents worth. I'm not sure that it's meaningful to talk about the VC dimension for decision tres. Consider a $d$ dimensional response, where each item is a binary outcome. This is the situation considered by Aslan et al. There are $2^d$ possible outcomes in this sample space and $2^d$ possible response patterns. If I build a complete tree, with $d$ levels and $2^d$ leaves, then I can shatter any pattern of $2^d$ responses. But nobody fits complete trees. Typically, you overfit and then prune back using cross-validation. What you get at the end is a smaller and simpler tree, but your hypothesis set is still large. Aslan et al. try to estimate the VC dimension of families of isomorphic trees. Each family is a hypothesis set with its own VC dimension.
The previous picture illustrates a tree for a space with $d=3$ that shatters 4 points: $(1,0,0,1),(1,1,1,0),(0,1,0,1), (1,1,0,1)$. The fourth entry is the "response". Aslan et al. would regard a tree with the same shape, but using $x1$ and $x2$, say, to be isomorphic and part of the same hypothesis set. So, although there are only 3 leaves on each of these trees, the set of such trees can shatter 4 points and the VC dimension is 4 in this case. However, the same tree could occur in a space with 4 variables, in which case the VC dimension would be 5. So it's complicated.
Aslan's brute force solution seems to work fairly well, but what they get isn't really the VC dimension of the algorithms people use, since these rely on pruning and cross-validation. It's hard to say what the hypothesis space actually is, since in principle, we start with a shattering number of possible trees, but then prune back to something more reasonable. Even if someone begins with an a priori choice not to go beyond two layers, say, there may still be a need to prune the tree. And we don't really need the VC dimension, since cross-validation goes after the out of sample error directly.
To be fair to Aslan et al., they don't use the VC dimension to characterize their hypothesis space. They calculate the VC dimension of branches and use that quantity to determine if the branch should be cut. At each stage, they use the VC dimension of the specific configuration of the branch under consideration. They don't look at the VC dimension of the problem as a whole.
If your variables are continuous and the response depends on reaching a threshold, then a decision tree is basically creating a bunch of perceptrons, so the VC dimension would presumably be greater than that (since you have to estimate the cutoff point to make the split). If the response depends monotonically on a continuous response, CART will chop it up into a bunch of steps, trying to recreate a regression model. I would not use trees in that case -- possibly gam or regression.
I know this post is kind of old and already has an accepted answered, but as it is the first to link appear on Google when asking about the VC dimension of decision trees, I will allow myself to give some new information as a follow up.
In a recent paper, Decision trees as partitioning machines to characterize their generalization properties by Jean-Samuel Leboeuf, Frédéric LeBlanc and Mario Marchand, the authors consider the VC dimension of decision trees on examples of $\ell$ features (which is a generalization of your question which concerns only 2 dimensions). There, they show that the VC dimension of the class of a single split (AKA decision stumps) is given by the largest integer $d$ which satisfies $2\ell \ge \binom{d}{\left\lfloor\frac{d}{2}\right\rfloor}$. The proof is quite complex and proceeds by reformulating the problem as a matching problem on graphs.
Furthermore, while an exact expression is still out of reach, they are able to give an upper bound on the growth function of general decision trees in a recursive fashion, from which they show that the VC dimension is of order $\mathcal{O}(L_T \log (\ell L_T))$, with $L_T$ the number of leaves of the tree. They also develop a new pruning algorithm based on their results, which seems to perform better in practice than CART's cost complexity pruning algorithm without the need for cross-validation, showing that the VC dimension of decision trees can be useful.
Disclaimer: I am one of the author of the paper.
