You have been asked to write a program to count the number of times each word occurs in a text file, and print them grouped according to word length. Below is a sample text file on the left, and the expected output of your program on the right:

This is the first line, and this line is the ultimate line

, is: 2

the: 2

and: 1

this: 2

line: 3

first: 1

ultimate: 1

Note that words are counted ignoring case, and are printed in order of word length. In any group of words of the same length, the printout can be in any order (e.g. the and and are both printed before words of greater length, but they need not be in any specific relative sequence.) You choose to store the words in an AVL tree. Each node in the AVL tree has a word (with its count), and words (alphabetical) are the basis of the AVL ordering.

a) Show the final AVL tree after all the words from the sample input file have been inserted. (Remember that words will be inserted one at a time as they are read in, but you only need to show the final tree, not all the intermediate trees). Make sure you show balance factors at all the nodes. There is only one correct AVL tree answer, following the AVL insertion algorithm you have learned in class.