In order for an iterator to work, it$$s necessary for each node to maintain a reference to its parent in the tree. These parent references will allow the iterator to work its way back up the tree.

In the copy of LinkedTree.java that we$$ve given you for this assignment, the inner Node class includes a field called parent, but the LinkedTree code does not actually maintain this field as the tree is updated over time. Rather, this parent field is assigned a value of null by the Node constructor, and its value remains null forever.

Before implementing the iterator, you should make whatever changes are needed to the existing LinkedTree methods so that they correctly maintain the parent fields in the Node objects.

For example, when a Node object is first inserted in the tree, you should set its parent field to point to the appropriate parent node.

Think about when the parent of a node can change, and update the necessary method$($s$)$ to modify the parent field in a Node object whenever its parent changes.

The root of the entire tree should have a parent value of null.