Decision-tree depth ($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 path of a decision tree computing $f$.

To prove that a threshold function requires every input bit in the worst case, an adversary answers queries while keeping completions on both sides of the threshold possible. If this remains true until the final unqueried bit, every decision tree has depth equal to the number of variables.