{title2=$D(f)$}

The <decision-tree depth> $D(f)$ of a <Boolean function> $f$ is the smallest possible maximum number of <input> coordinates queried along any root-to-leaf <graph path> of a <decision tree> computing $f$:
$$
D(f)=\min_{T\text{ computes }f}\max_{x\in\{0,1\}^n}q_T(x)=\min_{T\text{ computes }f}h(T).
$$
The actual depth $h(T)$ of a particular <decision tree> can exceed this optimum. A <constant function> admits a depth-zero tree even though an inefficient algorithm could inspect its entire <input> before returning that constant. <Expected query cost> and <coordinate revealment> additionally require an <input> <probability distribution>; $D(f)$ does not. The <three-bit majority decision tree> and three-<bit> <parity> both have optimal <decision-tree depth> three, although only the former has the two-query shortcuts described above.


 Decision-tree depth (source code)