Description
Modify the binary tree iterator from the BinarySearchTree code in lecture 12 or the AVLTree code in lecture 13 to support iterating in reverse order. For in-order traversal, it would first visit the right child, then the parent, then the left child. For post-order, it would first visit the right child, then the left child, then the parent. For pre-order, it would first visit the parent, the the right child, then the left child.
Do this by creating a BinaryTreeIteratorDirection enumeration with the values forwardTraversal andbackwardTraversal, and add this to the BinaryTreeNodeIterator struct as direction, and as a parmeter to newBinaryTreeNodeIterator().
Modify getNextBinaryTreeIteratorNode() to use this enum value to traverse the tree in forward or backward direction. The effect should be the same as if the tree were actually built in descending rather than ascending order. Modify the test cases to also test backwardTraversal.
Hint: Think about parameterizing the function using firstLink and secondLink rather than leftLink and rightLink, which can be set on entry to the function.
