Preorder and Postorder

Explore the different techniques used to implement the preorder and postorder traversal methods.

Hopefully, you are already familiar with the preorder and postorder traversals of rooted trees, both of which can be computed using depth-first search. Similar traversal orders can be defined for arbitrary directed graphs—even if they are disconnected—by passing around a counter, as shown below. Equivalently, we can use our generic depth-first-search algorithm with the following subroutines PreprocessPreprocess, PreVisitPreVisit, and PostVisitPostVisit.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy