# 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$$?

• @Aryeh thx alot, How can i proof this formula ? – Rhasta Shaman Oct 17 at 8:24

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.