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
Pop the vertex at the top of the stack and record its label
Push the children - going from right to left - of this vertex onto the stack
(The stack data structure was explained in Example 10.43).
What is the output when this 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