Tree iterator functions :An iterator is a structure that refers to the current position in some data structure. It is used to iterate through a data structure without needing to know the underlying details of the data structure. In other words, it encapsulates the process of iterating through a data structure.

In this part of the assignment, you will be implementing a tree iterator for a binary tree of shapes. The tree structure and iterator structure can be found in pointer.h$.$ Each tree node will have a pointer to a shape as well as a pointer to its left and right subtrees. The iterator will contain a pointer to the current node as well as the current depth of the node in the tree $($i$.$e$.,$ distance from the root node$)$ and an array of parent pointers for iterating through the tree. The first begin function starts the iteration at the first in$-$order node. The following next function transitions the iterator to the next in$-$order node. In$-$order traversal refers to the case where for any node X$,$ you always traverse the left subtree of X before traversing X$,$ and you always traverse the right subtree of X after traversing X$.$ For example, doing an in$-$order traversal of a sorted tree will traverse the nodes in sorted order. Next, the at$\_$end function indicates whether the iterator has reached the end of the tree, which is represented by a NULL state indicating the iterator is beyond the last node in the tree. The last two functions are accessor functions that return the node and shape corresponding to the current iterator position.

The purpose of the parents array is to help you traverse the tree as you are iterating through it$,$ so you'll need to update and$/$or use the array in the begin and next functions. The idea is that the array represents a stack of parent pointers similar to how recursively iterating through a tree tracks the nodes via variables$/$parameters stored within the function stack. The parents array essentially allows you to store that partial stack state as you iterate through the tree. Figuring out how this works is the challenge in this part of the assignment, and it is your responsibility to come up with a solution entirely on your own. Looking up solutions and$/$or hints is an academic integrity violation. This is meant to be the hardest part of the assignment where you have to think critically to develop a solution. Drawing pictures of trees and working through small examples can be very helpful. Lastly, note that you are NOT allowed to search for the next node starting from the root of the tree. We have explicitly added tests to break this approach. The purpose of the iterator is to store enough information to be able to effectively traverse through the tree from the current node.

$//$ Initializes an iterator to the beginning of a tree $($i$.$e$.,$ first in$-$order node$)$

void tree$\_$iterator$\_$begin$($tree$\_$iterator$\_$t$*$ iter, tree$\_$node$\_$t$*$ root$)$

$\{$

$//$ IMPLEMENT THIS

$\}$

$//$ Updates an iterator to move to the next in$-$order node in the tree if possible

$//$ Moving past the last in$-$order node in the tree results in the iterator reaching a NULL state representing the end of the tree

void tree$\_$iterator$\_$next$($tree$\_$iterator$\_$t$*$ iter$)$

$\{$

$//$ IMPLEMENT THIS

$\}$

$//$ Returns true if iterator is at the end of the tree or false otherwise

$//$ The end of the tree is the position after the last in$-$order node in the tree $($i$.$e$.,$ NULL state from tree$\_$iterator$\_$next$)$

bool tree$\_$iterator$\_$at$\_$end$($tree$\_$iterator$\_$t$*$ iter$)$

$\{$

$//$ IMPLEMENT THIS

return false;

$\}$

$//$ Returns the current node that the iterator references or NULL if the iterator is at the end of the tree

tree$\_$node$\_$t$*$ tree$\_$iterator$\_$get$\_$node$($tree$\_$iterator$\_$t$*$ iter$)$

$\{$

$//$ IMPLEMENT THIS

return NULL;

$\}$

$//$ Returns the current shape that the iterator references or NULL if the iterator is at the end of the tree

shape$\_$t$*$ tree$\_$iterator$\_$get$\_$shape$($tree$\_$iterator$\_$t$*$ iter$)$

$\{$

$//$ IMPLEMENT THIS

return NULL;

$\}$

$//$IN C PROGRAMMING