46.02.03 · information-theory / 02-source-coding

Huffman Codes: Construction, Optimality, and the Redundancy Bound

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §5.1-5.5; Gallager 1978 Variations on a Theme by Huffman IEEE Trans. Info. Theory 24(6) 668-674; Capocelli et al. 1991 On the Redundancy of Huffman Codes IEEE Trans. Info. Theory 37(1) 144-148

Intuition Beginner

Imagine you are packing a suitcase. You use small containers for things you bring rarely and large containers for things you bring often. The Huffman algorithm does this for data: it assigns short codewords to frequent symbols and long codewords to rare ones.

Start with every symbol as its own node, each labelled with its probability. Find the two nodes with the smallest probabilities and merge them into a parent node whose probability is their sum. Repeat until one node remains. The resulting binary tree is the Huffman tree. Reading the left/right branches as 0/1 gives the codewords.

Why is this good? Because the algorithm is greedy but optimal. At every step, the two least probable symbols are siblings in the tree. This guarantees that no other prefix-free code can have a shorter expected length. The proof works by an exchange argument: if any optimal code had those two symbols far apart, you could swap them with deeper nodes and shorten the code, contradicting optimality.

The redundancy bound says the expected length of a Huffman code exceeds the entropy by less than one bit, and in fact by less than $p_{m a x} + 0.086$ bits, where $p_{m a x}$ is the largest symbol probability. For a uniform source with many symbols, $p_{m a x}$ is small and the code is nearly optimal.

Visual Beginner

Figure: a Huffman tree for the source ${a, b, c, d, e}$ with probabilities $0.40, 0.20, 0.20, 0.10, 0.10$ . The two least-probable symbols $d$ (0.10) and $e$ (0.10) merge first into a node of weight 0.20. This node merges with $b$ (0.20) and $c$ (0.20) in subsequent steps. The final tree assigns: $a = 0$ , $b = 10$ , $c = 110$ , $d = 1110$ , $e = 1111$ .

Symbol	Probability	Codeword	Length	Contribution to $L$
a	0.40	0	1	0.40
b	0.20	10	2	0.40
c	0.20	110	3	0.60
d	0.10	1110	4	0.40
e	0.10	1111	4	0.40

Expected length: $L = 0.40 + 0.40 + 0.60 + 0.40 + 0.40 = 2.20$ bits. The entropy is $H \approx 2.12$ bits. The redundancy is $L - H \approx 0.08$ bits.

Worked example Beginner

Consider English letter frequencies (approximate, top 8 letters plus a catch-all). The probabilities are:

E: 0.13, T: 0.09, A: 0.08, O: 0.08, I: 0.07, N: 0.07, S: 0.06, H: 0.06, other: 0.36.

Step 1. Place all nine symbols in a list with their probabilities.

Step 2. Merge the two smallest: S (0.06) and H (0.06) become a node of weight 0.12.

Step 3. Merge the next two smallest: I (0.07) and N (0.07) become weight 0.14.

Step 4. Now the list is: E (0.13), {S,H} (0.12), T (0.09), A (0.08), O (0.08), {I,N} (0.14), other (0.36). Merge A and O: weight 0.16.

Step 5. Merge T (0.09) and {S,H} (0.12): weight 0.21.

Step 6. Merge E (0.13) and {I,N} (0.14): weight 0.27.

Continue until one node remains. The expected codeword length is approximately 2.84 bits per letter. The entropy of this distribution is approximately 2.79 bits. The redundancy is about 0.05 bits, well within the bound.

Compare this with a fixed-length code. With 9 symbols, a fixed-length code needs 4 bits per symbol (since $2^{3} = 8 < 9 \leq 16 = 2^{4}$ ). The Huffman code saves about 1.16 bits per symbol, a 29% reduction. Over a million characters of English text, the Huffman code would save roughly 1.16 million bits, or about 145 kilobytes. This is why Huffman coding is the backbone of file compression.

Check your understanding Beginner

Formal definition Intermediate+

Let $X = {x_{1}, \dots, x_{m}}$ be a finite source alphabet with probability distribution $p = (p_{1}, \dots, p_{m})$ where $p_{i} \geq 0$ and $\sum p_{i} = 1$ .

