chap binary trees figure huffman tree for the letters of figure and intlnode this implementation reflects the fact that leaf and internal nodes contain distinctly different information figure shows the implementation for the huffman tree nodes of the tree store key-value pairs (see figure )where the key is the weight and the value is the character figure shows the java code for the tree-building process huffman tree building is an example of greedy algorithm at each stepthe algorithm makes "greedydecision to merge the two subtrees with least weight this makes the algorithm simplebut does it give the desired resultthis section concludes with proof that the huffman tree indeed gives the most efficient arrangement for the set of letters the proof requires the following lemma lemma for any huffman tree built by function buildhuff containing at least two lettersthe two letters with least frequency are stored in siblings nodes whose depth is at least as deep as any other leaf nodes in the tree proofcall the two letters with least frequency and they must be siblings because buildhuff selects them in the first step of the construction process assume that and are not the deepest nodes in the tree in this casethe huffman tree must either look as shown in figure or in some sense be symmetrical to this for this situation to occurthe parent of and labeled vmust have greater weight than the node labeled otherwisefunction buildhuff would