Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

 3 "The typical property of frequency trees for Huffman encoding" -> "The characteristic property..." because it's not just typical, it's MUST HAVE edit approved Sep 16 '18 at 3:53 Bulat 1,59211 gold badge77 silver badges1414 bronze badges 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 typicalcharacteristic 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. 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 typical 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. 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. 2 [Edit removed during grace period]; added 5 characters in body edited Sep 14 '18 at 20:51 RandomPerfectHashFunction 45122 silver badges99 bronze badges 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 typical property of this frequency tree for Huffman encoding is that, all internal nodes have exactly two children. The typical 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. 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 typical property of this frequency tree 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. 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 typical 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. 1 answered Sep 14 '18 at 20:41 RandomPerfectHashFunction 45122 silver badges99 bronze badges 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 typical property of this frequency tree 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.