<p>The discussion in the linked FGGSV paper is about binary trees with <em>no unary nodes</em>. It is easy to encode such trees with <span class="math-container">$n$</span> nodes by <span class="math-container">$n$</span>-bit strings: write the tree in preorder, indicating for each node whether it has <span class="math-container">$0$</span> or <span class="math-container">$2$</span> children using <span class="math-container">$1$</span> bit. (In other words, if you think of such trees as terms/formulas in a language with one binary and one nullary symbol, just write it in prefix (Polish) notation.)</p>
<p>More precisely, the number of such trees is the Catalan number <span class="math-container">$C_{(n-1)/2}=\frac1n\binom n{(n-1)/2}=\Theta(2^nn^{-3/2})$</span> (NB: <span class="math-container">$n$</span> must be odd), hence the optimal number of bits they can be encoded with, not necessarily efficiently, is <span class="math-container">$n-\frac32\log n+O(1)$</span>.</p>
<p>For binary trees that may possibly include unary nodes, there are <span class="math-container">$4$</span> possibilities for each node depending on which of its two children is occupied, hence the preorder description takes <span class="math-container">$2n$</span> bits, and one can check the number of such trees is <span class="math-container">$C_n$</span>, thus the information-theoretic optimal encoding needs <span class="math-container">$2n-\frac32\log n+O(1)$</span> bits.</p>

CC BY-SA 4.0
2024-06-11T08:12:44.600Z
2024-06-11T09:47:11.320Z
2024-06-11T09:47:11.320Z
Emil Jeřábek
<p>By binary <a href="https://en.wikipedia.org/wiki/Cardinal_tree" rel="nofollow noreferrer">cardinal tree</a>, I mean a tree with degree 2.</p>
<p>The question confuses me because I know LOUDS/DFUDS can encode binary trees with 2n bits; however, <a href="https://www.ittc.ku.edu/%7Ejsv/Papers/FGG08.SearchingCompressed.pdf" rel="nofollow noreferrer">this paper</a> claims that it is possible to encode with only n bits.</p>
<p>The paper was published on PODS 2008 and provides solid inferences around the confusing point.
Thus, I could have missed some more succinct approach.</p>
<p>The related context is in Section 3, at the bottom right on Page 3 of the aforementioned paper.</p>
<p>I appreciate any advice or suggestions.</p>

CC BY-SA 4.0
2024-06-11T07:39:30.070Z
It’s not clear to me what exactly you are referencing, as the paragraph at bottom right on p. 3 discusses a *lower bound*, not *upper bound*, on the number of some kind of trees. However, the whole discussion there is about binary trees with *no unary nodes*. Such trees with $n$ nodes can be indeed encoded by $n$-bit strings in a straightforward way (write the tree in preorder, indicating for each node the 1-bit information whether it has 0 or 2 children).
Emil Jeřábek
CC BY-SA 4.0
2024-06-11T07:49:56.343Z
@EmilJeřábek Oh thank you! I see the problem is I missed 'no unary nodes.' Would you mind posting the comment as an answer, or shall I close this question?
Xavier Z
<ds.data-structures><it.information-theory><tree>
Is it possible to encode the structure of a binary cardinal tree with n nodes using only n bits?
Xavier Z
# Is it possible to encode the structure of a binary cardinal tree with n nodes using only n bits?

(Asked by: username_0 on 2024-06-11)

By binary [cardinal tree](https://en.wikipedia.org/wiki/Cardinal_tree), I mean a tree with degree 2.

The question confuses me because I know LOUDS/DFUDS can encode binary trees with 2n bits; however, [this paper](https://www.ittc.ku.edu/%7Ejsv/Papers/FGG08.SearchingCompressed.pdf) claims that it is possible to encode with only n bits.

The paper was published on PODS 2008 and provides solid inferences around the confusing point.
Thus, I could have missed some more succinct approach.

The related context is in Section 3, at the bottom right on Page 3 of the aforementioned paper.

I appreciate any advice or suggestions.

**Tags:** ds.data-structures, it.information-theory, tree
> **Comments:**
> **username_1**: It’s not clear to me what exactly you are referencing, as the paragraph at bottom right on p. 3 discusses a *lower bound*, not *upper bound*, on the number of some kind of trees. However, the whole discussion there is about binary trees with *no unary nodes*. Such trees with $n$ nodes can be indeed encoded by $n$-bit strings in a straightforward way (write the tree in preorder, indicating for each node the 1-bit information whether it has 0 or 2 children).  
> **username_0**: @EmilJeřábek Oh thank you! I see the problem is I missed 'no unary nodes.' Would you mind posting the comment as an answer, or shall I close this question?  

---

## 1 answers

### Answer by username_1 on 2024-06-11. Score: 3 | Accepted answer

The discussion in the linked FGGSV paper is about binary trees with *no unary nodes*. It is easy to encode such trees with $n$ nodes by $n$-bit strings: write the tree in preorder, indicating for each node whether it has $0$ or $2$ children using $1$ bit. (In other words, if you think of such trees as terms/formulas in a language with one binary and one nullary symbol, just write it in prefix (Polish) notation.)

More precisely, the number of such trees is the Catalan number $C\_{(n-1)/2}=\frac1n\binom n{(n-1)/2}=\Theta(2^nn^{-3/2})$ (NB: $n$ must be odd), hence the optimal number of bits they can be encoded with, not necessarily efficiently, is $n-\frac32\log n+O(1)$.

For binary trees that may possibly include unary nodes, there are $4$ possibilities for each node depending on which of its two children is occupied, hence the preorder description takes $2n$ bits, and one can check the number of such trees is $C\_n$, thus the information-theoretic optimal encoding needs $2n-\frac32\log n+O(1)$ bits.


---

