Kraft's inequality

Let and
A Prefix-Free Code
with word lengths exists
if and only if

Proof

Consider an tree
where each node has descendants labelled by the elements of .
Each codeword corresponds to a node,
the path from the root to this node spelling out the codeword.

Assuming is prefix-free,
no codeword is the ancestor of any other.
Now view the tree as a pipe network
with water being pumped in at constant rate
and dividing the flow equally at each node.
If a node is the end of a codeword,
then this node is a sink and we extract available water from it.
The total amount of water we extract at the codewords is ,
which is therefore .