  Many machine learning tools for regression are based on recursive
partitioning of the covariate space into smaller regions, where the regression
function can be estimated locally. Among these, regression trees and their
ensembles have demonstrated impressive empirical performance. In this work, we
shed light on the machinery behind Bayesian variants of these methods. In
particular, we study Bayesian regression histograms, such as Bayesian dyadic
trees, in the simple regression case with just one predictor. We focus on the
reconstruction of regression surfaces that are piecewise constant, where the
number of jumps is unknown. We show that with suitably designed priors,
posterior distributions concentrate around the true step regression function at
a near-minimax rate. These results do not require the knowledge of the true
number of steps, nor the width of the true partitioning cells. Thus, Bayesian
dyadic regression trees are fully adaptive and can recover the true piecewise
regression function nearly as well as if we knew the exact number and location
of jumps. Our results constitute the first step towards understanding why
Bayesian trees and their ensembles have worked so well in practice. As an
aside, we discuss prior distributions on balanced interval partitions and how
they relate to an old problem in geometric probability. Namely, we relate the
probability of covering the circumference of a circle with random arcs whose
endpoints are confined to a grid, a new variant of the original problem.
