  We explore the $\textit{average-case deterministic query complexity}$ of
boolean functions under a $\textit{uniform distribution}$, denoted by
$\mathrm{D}_\mathrm{ave}(f)$, the minimum average depth of zero-error decision
tree computing a boolean function $f$. This measure has found several
applications across diverse fields, yet its understanding is limited. We study
$\mathrm{D}_\mathrm{ave}(f)$ of several functions, including the penalty
shoot-out function, symmetric functions, linear threshold functions and the
tribes functions. We prove $\mathrm{D}_\mathrm{ave}(f) \le \max \{ \log
\frac{\mathrm{wt}(f)}{\log n} + O(\log \log \frac{\mathrm{wt}(f)}{\log n}),
O(1) \}$ for every $n$-variable boolean function $f$, where $\mathrm{wt}(f)$
denotes the weight (the number of inputs on which $f$ outputs $1$). For any
$4\log n \le m(n) \le 2^{n-1}$, we prove the upper bound is tight up to an
additive logarithmic term for almost all $n$-variable boolean functions with
weight $\mathrm{wt}(f) = m(n)$. Using H\r{a}stad's switching lemma or Rossman's
switching lemma [Comput. Complexity Conf. 137, 2019], one can derive
$\mathrm{D}_\mathrm{ave}(f) \leq n(1 - \frac{1}{O(w)})$ or
$\mathrm{D}_\mathrm{ave}(f) \le n(1 - \frac{1}{O(\log s)})$ for CNF/DNF
formulas of width $w$ or size $s$, respectively. We show that, for any $w \ge
\log n + \log \log n + 3$, there exists a DNF formula of width $w$ and size
$\lceil 2^w / w \rceil$ such that $\mathrm{D}_\mathrm{ave}(f) = n (1 -
\frac{\log n}{\Theta(w)})$. In other words, we show the criticality upper
bounds $O(w)$ and $O(\log s)$ are tight up to a multiplicative $\log n$ factor,
providing evidence on the tightness of the switching lemmas.
