9. Most books concerning algorithms and data structures present traversal algorithms as recursive procedures. (Recursive procedures are subroutines or functions that call themselves.) However, the computer achieves this recursion using iteration! The algorithm below uses a stack to perform an iterative preorder traversal of a tree.

(Refer to the previous question.) As each node is traversed, its key value is printed as in the diagram above.

ALGORITHM Preorder

TreeNode : node

Boolean : done

Stack: stack

Node ← root

Done ← FALSE

WHILE NOT done

WHILE node NOT NULL

PRINT node

PUSH node onto stack

node ← left child node pointer of node

ENDWHILE

IF stack is empty

done ← TRUE

ELSE

node ← POP node from stack

node ← right child node pointer of node

ENDIF

ENDWHILE

END Preorder

a) Modify the algorithm so that it will perform an in-order traversal.

b) Modify the algorithm so that it will perform a post-order traversal. (Hint: As you leave a node to follow its left sub-tree, update a value in the node to indicate that the node has been visited.)