 Decision-tree query cost

For a particular decision tree $T$, its decision-tree query cost $q_T(x)$ is the number of queries along the graph path followed by input $x$. Its actual tree depth isThe query vertices count as operations; each is followed by one answer edge. Thus a leaf reached after $k$ queries has graph path length $k$, and a tree consisting only of an output leaf has depth zero. With no repeated coordinates, $0\le q_T(x)\le n$. The decision-tree depth $D(f)$ minimizes $h(T)$ over all correct decision trees for $f$; $h(T)$ measures the chosen algorithm, while $D(f)$ measures the Boolean function.

Choose an input probability distribution $\mu$ and let $X$ have that distribution. Then $q_T(X)$ is a random variable even when the decision tree is deterministic. Its probability mass function describes how often each path length occurs, and its expected value is the expected query cost. None of these quantities changes the actual maximum depth of $T$.

The left panel aggregates the eight inputs from the three-bit majority decision tree: four cost two queries and four cost three. Parity always costs three. The right panel asks a different question, which coordinates are inspected: the majority function algorithm always queries coordinates 1 and 2, but queries coordinate 3 only on disagreements. These are probabilities of inspection, not probabilities that a bit equals one.