Ternary Search Tries $(10$ Points$)$Huffman Encoding $(15$ Points$)$

Show the Huffman encoding trie construction process for the string

"AAAAA BBB CCCCCCCC DDDD EEEEEEEEE FF GGGG HHH HIIIIIIII JJJJJ K

Use the following table to count the frequencies.

Use the space below the table to show the steps involved in the construction of the Huffman encoding trie and write the final Huffman codes in the table below. $(15$ Points$)$

$\backslash$table$[[$Character$,$Frequency,Huffman Code$],[$A$,5,],[$B$,3,],[$C$,8,],[$D$,$U$,],[$E$,9,],[$F$,2,],[$G$,$U$,],[$H$,3,],[$I$,10,],[$J$,5,],[$K$,1,],[$Space$,,]]$

Draw the TST that results when the following keys are inserted into an initially empty TST $($do not draw null links$).$

$\begin{array}{cc}\text{K}\text{e}\text{y}& \text{V}\text{a}\text{l}\text{u}\text{e}\\ \text{f}\text{i}\text{f}\text{t}\text{y}& 50\\ \text{f}\text{o}\text{r}\text{t}\text{y}& 40\\ \text{t}\text{h}\text{i}\text{r}\text{t}\text{y}& 30\\ \text{t}\text{w}\text{e}\text{n}\text{t}\text{y}& 20\\ \text{t}\text{e}\text{n}& 10\\ \text{n}\text{i}\text{n}\text{e}& 9\\ \text{e}\text{i}\text{g}\text{h}\text{t}& 8\\ \text{S}\text{e}\text{v}\text{e}\text{n}& 7\\ \text{S}\text{i}\text{x}& 6\\ \text{f}\text{i}\text{v}\text{e}& 5\\ \text{f}\text{o}\text{u}\text{r}& 4\\ \text{t}\text{h}\text{r}\text{e}\text{e}& 3\\ \text{t}\text{w}\text{o}& 2\\ \text{o}\text{n}\text{e}& 1\\ \text{Z}\text{e}\text{r}\text{o}& 0\\ ?& ?\end{array}$