  The degree distribution of an ordered tree $T$ with $n$ nodes is $\vec{n} =
(n_0,\ldots,n_{n-1})$, where $n_i$ is the number of nodes in $T$ with $i$
children. Let $\mathcal{N}(\vec{n})$ be the number of trees with degree
distribution $\vec{n}$. We give a data structure that stores an ordered tree
$T$ with $n$ nodes and degree distribution $\vec{n}$ using $\log
\mathcal{N}(\vec{n})+O(n/\log^t n)$ bits for every constant $t$. The data
structure answers tree queries in constant time. This improves the current data
structures with lowest space for ordered trees: The structure of Jansson et
al.\ [JCSS 2012] that uses $\log\mathcal{N}(\vec{n})+O(n\log\log n/\log n)$
bits, and the structure of Navarro and Sadakane [TALG 2014] that uses
$2n+O(n/\log^t n)$ bits for every constant $t$.

Data Structures and Algorithms