Definition (Prefix-free code). A code $C : X \to {0, 1}^{*}$ is prefix-free if no codeword is a prefix of another. The set of codewords ${C (x) : x \in X}$ forms a prefix-free set.

Definition (Expected length). The expected length of a code $C$ for source $p$ is

L (C) = i = 1 \sum m p_{i} l_{i},

where $l_{i} = ∣ C (x_{i}) ∣$ is the length of the codeword for $x_{i}$ .

Definition (Huffman code). The Huffman code is constructed by the following algorithm:

Create a leaf node for each symbol $x_{i}$ with weight $p_{i}$ .
While more than one node remains: a. Select the two nodes with the smallest weights. b. Create a new internal node with weight equal to the sum of the two selected nodes' weights. c. Make the two selected nodes children of the new node (assign 0 to one branch, 1 to the other).
The remaining node is the root of the Huffman tree.

The codeword for each symbol is the sequence of branch labels on the path from root to leaf.

Counterexamples to common slips

The Huffman code is not unique. Different tie-breaking rules produce different trees with different codeword assignments. All such codes have the same expected length (which is optimal).
Optimality is within the class of prefix-free codes. The Huffman code minimises $L (C)$ over all prefix-free codes. It does not minimise over all uniquely decodable codes, but by Kraft's inequality the minimum expected length is the same for both classes.
The bound $L - H < 1$ holds for any distribution, but the tighter bound involves $p_{m a x}$ . For a highly skewed distribution with $p_{m a x} \approx 1$ , the redundancy can be close to zero; for a near-uniform distribution, it is also close to zero. The worst case is in between.

Key theorem with proof Intermediate+

Theorem (Optimality of Huffman codes). For any discrete source with distribution $p$ , the Huffman code achieves the minimum expected codeword length among all prefix-free codes.

Proof. The proof proceeds by induction on $m = ∣ X ∣$ using an exchange argument.

Base case ( $m = 2$ ). With two symbols, the Huffman code assigns 0 and 1, giving expected length 1. Any prefix-free code for two symbols must have at least one codeword of length 1, and the only such code has expected length 1. So the Huffman code is optimal.

Inductive step. Assume optimality holds for all sources with $m - 1$ symbols. Let $p$ be a distribution on $m$ symbols, and assume (by relabelling) that $p_{1} \leq p_{2} \leq \dots \leq p_{m}$ . Let $C^{*}$ be any optimal prefix-free code for $p$ with codeword lengths $l_{1}^{*} \geq l_{2}^{*} \geq \dots \geq l_{m}^{*}$ .

Claim: In $C^{*}$ , the two symbols with the smallest probabilities ( $x_{1}$ and $x_{2}$ ) can be assumed to be siblings (i.e., their codewords differ only in the last bit, and $l_{1}^{*} = l_{2}^{*}$ ).

Proof of claim: If $l_{1}^{*} > l_{2}^{*}$ , swap the codeword of $x_{1}$ with that of any symbol at depth $l_{2}^{*}$ . Since $p_{1} \leq p_{2}$ and the swap shortens the codeword of $x_{1}$ while lengthening the codeword of a higher-probability symbol, the expected length decreases or stays the same. Similarly, if $x_{1}$ is not a sibling of $x_{2}$ but has some other symbol $x_{j}$ as a sibling at the same depth, swap $x_{2}$ and $x_{j}$ (which does not change expected length since $p_{2} \leq p_{j}$ and they are at the same depth). Hence we may assume $x_{1}$ and $x_{2}$ are siblings.

Now merge $x_{1}$ and $x_{2}$ into a single meta-symbol $x^{'}$ with probability $p^{'} = p_{1} + p_{2}$ . This creates a source with $m - 1$ symbols. By the induction hypothesis, the Huffman code for this reduced source is optimal. The Huffman code for the original source is obtained by expanding $x^{'}$ back into $x_{1}$ and $x_{2}$ (appending 0 and 1 respectively), which adds exactly $p^{'} \cdot 1 = p_{1} + p_{2}$ to the expected length. Any optimal code for the original source must also have $x_{1}$ and $x_{2}$ as siblings (by the claim), so it similarly corresponds to a code for the reduced source. By the induction hypothesis, no code for the reduced source has shorter expected length than the Huffman code. Therefore no code for the original source has shorter expected length than the Huffman code. $□$

