For this coursework, you are tasked with implementing the AVL tree algorithm. Your starting point will bean array of integers, which you will use to construct the AVL tree. Following the construction of the tree, you should output its elements in post-order traversal approach.

The necessary files for this assignment are available for download from Moodle. These include:

•    `Input.txt`: An example file that you will read as input.

•    `Output.txt`: A sample output file that corresponds to the `Input.txt` input.

Your Java code should fulfill the following requirements:

1.    Read the content of `Input.txt`.

2.    Implement the AVL tree algorithm.

3.    Print the constructed tree using post-order traversal, with each node printed on a new line.

For instance, given the content of 'Input.txt'provided:

9,6,2,1,4,25,16,13,37,27,17,34,10

The expected 'Output'should look like this:

1

4

2

9

13

10

6

17

25

34

37

27

16

Grading Criteria

Definitions

Standard input

System.in, means that the stream from which input to the program is taken. Typically this is the keyboard, but it can be specified that input is to come from a serial port or a disk file.

Standard output

System.out, means that the stream to which output from the program is sent. Typically this is a display, but it can be redirected to a serial port or a file.

Submission

You must submit a single Java source code file containing all your code for this coursework. This file must be called AVL.java and must not require any other files outside of the standard Java packages  which are always available. The file must compile and execute without warnings or errors using the command.

Compile: javac -encoding UTF-8 -sourcepath . AVL.java

Execute: java -Dfile.encoding=UTF-8 -XX:+UseSerialGC -Xss64m -Xms1920m -Xmx1920m AVL < Input.txt > Output.txt

Your program SHOULD send its output to standard output (by executing above command, it will produce Output.txt in the same directory as AVL.java and Input.txt, so no FileWriter is required).

Technical Notes

This part contains important technical information and it is important that you read and understand all the information below.

You program MAY have multiple classes if you wish, but only in one java file. And only the class with your main method SHOULD be marked as public.

Your program MUST read its input from standard input.

If your program exits with a non-zero exit code, it will be judged as a run-error.

Program submitted will be run inside a sandbox. The sandbox will allocate 2GB of memory for your   program. Your entire program, including its runtime environment, must execute within this memory limit. For Java, the runtime environment includes the interpreter (JVM).

We suggest that you do not use package statements (that is, we suggest that your solution reside in the “default package”).

Please use JDK versions latter than 7.

Possible results

A submission can have the following results:

CORRECT The submission passed all tests: you solved this problem! 0% will be given to errors listed below:

COMPILER-ERROR There was an error when compiling your program. Note that when compilation takes more than 30 seconds, it is aborted and this counts as a compilation error.

TIMELIMIT Your program took longer than the maximum allowed time for this problem, 5 seconds. Therefore it has been aborted. This might indicate that your program hangs in a loop or that your solution is not efficient enough.

RUN-ERROR There was an error during the execution of your program. This can have a lot of different causes like division by zero, incorrectly addressing memory (e.g., by indexing arrays out of bounds),

trying to use more memory than the limit, reading or writing to files, etc. Also check that your program exits with exit code 0!

NO-OUTPUT Your program did not generate any output. Check that you write to standard out.

OUTPUT-LIMIT Your program generated more output than the allowed limit. The solution is considered incorrect.

WRONG-ANSWER The output of your program was incorrect. This can happen simply because your

solution is not correct, but remember that your output must comply exactly with the specifications of

the judges. See testing below for more details. The judges may have prepared multiple test files for each problem.