Huffman coding is a prefix code, proof How would you prove that Huffman coding $C$ is a prefix code, i.e $$\forall x,y \in C,\  \forall z \in \lbrace 0,1\rbrace^*,\ x\not=y||z$$

Using induction according to the number of items to code? The base step would be easy, but I don't know how to prove the inductive step.
Let $T$ be an optimum prefix code tree, and let $b$ and $c$ be two siblings at the maximum depth of the tree (must exist because $T$ is full). Assume without loss of generality that $f (b) \le f(c)$ and $f(x) \le f(y)$ (if this is not true, then rename these characters). Since $x$ and $y$ have the two smallest frequencies it follows that $f(x) \le f(b)$ (they may be equal) and $f(y) \le f(c)$ (may be equal). Because $b$ and $c$ are at the deepest level of the tree we know that $d(b) \ge d(x)$ and $d(c) \ge d(y)$.
Now switch the positions of $x$ and $b$ in the tree resulting in a different tree $T′$ and see how the cost changes. Since $T$ is optimum,

$$\begin{align}
B(T) &amp;\le B(T′) \\
&amp;= B(T) − f(x)d(x) − f(b)d(b) + f(x)d(b) + f(b)d(x) \\
&amp;= B(T) − (f(b) − f(x))(d(b) − d(x)) \\
&amp;\le B(T)
\end{align}$$

Therefore, $B(T′) = B(T)$, that is, $T′$ is an optimum tree. By switching $y$ with $c$ we get a new tree $T ′′$ which by a similar argument is optimum. The final tree $T′′$ satisfies the statement of the claim.