Guidelines for writing pseudocode:

1. C/Java/Python instructions are fine. But do not write object-oriented additions. Do not declare or use any class. Declare only procedures (if necessary) and explain in words what each procedure does, and what is the use of each parameter.

2. One instruction per line

3. Match the brackets with a horizontal line

4. Number your lines

5. Write down if your array is indexed 0...n1 or 1...n.

6. If you decide to use procedures/functions/methods from the class (such as, say, DELETE- MAX(S) for S a max-heap), explain clearly what they do and in what running time. Explain the data structures, if any.

Question: You are given a tree represented by the following data structure. Nodes have three fields: element, parent, and auxiliary. The auxiliary field is 0 and is there to help during traversals. In this problem your algorithm should leave the tree unchanged. You are given the location (or pointer to) two nodes x and y. The goal is to print the elements on the path from x to y in tree, in time proportional to the length of the path. That is, if the tree has n nodes and this path has length k, the running time of the algorithm should be O(k) (O(n) is not good enough, and the tree does not have to be balanced). Argue that your algorithm algorithm indeed has running time O(k). Dont forget to bring back the tree to its original state. Present pseudocode.