Proof of the Converse of Kraft's Theorem

Question

So I have already proven Kraft's theorem for ternary trees, and I have been tasked with proving the converse. That is, I need to show that there is a ternary tree with $k$ leaves, such that leaf $i$ is a distance $l_i$ from the root. It is given that: $$ \sum\limits_{i=1}^{k} 3^{-l_i} \leq 1\ $$

I'm not positive where to start with this proof. I understand that each leaf has a probability of $3^{-l_i}$ of being chosen, but every proof I attempt is simply proving Kraft's theorem again.

Edit: I was also thinking that it may have something to do with finding a bijection? But I'm not sure if that's the wrong route.

Answer 1

Assume that $\ell_1\le\ldots\le\ell_k$. Start with the full ternary tree $T$ of depth $\ell_k$. Pick a node $v_1$ at depth $\ell_1$ and remove its descendants; $v_1$ will be the leaf at depth $\ell_1$. Its descendants together with $v_1$ itself form a full ternary tree of depth $\ell_k-\ell_1$, so the pruned tree $T_1$ contains a fraction $$3^{-\big(\ell_k-(\ell_k-\ell_1)\big)}=3^{-\ell_1}$$ of the vertices of $T$; those vertices are no longer available as possible choices for the next leaf.

See if you can finish it from there; I’ve sketched the rest in the spoiler-protected paragraph below.

Now let $v_2$ be any node of $T_1$ (other than $v_1$) at depth $\ell_2$. Prune the descendants of $v_2$ to yield a subtree $T_2$; these descendants, together with $v_2$, amount to a fraction $3^{-\ell_2}$ of the nodes of the full tree $T$. Continue until you have $T_k$. Your hypothesis ensures that you don’t run out of nodes before that stage. Do a final pruning of any unwanted rubbish.