Non-recursive Depth-First search:

Question

In this post biziclop inserted the pseudocode for the non-recursive Depth-First Search algorithm.

If we want to use the recursive DFS algorithm is used to check the nodes for a propriety, we can exploit two variants: pre-order (when a node is checked before his children) and post-order (when the children are checked before the node), plus a third variant (in-order: left subtree, then node, then right subtree) for binary tree only.

Since I am interested into having all three variants if possible, I tried to modify biziclop 's pseudocode in order to obtain all three variants of the DFS algorithm. Problem being, I got stuck on the fact that the node is added to the stack (and thus checked) before its children. Any idea?

Answer 1

why " (and thus checked)" ?? in recursive approach you choose to check current node first or first see it's children,here in the same way,you just see nodes,but when to check them?it's on you. for example if you see it's children and checked them,in simple way just use flag to seen_its_children(not means checked)to handle it for post_order,and for in_order it is the same, in pre_order you do just what you said and it is enough.