TreeStats

Background:

The height of a binary tree is defined as the number of nodes in the longest path from the root to a leaf of the tree. The heights of the trees above are 5 for Tree 1, and 6 for Tree 2.

The width of a binary tree is the number of nodes in the longest path in the tree. The width of an empty tree is 0, and the width of a single-node tree is 1. The width of Tree 1 is 8 (symbolized by the darkened nodes) and the width of Tree 2 is 9. The longest path may or may not include the root node.

In general, the width of an empty tree is 0, and the width of a nonempty tree is the maximum of the following three quantities:

1. The width of the left subtree

2. The width of the right subtree

3. The length of the longest path that includes the root (which can be calculated from the heights of the left and right subtrees)

When writing these two methods (height and width), you may find it useful to use the max method from the java.lang.Math.

Math.max(int a, int b)

Assignment:

1. Fill in the methods in MyTreeSet.java to perform the following functions in the menu below:

   (1) Fill the tree from a file
(2) Preorder output
(3) Inorder output
(4) Postorder output
(5) Count the nodes in the tree
(6) Count the leaves in the tree
(7) Find the height of the tree
(8) Find the width of the tree
(9) Clear the tree - i.e. remove all nodes from tree
(10) Interchange the tree(mirror image)
(11) Print all nodes of a given level of a tree
(12) isAncestor
(q) Quit

2. Your task is to systematically code and test each of these methods. The data stored in this tree will be a single letter (stored as a String). The source of the letters will be two different files, each consisting of one line of capital letters: (fileA.txt) and (fileB.txt).

   (fileA.txt) = KECAJGHOSRV

   (fileB.txt) = QJHBADFKNLMPTW
   

3. You should print appropriate messages, labeling each output.

Instructions:

1. The two files above will generate binary trees having the distinctive shape shown at the top of the first page of this lab. This will allow you to test your program and verify the correctness of your answers.
   
2. Turn in your code to Web-CAT.