Binary Tree ADT

[tish]

Hi guys im pretty new at C++ and still learning basics. I have to answer the following question and I am lost ... can anyone help me?

Consider two algorithms for traversing a binary tree. Both are non-recursive algorithms that use an extra ADT for bookkeeping. Both algorithms have the following basic form:

Put the root of the tree on the list
While (the ADT is not empty)
{ Remove a node from the ADT and call it n
Visit n
if (n has a left child
Put the child in the ADT
if (n has a right child)
Put the child in the ADT
} //end while

The difference between the two algorithms is the approach for choosing a node n to remove from the ADT.

Algorithm 1: Remove the newest (most recently added) node from the ADT.
Algorithm 2: Remove the oldest (earliest added) node from the ADT.

In what order would each algorithm visit the nodes of the tree in the figure below?

________________________Jane_

_______Bob___________________________________Tom____


Alan________Ellen___________________Nancy______________Wendy

My apologise for the above tree i couldnt paste it in and this seemed to be the only way i could give you an idea of the layout of the tree lol.

Please any help would be great

[Gumbercules]

try to go through it step by step. for algorithm 1:

stack:                       visited:
Jane                         Jane
Bob, Tom                     Tom
bob, Nancy, Wendy            Wendy
Bob, Nancy                   Nancy
Bob                          Bob
Alan, Ellen                  Ellen
Alan                         Alan

for 2

Queue:                       visited:
Jane                         Jane
Bob, Tom                     Bob
Tom, Alan, Ellen             Tom
Allan, Ellen, Nancy, Wendy   Allan
Ellen, Nancy, Wendy          Ellen
Nancy, Wendy                 Nancy
Wendy                        Wendy

[tish]

Aw thank you so much for your help :)
i really appreciate it