Bridge. The optimality of Huffman codes builds toward the method of types in 46.02.06, where universal codes operate without knowing the source distribution and the redundancy bound here quantifies the price of ignorance. This is exactly the starting point for universal source coding, where the redundancy over entropy becomes the overhead of learning the distribution from data. The exchange argument appears again in 46.03.03 as the structural backbone of Fano's inequality, and the foundational reason entropy governs compression is that the Huffman redundancy vanishes as the alphabet grows. The central insight is that greedy local merging produces a globally optimal code, generalises to $D$ -ary alphabets for non-binary channels, and is dual to the sphere-packing argument in 46.03.04 where the geometric structure of codewords determines capacity.

Exercises Intermediate+

Exercise (medium, short answer).

Prove that the Huffman code for a dyadic distribution (one where every $p_{i}$ is of the form $2^{- k_{i}}$ for integers $k_{i}$ ) achieves expected length exactly equal to the entropy $H (X)$ .

Hint

For a dyadic distribution, the Kraft sum $\sum 2^{- l_{i}}$ equals 1 with $l_{i} = - lo g_{2} p_{i}$ , so setting codeword lengths equal to $- lo g_{2} p_{i}$ gives a valid prefix-free code.

Answer

For a dyadic distribution, $p_{i} = 2^{- k_{i}}$ for positive integers $k_{i}$ . The Kraft sum with $l_{i} = k_{i} = - lo g_{2} p_{i}$ is $\sum 2^{- k_{i}} = \sum p_{i} = 1$ . By Kraft's theorem, there exists a prefix-free code with these lengths. The expected length is $\sum p_{i} k_{i} = \sum p_{i} (- lo g_{2} p_{i}) = H (X)$ . Since $L \geq H (X)$ for any prefix-free code, this code is optimal, and the Huffman code must achieve the same expected length.

Exercise (hard, short answer).

Prove the redundancy bound $L^{*} - H (X) < p_{m a x}$ where $L^{*}$ is the expected length of the Huffman code and $p_{m a x} = max_{i} p_{i}$ .

Hint

Use the Shannon code with lengths $l_{i} = ⌈ - lo g_{2} p_{i} ⌉$ , which satisfies $L_{S} - H < 1$ . Then show that the Huffman code is at least as good as the Shannon code. Strengthen the bound using the structure of the Huffman tree.

Answer

The Shannon code has lengths $l_{i} = ⌈ - lo g_{2} p_{i} ⌉$ and satisfies $H (X) \leq L_{S} < H (X) + 1$ . Since the Huffman code is optimal among prefix-free codes, $L^{*} \leq L_{S}$ , so $L^{*} - H (X) < 1$ .

