Description:

In this assignment you are required to implement prefix$-$free codes using binary trees

with linked nodes. For this, you have to write the Java classes BinTree and TNode

in the same package. Class BinTree uses binary trees with linked nodes to represent

prefix$-$free codes. Class TNode represents the nodes of the binary tree. You also need to

perform the time and space complexity analysis of your algorithms.

You are not allowed to use any predefined Java methods other than those de$-$

fined in the classes java.util.ArrayList, java.lang.String and java.lang.Math.

Definitions:

A prefix$-$free code $($used in data compression$)$ is a set of binary sequences $($sequences

of $0$s and $1$s$)$ such that none of them is a prefix of another. For instance, the set

A $=\{0,10,110,111\}$ is a prefix$-$free code. On the other hand, the set $\{0,10,100,111\}$

is not a prefix$-$free code because the sequence $10$ is a prefix of $100.$ The elements of the

prefix$-$free code are referred to as $($binary$)$ codewords.

A prefix$-$free code can be used to encode a sequence of symbols from an alphabet B

$($i$.$e$.,$ convert the sequence of symbols into a bitstream$)$ as follows. Each symbol

in alphabet B $=\{$c$0,$ c$1,$ c$2,,$ cn$\}$ is assigned a distinct binary codeword. Then we

can encode any sequence of symbols by replacing every symbol by the corresponding

binary codeword. For instance, assume that alphabet B contains $4$ symbols. Then they

are c$0,$ c$1,$ c$2,$ c$3.$ Further, assume that symbol c$0$ is assigned $0,$ c$1$ is assigned $10,$ c$2$

is assigned $110$ and c$3$ is assigned $111.$ Consider now the following sequence of symbols

over the alphabet B: $$c$2$ c$3$ c$1$ c$2$ c$0$ c$0$ c$0.$ This sequence is encoded into the bitstream

$11011110110000.$