  We study preimages of permutations under the bubblesort operator
$\mathbf{B}$. We achieve a description of these preimages much more complete
than what is known for the more complicated sorting operators $\mathbf{S}$
(stacksort) and $\mathbf{Q}$ (queuesort). We describe explicitly the set of
preimages under $\mathbf{B}$ of any permutation $\pi$ from the left-to-right
maxima of $\pi$, showing that there are $2^{k-1}$ such preimages if $k$ is the
number of these left-to-right maxima. We further consider, for each $n$, the
tree $T_n$ recording all permutations of size $n$ in its nodes, in which an
edge from child to parent corresponds to an application of $\mathbf{B}$ (the
root being the identity permutation), and we present several properties of
these trees. In particular, for each permutation $\pi$, we show how the subtree
of $T_n$ rooted at $\pi$ is determined by the number of left-to-right maxima of
$\pi$ and the length of the longest suffix of left-to-right maxima of $\pi$.
Building on this result, we determine the number of nodes and leaves at every
height in such trees, and we recover (resp. obtain) the average height of nodes
(resp. leaves) in $T_n$.