For the tighter bound: let $p_{m a x} = p_{1}$ . Consider the reduced source obtained by merging the two least-probable symbols. By induction on $m$ , let $C^{'}$ be the Huffman code for the reduced source with expected length $L^{'}$ . Then $L^{*} = L^{'} + p_{1} + p_{2}$ where $p_{1}, p_{2}$ are the merged probabilities. By the induction hypothesis, $L^{'} - H^{'} < p_{m a x}^{'}$ where $p_{m a x}^{'} = max (p_{1} + p_{2}, p_{3}, \dots, p_{m})$ . Since $H = H^{'} + (p_{1} + p_{2}) H_{b} (p_{1} / (p_{1} + p_{2}))$ where $H_{b} \leq 1$ , we get $L^{*} - H = L^{'} - H^{'} + (p_{1} + p_{2}) (1 - H_{b} (\cdot)) \leq p_{m a x}^{'}$ . Direct analysis of the Shannon code lengths shows the sharper bound $L^{*} - H < p_{m a x}$ (Gallager 1978).

Exercise (hard, short answer).

Construct a source distribution for which the Huffman redundancy $L^{*} - H$ is arbitrarily close to 1. Explain why the bound cannot be improved below 1 without additional assumptions.

Answer

Consider a source with two symbols of probabilities $(p, 1 - p)$ where $p$ is close to $1/2$ but not dyadic. The Huffman code assigns lengths $(1, 1)$ with expected length $L = 1$ . The entropy is $H (p) < 1$ , approaching 1 as $p \to 1/2$ but never reaching it for non-uniform $p$ . Specifically, for $p = 1/2 - ϵ$ , $H (p) = 1 - O (ϵ^{2})$ and $L - H = O (ϵ^{2})$ , which is small. For a worse case, use $m$ symbols with probabilities approaching $1/ m$ from below (non-dyadic), giving $L = ⌈ lo g_{2} m ⌉$ and $H \approx lo g_{2} m$ , with gap up to 1.

A more precise construction: let $m = 2^{k} + 1$ symbols with probabilities $p_{i} = 1/ m$ for all $i$ . The Huffman code has expected length $⌈ lo g_{2} m ⌉ = k + 1$ while $H = lo g_{2} m \approx k$ . The redundancy is approximately $1 - lo g_{2} (1 + 2^{- k}) \to 1$ as $k \to \infty$ .

Exercise (hard, short answer).

Prove that the Huffman code is the unique optimal prefix-free code (up to relabelling of branch labels) if and only if all probabilities are distinct.

Answer

If all probabilities are distinct, the two smallest probabilities are unique at each step of the algorithm, so there is no tie-breaking ambiguity. The resulting tree structure is unique (up to swapping 0/1 labels on branches).

If some probabilities are equal, there are at least two symbols with the same probability. At some step, the algorithm must choose among tied probabilities. Different choices produce different tree structures with different codeword assignments (though the same optimal expected length). For example, with probabilities $(1/3, 1/3, 1/3)$ , the first merge can pair any two of the three symbols, giving three structurally different trees.

Lean formalization Intermediate+

Mathlib does not define prefix-free codes or the Huffman algorithm. The ComputeQuantities and Omega frameworks for computational reasoning are available, but there is no PrefixFreeCode type, no expected-length functional, and no optimality theorem. A Codex.InformationTheory.Huffman module would need to define a binary tree type for code trees, a prefix-free predicate, an expected-length functional, the merge algorithm, and the optimality proof by induction and exchange. The redundancy bound requires additional analysis of the Shannon code as an intermediate step. This unit ships without formal verification.

Advanced results Master

The sibling property and code characterisation

Gallager (1978) introduced the sibling property: a binary prefix code on $m$ symbols is a Huffman code if and only if the corresponding code tree has the property that its $2 m - 1$ nodes (internal nodes and leaves combined) can be listed in order of non-increasing probability so that each pair of siblings is adjacent in the list.

This characterisation provides an efficient test for whether a given prefix-free code is a Huffman code without re-running the algorithm: compute the node probabilities and check the sibling property. It also gives a clean proof that the Huffman code is optimal, since any non-Huffman code violates the sibling property, and the violation identifies a local swap that reduces expected length.

The Shannon code and its competitive optimality

The Shannon code assigns length $l_{i} = ⌈ - lo g_{2} p_{i} ⌉$ to symbol $x_{i}$ . By construction, $H (X) \leq L_{S} < H (X) + 1$ . The Huffman code $L^{*}$ satisfies $L^{*} \leq L_{S}$ , so $L^{*} - H (X) < 1$ .

Cover and Thomas (2006, §5.5) prove a stronger result: the Shannon code is competitively optimal in the sense that for any other prefix-free code $C^{'}$ with lengths $l_{i}^{'}$ ,

Pr [l_{S} (X) < l^{'} (X)] \geq Pr [l_{S} (X) > l^{'} (X)] .

The Huffman code inherits this property. This means the Huffman code is not just optimal on average but also dominates any competitor symbol-by-symbol in a probabilistic sense.

Tight redundancy bounds

The general redundancy bound is $L^{*} - H (X) < p_{m a x} + lo g_{2} (e / (e + 1)) \approx p_{m a x} + 0.0861$ , due to Gallager (1978). A sharper result by Capocelli, De Santis, and Gargano (1991) shows:

L^{*} - H (X) \leq σ - \frac{H ( X ) + σ}{1 + ln 2 \cdot p _{m a x}^{- 1}},

where $σ = 1 - H_{b} (p_{m a x})$ and $H_{b}$ is the binary entropy. For the special case $p_{m a x} \geq 1/2$ , the bound simplifies to $L^{*} - H (X) < p_{m a x}$ .

The redundancy is zero exactly when the distribution is dyadic (all probabilities are negative powers of 2). This is the only case where the Shannon code lengths $- lo g_{2} p_{i}$ are all integers, and the Huffman code achieves exact entropy.

Adaptive and canonical Huffman codes

In practice, the source distribution is often unknown. Adaptive Huffman coding (the FGK algorithm of Faller, Gallager, and Knuth) updates the Huffman tree incrementally as symbols are observed, maintaining the sibling property at each step. The redundancy of adaptive Huffman coding over a stationary source converges to the static redundancy as $n \to \infty$ .

Canonical Huffman codes assign codewords in a fixed order (e.g., the first codeword of length $l$ is the binary increment of the last codeword of length $l - 1$ ), which allows compact representation of the codebook: only the codeword lengths need to be transmitted, and the decoder reconstructs the canonical code from these lengths.

Synthesis. The Huffman algorithm is the unique greedy procedure that produces an optimal prefix-free code; the exchange argument at its core builds toward the method of types in 46.02.06 where universal codes achieve entropy without knowing the distribution. The redundancy bound $L^{*} - H < p_{m a x} + 0.086$ quantifies the gap between practice and theory, and the sibling property characterises Huffman codes structurally. The central insight is that local greedy merging guarantees global optimality, generalises to $D$ -ary alphabets and adaptive settings, and is dual to the Kraft inequality that constrains all prefix-free codes. Putting these together, the Huffman code is not merely a good heuristic but an exact solution to the optimal coding problem, with the redundancy bound characterising how far any practical code can deviate from the entropy limit.

Full proof set Master

Proposition (Redundancy bound via Shannon code). Let $C^{*}$ be the Huffman code and $C_{S}$ be the Shannon code for distribution $p$ . Then $L (C^{*}) \leq L (C_{S}) < H (X) + 1$ .

Proof. The Shannon code assigns lengths $l_{i} = ⌈ - lo g_{2} p_{i} ⌉$ . Since $- lo g_{2} p_{i} \leq ⌈ - lo g_{2} p_{i} ⌉ < - lo g_{2} p_{i} + 1$ , we have $p_{i} l_{i} < p_{i} (- lo g_{2} p_{i} + 1)$ for each $i$ . Summing: $L (C_{S}) = \sum p_{i} l_{i} < \sum p_{i} (- lo g_{2} p_{i}) + \sum p_{i} = H (X) + 1$ .

Since the Huffman code minimises expected length over all prefix-free codes, $L (C^{*}) \leq L (C_{S}) < H (X) + 1$ . $□$

Proposition (Huffman redundancy for dyadic distributions). If the distribution $p$ is dyadic (each $p_{i} = 2^{- k_{i}}$ for positive integers $k_{i}$ ), then $L (C^{*}) = H (X)$ .

Proof. For a dyadic distribution, the Kraft sum with $l_{i} = k_{i} = - lo g_{2} p_{i}$ is $\sum 2^{- k_{i}} = \sum p_{i} = 1$ , so by Kraft's theorem there exists a prefix-free code with these lengths. The expected length is $\sum p_{i} k_{i} = H (X)$ . Since $L \geq H (X)$ for any code (by the noiseless coding theorem, which follows from $L \geq H$ via Kraft's inequality and the log-sum inequality), this code achieves the lower bound. The Huffman code, being optimal, must also achieve $L (C^{*}) = H (X)$ . $□$

