Step $1$: Inspect the Node$234.$h file

Inspect the Node$234.$h file. Node$234.$h is read$-$only and has a complete implementation of a Node$234$ class for a $2-3-4$ tree node. Member variables are protected and so must be accessed through the provided getter and setter functions.

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

Inspect the Tree$234$Iterator.h file. The Tree$234$Iterator class is declared, but required member functions are not implemented. The implementation must satisfy the following requirements:

Iteration 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$($log N$)$ time.

Dereferencing executes in worst$-$case O$(1)$ time.

Incrementing executes in worst$-$case O$($log N$)$ time.

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 pointers. 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 the iterator is dereferenced. "Visiting" a node means calling any of that node's member functions. Ex: Suppose an iterator is built for the tree below. Then the iterator's $*$ operator is invoked to return key $5,$ then $++$ is invoked to advance to key $10,$ then $*$ is invoked to return key $10,$ then $++$ is invoked to advance to key $15,$ and then $*$ is invoked to return key $15.$ The iterator should have only visited the highlighted nodes.

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

Implement the Tree$234$Iterator to satisfy the complexity requirements mentioned above. Code in main.cpp 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 code in main.cpp$.$ Rather, main.cpp 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 and ensure that the test in main.cpp passes before submitting code for grading.

Hints

Assume that Tree$234\text{'}$s begin$()$ and end$()$ member functions return a Tree$234$Iterator object.

Tree$234$ uses a template type, IteratorType, for the iterator type, allowing specialized iterators to be used for grading. So the declared return type for begin$()$ and end$()$ is actually IteratorType.

The conceptual description of an iterator mentions that the iterator "points to$"$ a key. In the actual implementation, the "pointer" to a key is not an int$*.$ The iterator must know if more keys exist in the node, and a direct pointer to the key integer itself does not include such information.