This snippet defines a function walk() which generically performs a depth-first traversal of a tree, using preorder, inorder or postorder rules. Here, genericity means here that there are no hypotheses on what the tree nodes are or the implementation of the tree. Walk() only needs an arbitrary object used as a root node and a function generating children 'nodes' for a given 'node'. At any moment during the walk, it exposes the path from the root node to the visited node. Finally, the implementation is fully non recursive, allowing very deep trees to be traversed.
IMPORTANT: this snippet needs class ConstSequence from the snippet