Connections Master

46.02.02 — Shannon's source coding theorem establishes $H (X)$ as the compression limit; the Huffman code achieves this limit up to the redundancy bound.
46.02.01 — The AEP shows that the typical set has $\approx 2^{n H}$ elements; Huffman coding assigns $\approx H$ bits per symbol, matching the AEP rate.
46.02.06 — The method of types and universal coding extend Huffman coding to settings where the source distribution is unknown; the redundancy bound quantifies the overhead.
46.03.04 — Sphere-packing bounds for channel codes are the dual of prefix-free constraints for source codes; both are governed by counting arguments.
40.06.06 — Linear codes and the Gilbert-Varshamov bound share the combinatorial counting structure that underlies the Kraft inequality.

Historical & philosophical context Master

David Huffman was a graduate student at MIT when he invented the algorithm in 1951. His information theory professor, Robert Fano, assigned the class a term paper on optimal prefix-free codes. Huffman, unable to prove anything about the existing top-down approach (Shannon-Fano coding), discarded it and invented the bottom-up merge algorithm in a flash of insight. The result was published in the Proceedings of the IRE in 1952 as "A Method for the Construction of Minimum-Redundancy Codes" (40(9), pp. 1098-1101). Fano is said to have remarked that Huffman had solved the problem that Fano and Shannon had both failed to crack.

