The traversal methods that are part of theLinkedTreeclass are limited in two significant ways: (1) they always traverse the entire tree; and (2) the only functionality that they support is printing the keys in the nodes. Ideally, we would like to allow the users of the class to traverse only a portion of the tree, and to perform different types of functionality during the traversal. For example, users might want to compute the sum of all of the keys in the tree. You will add support for more flexible tree traversals by implementing an iterator for ourLinkedTreeclass.

You should use an inner class to implement the iterator, and it should implement the following interface:

public interface LinkedTreeIterator { // Are there other nodes to see in this traversal? boolean hasNext(); // Return the value of the key in the next node in the // traversal, and advance the position of the iterator. int next(); } 

You will implement apostorderiterator for this problem.

Your postorder iterator class should implement thehasNext()andnext()methods so that, given a reference named tree to an arbitraryLinkedTreeobject, the following code will perform a complete postorder traversal of the corresponding tree:

LinkedTreeIterator iter = tree.postorderIterator(); while (iter.hasNext()) { int key = iter.next(); // do something with key } 

Important guidelines

• In theory, one approach to implementing a tree iterator would be to perform a full recursive traversal of the tree when the iterator is first created and to insert the visited nodes in an auxiliary data structure (e.g., a list). The iterator would then iterate over that data structure to perform the traversal.You shouldnotuse this approach.One problem with using an auxiliary data structure is that it gives your iterator a space complexity ofO(n), wherenis the number of nodes in the tree. Your iterator class should have a space complexity ofO(1).
• Your iterator'shasNext()method should have a time efficiency ofO(1).
• Your iterator's constructor andnext()methods should be as efficient as possible, given the time efficiency requirement forhasNext()and the requirement that you use no more thanO(1) space.
• We encourage you to consult our implementation of thePreorderIteratorclass when designing your class. It can also help to draw diagrams of example trees and use them to figure out what you need to do to go from one node to the next.

Here are the tasks that you should perform:

1. 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.
2. In the copy ofLinkedTree.javathat we've given you for this assignment, the innerNodeclass includes a field calledparent, but theLinkedTreecode doesnotactually maintain this field as the tree is updated over time. Rather, thisparentfield is assigned a value ofnullby theNodeconstructor, and its value remainsnullforever.
3. Before implementing the iterator, you should make whatever changes are needed to the existingLinkedTreemethods so that they correctly maintain theparentfields in theNodeobjects.

• For example, when aNodeobject is first inserted in the tree, you should set itsparentfield 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 theparentfield in aNodeobject whenever its parent changes.
• The root of the entire tree should have aparentvalue ofnull.

1. Next, add a skeleton for your iterator class, which you should namePostorderIterator(note that only thePandIare capitalized). It should be a private inner class of theLinkedTreeclass, and it should implement theLinkedTreeIteratorinterface. Include whatever private fields will be needed to keep track of the location of the iterator. Use ourPreorderIteratorclass as a model.
2. Implement the constructor for your iterator class. Make sure that it performs whatever initialization is necessary to prepare for the initial calls tohasNext()andnext().
3. In thePreorderIteratorconstructor that we've given you, this initialization is easy, because the first node that a preorder iterator visits is the root of the tree as a whole. For a postorder iterator, however, the first node visited is not necessarily the root of the tree as a whole, and thus you will need to perform whatever steps are needed to find the first node that the postorder iterator should visit, and initialize the iterator's field(s) accordingly.
4. Implement thehasNext()method in your iterator class. Remember that it should execute inO(1) time.
5. Implement thenext()method in your iterator class. Make sure that it includes support for situations in which it is necessary to follow one or moreparentlinks back up the tree, as well as situations in which there are no additional nodes to visit. If the user calls thenext()method when there are no remaining nodes to visit, the method should throw aNoSuchElementException.
6. Add apostorderIterator()method to the outerLinkedTreeclass. It should take no parameters, and it should have a return type ofLinkedTreeIterator. It should create and return an instance of your new class.
7. Test everything!At a minimum, you must do the following:In themain()method, add a unit test that uses thewhile-loop template shown near the start of this problem to perform a full postorder traversal of a sample tree.