Part 1:

You're not really convinced those recursive methods operating on trees really work, so you plan

to write one for yourself and see. You will implement a recursive method that changes a binary tree (any binary tree; not necessarily balanced, not necessarily a BST) as if it was flipped left to right.

As an example, the transformation below would be performed when the tree is flipped.

AA

B C to C B DE ED

Hint: the code is minimal but some thinking is required. As always, best done on paper first. To test your code you can make up a tree by manually linking nodes. Then flip it and verify the result (you can do a tree traversal and print each node).

Part 2:

You have some free time left and you decide to have a look at an industrial strength balanced

BST implementation. You have heard that for any large size text, quite a large portion of the words are very common words which occur over and over again (e.g. a, the, ...). You plan to check for yourself by counting occurrences of all the words in a text file that occur more often than a given number of times and compare that number to the total of words in the file. You will print these words and the number of times they each occur so that you get some idea what kind of words these are.

Part 3:

You will analyze the time efficiency of your solution in part 2.

Hints:

- Have a look at the TreeMap class documentation. Don't be intimidated by the large number of

methods; you will only need to use the main ones we have seen.

https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html

- Once you have all the word number of occurrence pairs in the tree, you will iterate over the tree and print the pairs in order.

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Map;

import java.util.Scanner;

import java.util.SortedMap;

import java.util.TreeMap;

/**

*

* @author YOUR NAME HERE

*

*/

public class Project5 {

/*

* ******************************** Part 1 ******************************

*/

/* DO NOT MODIFY THE NODE CLASS */

static class Node {

Node(int data) {

this.data = data;

}

int data;

Node left;

Node right;

}

static void flip(Node root) {

// ****************** Your code here **********************

}

/*

* ******************************** Part 2 ******************************

*/

/**

* Prints all the words that occur threshold times or more and their count.

* The words are printed in alphabetical order.

* All the words read from the file are converted to lower case so that "That" and "that"

* are considered the same word. Empty words are not counted.

*

* @param filename The text file to process

* @param threshold e.g. 1000 -> only words that occur 1000 times or more are printed

*/

static void mostFrequentWords(String filename, int threshold) {

// You may find useful these methods for strings:

// split(), toLowerCase(), trim(), isEmpty()

// iterate over the pairs and print the ones that meet the threshold

// System.out.println(word + " " + count);

// print statistics

System.out.println("Total words : " + 0);

System.out.println("Total common words: " + 0);

System.out.println("Total common words as a portion of total words: " + 0);

}

/*

* ******************************** Part 3 ******************************

* Your Part 2 time analysis here.

* Briefly and clearly explain where the final time big O comes from:

*

*

*

*/

/**

* @param args

*/

public static void main(String[] args) {

/*

*

* Test your code well.

*

* You can leave that code in the main but I will not use that or grade

* you on it.

*/

Node root = new Node(1);

// populate tree ...

flip(root);

System.out.println("Most frequent words:");

mostFrequentWords("LesMiserables.txt", 1000);

// Would output something like below (all numbers shown are made up)

// a 12345 - this means the word "a" occured 12345 times in the text

// all 2345 - "all" 2345 times, and so on ...

// an 3456

// ...

// ...

// with 4567

// would 1234

// you 2345

// Total words : 234567

// Total common words: 123456

// All common words as a portion of total: 0.53

}

}