VC dimension for balanced binary decision trees What is the VC dimension of all balanced binary decision tree of
depth $k$ in $\{0,1\}^d$? Does it depend on depth $k$ or dimension $d$?
It is shown here (slide 10) that if $H_{d,k}$ is the number of depth-$k$ decision trees over $d$ input bits, then
$$v:=\log_2(H_{d,k})=
(2^k-1)(1+\log_2(d))+1
.
$$
So $v$ is an upper bound on the VC-dimension of your class. I don't know how tight it is, since you have the additional constraint of the trees being balanced.