but we can still represent it as a binary tree.
It's just not going to be a complete one. So I'm going to label the edges of this
tree the same way as before. Left-child edges will be given a label of
0, right-child edges will be given a label
of 1. I'm going to label the left and right
children of the root A and D respectively and the two leaves will be given the
labels B and C. The reason I labeled the nodes in this
way is, because then we have the same kind of correspondence between the
encodings that we proposed for the various symbols and the bits that you see
along a path from the root to nodes with those symbols.
So for example, if you at the node labeled D, the path from the root only
has a single bit 1 and that coincides with the proposed encoding of the symbol
D. Now, remember, this code is not
prefix-free and so therefore, as we saw, it had ambiguity.
So if you're wondering what some encoded message means and you see a 0, you're not
sure that 0 might be representing the symbol A or alternatively it might be the
first half of an encoding of the symbol B.
So, this ambiguity is also noticeable in the tree.
And the property in the tree that tips you off to the ambiguity is that there
are symbols at internal nodes of the tree.
The symbols are not merely at the leaves as they were with the first tree with the
fixed length in coding, but there are also two internal nodes
that have symbols. So let's draw the tree for our final
example which, was the variable length but prefix-free code that we looked at in
the previous video. So this is going to correspond to a tree
which is not perfectly balanced, but it will have labels only at the leaves of
the tree. So, if you label the edges of this tree
the way we've been doing, all the left-child edges get a 0, all the
right-left edges get a 1, and we label the leaves of the tree from
A to D going from left to right. You'll see we have the same
correspondence as in the previous two trees.
the sequence of bits from the root to a leaf coincide with the proposed encoding
for it. So, for example, if you look at the leaf
labeled C, because you traverse a right-child, another right-child and a
left-child to get to it, that's the sequence 1, 1, 0 and that is precisely
the proposed encoding for the symbol C. So in general, any binary code can be
expressed as a tree in this way, with the left-child pointers being labeled with
0's, the right child pointers being labeled with 1's,
and the various nodes being labeled the symbols of the given alphabets, and the
bits from the root down to the node labeled with the given symbol
corresponding to the proposed encoding for that symbol.