chap binary trees class hufftree / huffman coding tree private huffnode root/root of the tree public hufftree(lettfreq valroot new huffnode(val)public hufftree(lettfreq valhufftree lhufftree rroot new huffnode(vall root() root())public huffnode root(return rootpublic int weight(/weight of tree is weight of root return root element(weight()figure class declarations for the huffman tree induction hypothesisassume that any tree created by buildhuff that contains leaves has minimum external path length induction stepgiven huffman tree built by buildhuff with leavesn > suppose that < <<wn where to wn are the weights of the letters call the parent of the letters with frequencies and from the lemmawe know that the leaf nodes containing the letters with frequencies and are as deep as any nodes in if any other leaf nodes in the tree were deeperwe could reduce their weighted path length by swapping them with or but the lemma tells us that no such deeper nodes exist call the huffman tree that is identical to except that node is replaced with leaf node whose weight is by the induction hypothesist has minimum external path length returning the children to restores tree twhich must also have minimum external path length thus by mathematical inductionfunction buildhuff creates the huffman tree with minimum external path length assigning and using huffman codes once the huffman tree has been constructedit is an easy matter to assign codes to individual letters beginning at the rootwe assign either ' or ' to each edge in the tree ' is assigned to edges connecting node with its left childand ' to edges connecting node with its right child this process is illustrated by figure the huffman code for letter is simply binary number determined by the path from the root to the leaf corresponding to that letter thusthe code for is ' because the path from the root to the leaf node for takes single left branch the code for is ' because the path to the node for takes four