  We present a new universal source code for unlabeled binary and ordinal trees
that achieves asymptotically optimal compression for all tree sources covered
by existing universal codes. At the same time, it supports answering many
navigational queries on the compressed representation in constant time on the
word-RAM; this is not known to be possible for any existing tree compression
method. The resulting data structures, "hypersuccinct trees", hence combine the
compression achieved by the best known universal codes with the operation
support of the best succinct tree data structures. Compared to prior work on
succinct data structures, we do not have to tailor our data structure to
specific applications; hypersuccinct trees automatically adapt to the trees at
hand. We show that it simultaneously achieves the asymptotically optimal space
usage for a wide range of distributions over tree shapes, including: random
binary search trees (BSTs) / Cartesian trees of random arrays, random
fringe-balanced BSTs, binary trees with a given number of binary/unary/leaf
nodes, random binary tries generated from memoryless sources, full binary
trees, unary paths, as well as uniformly chosen weight-balanced BSTs, AVL
trees, and left-leaning red-black trees. Using hypersuccinct trees, we further
obtain the first data structure that answers range-minimum queries on a random
permutation of $n$ elements in constant time and using the optimal $1.736n +
o(n)$ bits on average, solving an open problem of Davoodi et al. (2014) and
Golin et al. (2016).
