FAQ: Graph Search: Conceptual - Graph Search Traversal Order

Community%20FAQs%20on%20Codecademy%20Exercises

This community-built FAQ covers the “Graph Search Traversal Order” exercise from the lesson “Graph Search: Conceptual”.

Paths and Courses
This exercise can be found in the following Codecademy content:

FAQs on the exercise Graph Search Traversal Order

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

Can some one explain the post order traversal mentioned in the example? Did quite understand how it started with “Spikes”… Below is the statement from the lesson…

"
Now, let’s say we want the same values, but with each value only added to the list once its vertex has been popped from the stack. In this case, our post-order DFS traversal would result in a list that looked like:

[“Spikes”, “Snakes”, “Lava”, “Piranhas”, “Lasers”]
"

2 Likes

Here’s the graph:

Now you set out, in this order

“lasers” => “lava” => “snakes” => “spikes”. Those names are appended to your stack.

You’re now at the end of a branch, so you back up, popping as you go, appending each name to your “visited” list:

[ "spikes","snakes" , "lava"]

Now you are back at “lasers”, the only remaining name on the stack, but you don’t want to pop that yet, because you’re not done. It’s time to explore the second branch:

“lasers” =>“piranhas”. (end of branch, as “spikes” has already been visited) Now the stack is [“lasers’, 'piranhas”]

So, pop “piranhas”, append to the “visited” list, then pop “lasers”, giving the final list:

[ "spikes","snakes" , "lava", "piranhas", "lasers"]

6 Likes

The final question is as follows:

What would the resulting lists look like from pre-order, post-order, and reverse post-order DFS traversals if the origin vertex were “Spikes”?

What would it look like? I would honestly think the answer to all questions is “empty” since “Spikes” has no edges (correct?) but that feels wrong to me.

2 Likes

@byteninja93187, you’re correct. Since the graph is directed, “Spikes” has no reachable neighbors, so each search would be an empty list.

4 Likes

But you still visited “Spikes” so it should return its value.