 Decision-tree depth

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$: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.