  In this paper we propose and study a version of the Dyadic Classification and
Regression Trees (DCART) estimator from Donoho (1997) for (fixed design)
quantile regression in general dimensions. We refer to this proposed estimator
as the QDCART estimator. Just like the mean regression version, we show that a)
a fast dynamic programming based algorithm with computational complexity $O(N
\log N)$ exists for computing the QDCART estimator and b) an oracle risk bound
(trading off squared error and a complexity parameter of the true signal) holds
for the QDCART estimator. This oracle risk bound then allows us to demonstrate
that the QDCART estimator enjoys adaptively rate optimal estimation guarantees
for piecewise constant and bounded variation function classes. In contrast to
existing results for the DCART estimator which requires subgaussianity of the
error distribution, for our estimation guarantees to hold we do not need any
restrictive tail decay assumptions on the error distribution. For instance, our
results hold even when the error distribution has no first moment such as the
Cauchy distribution. Apart from the Dyadic CART method, we also consider other
variant methods such as the Optimal Regression Tree (ORT) estimator introduced
in Chatterjee and Goswami (2019). In particular, we also extend the ORT
estimator to the quantile setting and establish that it enjoys analogous
guarantees. Thus, this paper extends the scope of these globally optimal
regression tree based methodologies to be applicable for heavy tailed data. We
then perform extensive numerical experiments on both simulated and real data
which illustrate the usefulness of the proposed methods.
