# VC-dimension of the class of decision trees

I need to show that the VC-dimension of the class of decision trees over the domain $${0,1}^d$$ is $$2^d$$

I tried to show that any binary classi er can be implemented as a decision tree of height at most $$d + 1$$.

Can you help?

Let $$h$$ be any binary classifier. i.e, for any input $$x= {0,1}^d$$, it return 0 or 1.

Let the general decision tree, in which on the d+1 height, there are leaves that represent the value of the input.

Each input $$x$$ can be uniquely expressed as a path in this decision tree. For any $$h$$, we can express its output on the domain as a set of leaves, while any leaf is a unique identifier of an input. We can manually take each input, and assign its leaf the output of the binary classifier $$h$$.

Now, on any input, walking on the decision tree will result the output of $$h$$. Therefore, any binary classifier can be implemented as a decision tree of height at most $$d+1$$.

The output vector of the tree hypothesis is represented by a vector of leafs of size of $$2^d$$. The leafs can be assigned accordingly to any hypothesis, inducing $$2$$ in power of $$2^d$$ implementations by the class of decision trees.

Therefore, any sample S of size $$2^d$$ from the domain $${0,1}^d$$ can be shattered by this tree.

This conclude that the VC-Dimension of the class of decision trees over the space of $${0,1}^d$$ is $$2^d$$.