Preorder and Postorder

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

Hopefully, we’re already familiar with 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