  We observe that a standard transformation between \emph{ordinal} trees
(arbitrary rooted trees with ordered children) and binary trees leads to
interesting succinct binary tree representations. There are four symmetric
versions of these transformations. Via these transformations we get four
succinct representations of $n$-node binary trees that use $2n + n/(\log
n)^{O(1)}$ bits and support (among other operations) navigation, inorder
numbering, one of pre- or post-order numbering, subtree size and lowest common
ancestor (LCA) queries. The ability to support inorder numbering is crucial for
the well-known range-minimum query (RMQ) problem on an array $A$ of $n$ ordered
values. While this functionality, and more, is also supported in $O(1)$ time
using $2n + o(n)$ bits by Davoodi et al.'s (\emph{Phil. Trans. Royal Soc. A}
\textbf{372} (2014)) extension of a representation by Farzan and Munro
(\emph{Algorithmica} \textbf{6} (2014)), their \emph{redundancy}, or the $o(n)$
term, is much larger, and their approach may not be suitable for practical
implementations.
  One of these transformations is related to the Zaks' sequence (S.~Zaks,
\emph{Theor. Comput. Sci.} \textbf{10} (1980)) for encoding binary trees, and
we thus provide the first succinct binary tree representation based on Zaks'
sequence. Another of these transformations is equivalent to Fischer and Heun's
(\emph{SIAM J. Comput.} \textbf{40} (2011)) \minheap\ structure for this
problem. Yet another variant allows an encoding of the Cartesian tree of $A$ to
be constructed from $A$ using only $O(\sqrt{n} \log n)$ bits of working space.

Data Structures and Algorithms