Lossless Spec: Is "complete binary tree" intentional?

[Jingyu Lim]

Hi,

I have a question about the WebP Lossless Bitstream Specification.

In Section 6.2.1 Decoding and Building the Prefix Codes [^1], the spec says:

> The described tree must be a complete binary tree.

I think "the described tree" here refers to the prefix code tree (built from the code lengths).

However, as far as I know, a prefix code tree usually can't be "complete" in the computer science sense (every level filled, except maybe the last one, filled from left to right). Leaf depths depend on symbol frequencies, so the tree shape is normally irregular. Also, if the tree were actually complete, all leaves would have nearly the same depth, meaning nearly all symbols would get nearly the same code length. This would defeat the purpose of using a prefix code tree in the first place, since the whole point is to give shorter codes to more frequent symbols.

So being a complete binary tree doesn't seem like a useful requirement here. Should it instead say "full binary tree" (every internal node has exactly 2 children)? Or is "complete" intentional, and used with a different meaning?

Thank you.

[^1]: https://developers.google.com/speed/webp/docs/webp_lossless_bitstream_specification#621_decoding_and_building_the_prefix_codes