sort predicate to have nodes sorted in Depth First Search order

Question

I have a list of nodes, where each of the nodes belong to one or multiple trees. (they do not necessarily share a common ancestor)

I want to sort the nodes in the same order I would find them when doing a Depth First Search.

Let say I have a predicate for sorting tree roots together, and another predicate to sort children of a common parent together. Each node have a Parent accessor, and a children enumerator. I want to avoid using the Children enumeration for performance reasons (if possible).

What can be the pseudo code for a predicate to pass to a sort function (the predicate would return a boolean value if node 1 is less than node 2).

Answer 1

I found an easy working solution:

For a node, have a function that returns the path from the root. For example, in a file system, the path for a file could be : c:\directory\file.txt, where "C:", "directory" and "file.txt" are the parent nodes.

The predicate simply need to compare the paths together, as a simple string comparison would do. The path does not need to be a string, the path comparison function need to compare path elements one by one starting at the root, and return as soon a path element is different.

The resulting sort is the same as a Depth First Search.