Step $2$: Inspect the Tree$234$Iterator.java file

Inspect the Tree$234$Iterator.java file. The Tree$234$Iterator class is declared, but no fields exist and methods are not implemented. The

implementation must satisfy the following requirements:

The iterator never changes the tree in any way

Iteration starts at the tree's minimum key and ends at the maximum

Construction occurs in worst$-$case $O(logN)$ time

hasNext$()$ executes in worst$-$case $O(1)$ time

next$()$ executes in worst$-$case $O(logN)$ time

The iterator's space complexity is worst$-$case O$($log $N$

For simplicity, assume the tree is not changed by an outside source during the iterator's lifetime.

Step $3$: Understand requirement implications

To satisfy the requirements, the iterator must maintain a collection of node references. A node exists in the collection only if that node must

be revisited at some point in time.

The iterator must visit only the necessary nodes to deliver a key when next$()$ is called. "Visiting" a node means calling any of that node's

methods. Ex: Suppose an iterator is built for the tree below and the iterator's next$()$ method is called three times to return keys $5,10,$ and $15.$

The iterator should have only visited the highlighted nodes.

Node visited by iterator that has iterated

through keys $5,10,$ and $15$

Node not visited by iterator that has iterated

through keys $5,10,$ and $15$ Node visited by iterator that has iterated

through keys $5,10,$ and $15$

Node not visited by iterator that has iterated

through keys $5,10,$ and $15$

Step $4$: Implement the Tree$234$Iterator class

Implement the Tree$234$Iterator to satisfy the complexity requirements mentioned above. Code in LabProgram.java adds random keys to a

Tree$234$ object, then tests that the iterator properly iterates through all keys in ascending order. But time and space complexity aren't tested

by LabProgram. LabProgram only ensures that the iterator properly iterates through all keys.

Most unit tests will fail if the iterator does not properly iterate through all the tree's keys in the correct order. So run code in develop mode

and ensure that the test passes before submitting code. Run your program as often as you'd like, before submitting for grading. Below, type any needed

input values in the first box, then click Run program and observe the program's output in the

second box.

Enter program input $($optional$)$

If your code requires input values, provide them here.Run your program as often as you'd like, before submitting for grading. Below, type any needed

input values in the first box, then click Run program and observe the program's output in the

second box.

Enter program input $($optional$)$

If your code requires input values, provide them here.In this lab, the Tree$234$ class is extended to support iteration with an enhanced for loop. Such support is provided via the implementation of

an iterator that can iterate through the tree's keys in ascending order.

An iterator is an object that maintains a reference to a specific element in a collection and can move to the next element. Ex: A Tree$234$

iterator references the tree's minimum key upon construction. The iterator can then move to the second to minimum key, then the third to

minimum, and so on$.$ Eventually the iterator moves to the last key and can move no further.

Overview of Iterable and Iterator in Java

Enhanced for loops work on any class that implements the Iterable interface. Tree$234$ stores a collection of integer keys, so the Tree$234$

class implements Iterable