Optimal prefix code: full binary tree existence
You can formulate this proof in completely constructive terms. Starting with any prefix code, consider any node $v$ which has exactly one child $w$, and contract the edge $(v,w)$. Repeat this as long as no node has exactly one child. Since each operation decreases the number of nodes, we know that after finitely many iterations we reach a full binary tree.