Consider the following algorithm where the input is a rooted tree with root r.
Step 1: Push r onto the (empty) stack
Step 2: While the stack is not empty
If the entry at the top of the stack is not marked
Then mark it and push its
children-right to left-onto the stack
Else
Pop the vertex at the top of the stack and record its label
What is the output when the algorithm is applied to
(a) The tree in Fig. 12.19?
(b) Any rooted tree?

Transcribed Image Text:

4 7 8 9 11 12 13 14 15 16 17