How to know if a code is Huffman or not without having the probability of each codeword?

Question

I am new to Huffman coding and I find myself facing a lot of confusion as to how to determine if a code is Huffman or not without having the probabilities associated to each codeword. I know one way is look at whether or not the code is prefix. If not, then it's not a Huffman code. If yes, then we need to check if it gives the shortest possible length, but we don't know the probabilities. How do we ensure the code guarantees the shortest possible length in such case? To illustrate my question, let us look at the following two examples:

Example 1: $\{00,01,10,110\}$

The code is a prefix code, but is the length minimal? I mean it's a bit unusual for me to see Huffman code for $4$ symbols that does not have one-bit codeword for one of its symbol (the symbol with highest probability), but them I thought maybe the first three symbols are equally probable. As such, I tried to find the Huffman code for $\{0.33,0.33,0.33,0.01\}$ and got $\{00,01,10,11\}$ with different orders (depending on the usage of $0,1$ or $1,0$ in the tree). This led me to thinking that the code under investigation might not be Huffman, yet I am still not sure.

Example 2: $\{01, 10\}$

Again another unusual prefix code as the obvious choice (and the one with minimal length) for two symbols would be $\{0, 1\}$. But could it be the case that $\{01, 10\}$ can possibly give a minimal length? I can not see any possible probabilities in which this is the case, thus I believe this is not a Huffman code.

Am I on the right track? Does there exist an actual method to check whether or nor a code is Huffman without having the probabilities?

Answer 1

If you have a Huffman code, and the codes have lengths $l_i$, then the sum over $2^{-l_i}$ must be equal to 1. In your case, that sum is 1/4 + 1/4 + 1/4 + 1/8 = 7/8 < 1, therefore not a Huffman code. You can replace the code 110 with 11.

(I am quite sure you can prove that for any prefix code, the sum is ≤ 1. And I'm quite sure you can prove that if the sum is less than 1, then there is some bit that you can remove from some code with the code remaining a prefix code, and since there is a finite number of bits to remove, the sum must become 1 eventually).

Answer 2

When a frequency tree is built for a message upon its characters, the leaf nodes of the tree are the characters composing the message with their frequency and internal nodes just have a frequency sum of all its descendents.
The characteristic property of frequency trees for Huffman encoding is that, all internal nodes have exactly two children.

For your example 1, $\{00,01,10,110\}$, the frequency tree would be something like this (forgive me for how the tree looks like. Subtrees are denoted by + and the first subtree is the left subtree and the second is the right subtree):

(root)
+ (0)
|  + (0) (leaf)
|  + (1) (leaf)
+ (1)
   + (0) (leaf)
   + (1)
      + (0) (leaf)

The subtree $\{root,1,1\}$ has one child, not two. Hence, such a prefix code can not be a Huffman encoding for any message. Similarly for example two, subtrees $\{root,0\}$ and $\{root,1\}$ have exactly one child.