Topological Sort and Graph Traversals

Trees are ubiquitous in computer science to manipulate various forms of data. A necessary condition for the existence of a topological sort is obviously that the digraph does not contain any cycle. This chapter considers different types of graph traversals: preorder traversal, postorder traversal and in-order traversal. Preorder traversal first output the root, then recursively proceed to a preorder traversal of each subtree rooted at the successors of the root respecting the given ordering of the successors. Postorder traversal first recursively proceed to a postorder traversal of the subtrees rooted at the ordered successors of the root, then output the root. For in-order traversal, we assume that we have a binary rooted tree. Proceed recursively to an in-order traversal of the subtree rooted at the first successor, then output the root, finally recursively proceed to an in-order traversal of the subtree rooted at the second successor of the root.