You should submit your solution on Canvas as a cpp file named as Firstname_Lastname_HW6.cpp. For ex, if your name is Adam Smith, the submitted file will be Adam_Smith_HW6.cpp

However, you are instructed to use binary search trees rather than arrays.

Main task (100 points)

Assume that you are working for Google and you want to analyze the trends of users' queries, e.g. what are the most frequent search terms. prepare a program whose input is a text file named input.txt containing search terms, each term is in one line. Its output is a text file named output.txt which lists all distinct terms in the input file with their corresponding frequencies sorted decreasingly by those frequencies. Each term and its frequency are written in one line.

ex:

input.txt
dog
cat
iPhone
dog
snow
cat
dog

output.txt
dog 3
cat 2
iPhone 1
snow 1

Note: The input file might contain up to a million distinct terms.

Instruction:
You will store the words and their frequencies in binary search trees. A tree node will contain a field for the word, a field for the count, and two pointers to its left and right nodes.

First, you use a binary search tree T for the words. That is, when you read a new word, you will find the corresponding node in the tree. If that node exists, you increase the corresponding count. If not, you create a new node for the word (with initial frequency of 1) and insert it to the tree T.

After reading all the words, you will use another binary search tree S to sort the frequencies. You will visit all nodes of T (using any tree traveral method). For each node, you will create an equivalent node (i.e. same word and frequency) for inserting into S. When inserting, you check frequency first. If frequencies equal, you will compare the words.

Finally, you print S to the output file, using in-order traveral and call recursively for the right node before the left node. This way, you will have the output with frequencies sorted descendingly.