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.