If we grow a classification tree with $n$ samples and a $p$-dimensional predictor variable, what is the minimal depth of a decision tree if it grows to full size?
There is an answer saying that
The maximal number of observations at each depth $d$ of the tree falls like $n/2^{d-1}$, so the minimal depth is $\lceil\log_2n+1\rceil$.
I don't understand. Are this suggesting at each depth we classify roughly half the observations, and the to next level with the other half?
The minimal depth of a binary decision tree is the shortest distance from root node to any leaf nodes. Starting from the root node (d=1), where you have all n samples within a single node, the best strategy to build a tree with minimal depth is to divide the samples in two equal (or nearly equal if odd) parts at any level/bifurcation (clearly any other type of ripartition shortens one way but prolongs the other, thus increasing the overall depth). Thus, we have n/2 samples for d=2, n/4 samples for d=3, and so on. Therefore, we will reach the leaves after $\lceil \log_2 n \rceil$ bifurcations. To obtain the minimal depth, we simply have to add 1 to this number (because we have to count the root node).
