  We prove that for every parity decision tree of depth $d$ on $n$ variables,
the sum of absolute values of Fourier coefficients at level $\ell$ is at most
$d^{\ell/2} \cdot O(\ell \cdot \log(n))^\ell$. Our result is nearly tight for
small values of $\ell$ and extends a previous Fourier bound for standard
decision trees by Sherstov, Storozhenko, and Wu (STOC, 2021).
  As an application of our Fourier bounds, using the results of Bansal and
Sinha (STOC, 2021), we show that the $k$-fold Forrelation problem has
(randomized) parity decision tree complexity
$\tilde{\Omega}\left(n^{1-1/k}\right)$, while having quantum query complexity
$\lceil k/2\rceil$.
  Our proof follows a random-walk approach, analyzing the contribution of a
random path in the decision tree to the level-$\ell$ Fourier expression. To
carry the argument, we apply a careful cleanup procedure to the parity decision
tree, ensuring that the value of the random walk is bounded with high
probability. We observe that step sizes for the level-$\ell$ walks can be
computed by the intermediate values of level $\le \ell-1$ walks, which calls
for an inductive argument. Our approach differs from previous proofs of Tal
(FOCS, 2020) and Sherstov, Storozhenko, and Wu (STOC, 2021) that relied on
decompositions of the tree. In particular, for the special case of standard
decision trees we view our proof as slightly simpler and more intuitive.
  In addition, we prove a similar bound for noisy decision trees of cost at
most $d$ -- a model that was recently introduced by Ben-David and Blais (FOCS,
2020).
