# Is it possible to encode the structure of a binary cardinal tree with n nodes using only n bits?

By binary 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 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.

• 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). Commented Jun 11 at 7:39
• @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? Commented Jun 11 at 7:49

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.