Your program has to be a console based program (no graphical interface). The user should not be prompted for any information (all required information for the program to run is provided in the input file given as a command line argument). The output of the program should be printed to standard output stream. Any error messages should be printed to the standard error stream.

PROGRAM USAGE

The program is started from the command line (or run within an IDE). It expects one command line argument: the name of the input file.

The input file describes the binary tree maze. Each line in the input is a single node in the maze (node in a BST). The format of each line is as follows:

LABEL LIFE POINTS

In the above, LABEL is a string with the name of the node. The alphanumeric comparison of the labels determines the shape of the tree. LIFE_POINTS is a number of life points that our hero can collect at that node. See below for an example.

If the program is executed with non-existent or invalid command line argument, it should print an error message and terminate.

If the file contains any additional (and invalid) strings in the description of a node, those extra strings should be ignored. (Each valid line contains only one string followed by one number.)

The program should not be interactive. All input should be provided as the command line arguments. The user should not be prompted for any additional information.

RESULTS/OUTPUT

The program has to calculate all possible paths through the maze that lead to the valid exits that are reachable by our hero. Valid exits are leaves in the tree that are at the lowest level. But our hero needs to have enough life points to reach such an exit. If the life points run out before the exit can be reached, the path to such an exit should not be listed among the ones recommended by your program.

The program output should consist of a number of lines equal to the number of valid paths. Each valid path should consist of a space separated list of the node labels in order in which they are followed from the root of the tree to the leaves that are valid exits. The paths should be printed in order from leftto rightin the binary search tree that represents the maze (this is also the alphanumeric ordering of the paths).

EXAMPLE

The above figure depicts visually a tree that results from the following input file

J 2

G 1

Q 0

B 0

I 1

A 0

C 1

E 2

D 0

H 1

F 0

L 3

R 1

U 0

S 1

V 1

T 1

K 2

O 0

P 1

N 2

M 0

The starting point for the maze is at its root at node lebeled "J". The valid exits from the maze are at the nodes at the lowest level. They are labeled "D", "F", "M", and "T". There are trap doors at any leaf node that is not at the lowest level. They are nodes labeled "A", "H", "K", "P", and

"V"

.

The tree also shows the number of life points that the hero can collect at each of the life-points. Note that if a number of life points at the room is less than one, the hero cannot go anywhere since they need exactly one life-point to travel from one node to the next.

There are several possible paths through the maze depicted above, but only three lead to reachable valid exits that are reachable by our hero with sufficient life points. The four paths that reach the bottom-most level are J G B C E D, J G B C E F, J Q L O N M, and J Q R U S T. The last path does not allow our hero to collect enough life points to make it to the bottom-most level.

In this case, the program should produce three lines of output:

J G B C E D

J G B C E F

J Q L O N M

DATA STORAGE AND ORGANIZATION

The design of classes is up to you, but you do need to implement certain classes to represent certain entities in the program. You need to make decisions about how to design these classes to produce an efficient and well-put- together program. Make sure that all methods that you include in a particular class belong in that class.

BinaryTreeMaze class

This is the class that is the program. This means it has the main method. This class is responsible for parsing and validating the command line arguments, reading and parsing the input file, producing any error messages, handling any exceptions thrown by other classes, and producing output.

BST class

This is a generic BST class. The specification is similar to the one for TreeSet class provided by Java libraries, but your implementation will be very different.

The specification for this class is provided at its javadoc page. You can use the source code that we wrote in class, but keep in mind that the class that you are implementing requires additional functionality and you may need to rewrite some of the methods that were created in class.

Node class

The program should provide and use a nested class (to learn more about nested and inner classes see: https://docs.oracle.com/javase/tutorial/java/javaOO/nested.h that provides nodes for your tree. The details of the implementation of that class are up to you, but this class should be private (or protected, if another class in your code inherits from it and needs to be able to create variables of type Node): private class Node

HINT: to improve the performance of your BST algorithms, it may be useful to keep additional data fields in the nodes, i.e., more than just data, left and right. Those design decisions are up to you. But you should explain in comments for this class, why you have additional data fields if you chose to do so.

Iterator

The BST class implements Iterable interface. This means that its iterator() method needs to return an instance of a class that implements the Iterator interface. The iterator() method should return an iterator instance that accesses the values in the tree according to the inorder traversal of the binary search tree. The two additional methods preorderIterator() and postOrederIterator() need to return iterators that access the values in the tree according to the preorder and postorder traversals, respectively.

The details of the implementation are up to you and you are free to implement more than one internal private iterator class. The next() and hasNext() methods of the iterator classes should perform in O(1). The constructor of the iterator classes should be O(N).

The remove method in the Iterator interface is optional and you do not need to provide the actual remove functionality. (This means that the method has to exist, but instead of performing its function, it throws an instance of UnsopportedOperationException.)

NOTE: normally, all data fields in the class should be private. But since the BST class serves as a base class for the Maze class below, its data fields can be made protected instead to allow the subclass to access these data fields.

Maze class

This should be the class that inherits from your own BST. Your class should represent the maze itself (therefore, it should not be generic and its nodes should store data items of type MazeNode). It is up to you to decide how to implement this class, which methods to provide etc. The important distinction is that the Maze class should contain all the methods that are specific to the maze itself, not the general BST methods that are inherited from the BST class.

MazeNode class

This class should represent the points in the maze at which our hero can collect life-points and at which they need to make a decisions as to which way to continue. It should be capable of storing the label of the node and the number of possible life points our hero can collect at this maze node. It may be useful (or may be even necessary) to implement the Comparable interface.

Note that his is NOT the same as the internal Node class for the BST class itself.

Hero class

This class should represent our hero traveling through the maze. An object of this class should be capable of keeping track of all the life points that our hero possesses at any given time. This information should be updated as the hero travels along the different potential paths through the maze.

You may, but you are not required to, implement other classes.