1. Use the following algorithm steps to write the method, constructHuffmanTree (listHead, Root), where listHead and Root are HuffmanTreeNode pointers and listHead points to an ascending linked list sorted by nodes' prob. (8)

Step 1: newNode create a HuffmenTreeNode // use the constructor you wrote in the above

newNodes prob the sum of prob of the first and second node of the list // first is the node after dummy

newNodes chStr concatenate chStr of the first node and chStr of the second node in the list

newNodes left the first node of the list

newNodes right the second node of the list

newNodes next null

Step 2: listInsert (listHead, newNode) // You may call listInsert mehod without define it again.

Step 3: listHeads next listHead.next.next.next // third node after dummy node

Step 4 : repeat step 1 step 3 until the list only has one node after the dummy node

Step 5: Root listHead's next