Evasive Boolean function ($D(f)=n$)

A Boolean function is evasive when every deterministic decision tree computing it has a worst-case path that queries all input bits. The alternating-sum criterion for decision-tree evasiveness is one sufficient method for proving this lower bound.

A leaf reached before all $n$ input bits are queried leaves at least one coordinate free. Flipping that coordinate pairs its inputs with opposite alternating signs and equal output. Thus every such leaf contributes zero. If the total alternating sum is nonzero, a depth below $n$ is impossible.