The algorithm became one of the most widely deployed compression techniques in computing. It forms the backbone of JPEG image compression (after DCT and quantisation), MP3 audio compression, and the DEFLATE algorithm used in gzip and PNG. Canonical Huffman codes were adopted by the deflate format to minimise header overhead.

Robert Gallager's 1978 paper "Variations on a Theme by Huffman" (IEEE Trans. Info. Theory 24(6), pp. 668-674) deepened the theoretical understanding by introducing the sibling property and proving the tighter redundancy bounds. The adaptive FGK algorithm (Faller 1973, Gallager 1978, Knuth 1985) extended Huffman coding to the online setting where the source distribution is learned on the fly.

Bibliography Master

@article{huffman1952,
  author  = {Huffman, D. A.},
  title   = {A Method for the Construction of Minimum-Redundancy Codes},
  journal = {Proceedings of the IRE},
  volume  = {40},
  number  = {9},
  pages   = {1098--1101},
  year    = {1952},
}
@article{gallager1978,
  author  = {Gallager, R. G.},
  title   = {Variations on a Theme by {Huffman}},
  journal = {IEEE Transactions on Information Theory},
  volume  = {24},
  number  = {6},
  pages   = {668--674},
  year    = {1978},
}
@article{capocelli1991,
  author  = {Capocelli, R. M. and De Santis, A. and Gargano, L.},
  title   = {On the Redundancy of {Huffman} Codes},
  journal = {IEEE Transactions on Information Theory},
  volume  = {37},
  number  = {1},
  pages   = {144--148},
  year    = {1991},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@article{knuth1985,
  author  = {Knuth, D. E.},
  title   = {Dynamic {Huffman} Coding},
  journal = {Journal of Algorithms},
  volume  = {6},
  pages   = {163--180},
  year    = {1985},
}

Prerequisites

46.02.02

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §5.2 (the tree-building algorithm, the coin-weighing analogy, the English-letter example)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §5.2-5.4 (formal construction, proof of optimality by exchange argument, redundancy bounds)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §5.1-5.5; Gallager 1978 Variations on a Theme by Huffman IEEE Trans. Info. Theory 24(6) 668-674; Capocelli et al. 1991 On the Redundancy of Huffman Codes IEEE Trans. Info. Theory 37(1) 144-148

References

Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 5.2: the Huffman algorithm — bottom-up tree construction merging the two least-probable symbols. Section 5.3: proof of optimality via exchange argument — any optimal code can be transformed so that the two least-probable symbols are siblings at the bottom of the tree. Section 5.4: redundancy bound $L^{*} - H < p_{m a x} + lo g (e / (e + 1))$ and the sharper bound $L^{*} - H < p_{m a x}$ . Section 5.5: competitive optimality of the Shannon code.
Huffman, D. A. — A Method for the Construction of Minimum-Redundancy Codes · Proceedings of the IRE 40(9) (1952) 1098-1101. The original paper introducing the greedy merge algorithm. Huffman proves optimality by showing that an optimal prefix code can always be arranged so that the two least-probable source symbols are siblings with equal codeword length, then proceeds by induction on the alphabet size.
Gallager, R. G. — Variations on a Theme by Huffman · IEEE Transactions on Information Theory 24(6) (1978) 668-674. Derives the redundancy bound $L^{*} - H < p_{m a x} + 1$ and tighter versions. Introduces the sibling property: a prefix code is a Huffman code iff the corresponding code tree has the sibling property (the node probabilities can be listed in non-increasing order so that each node is adjacent to its sibling).

Estimated time

beginner: 15m
intermediate: 45m
master: 90m