= Solution
Let $L$ again denote the largest <codeword length>, and assume a <full-support finite distribution>. The missing-branch exchange from part iii forces every internal <vertex> at depth at most $L-2$ to have three <tree children>. At depth $L-1$, all <tree children> are <tree leaves>. Part ii rules out one <tree child> there; the hypothesis that there is no pair of two deepest <sibling codewords> rules out two <tree children>. Thus each such <tree parent> also has three <tree children>. \b[Every internal <vertex> has exactly three <tree children>], which is a <full ternary tree>, called semi-complete in this paper. The same last-level argument covers $L=1$.
Without the assumption of a <full-support finite distribution> the implication is false: for $p=(1,0,0)$, the optimal <prefix code> $(0,10,110)$ has no deepest pair of two <sibling codewords>, but its <code tree> contains <vertices> with a single <tree child>. Empty unused <tree children> are not <vertices> of the <code tree>.
Back to article page
